A little app to simulate every possible move in Connect Four.
singingpigs.online
1#include "core.h"
2#include "helpers.h"
3
4#include <cassert>
5#include <math.h>
6#include "SDL.h"
7#include <stdio.h>
8
9struct WinningBoardCollection
10{
11 uint8_t num_boards;
12 binary_board* boards;
13};
14
15MakeMoveResult make_move_table_partial[2][MAKE_MOVE_TABLE_PARTIAL_SIZE];
16MakeMoveResult make_move_table_full[2][MAKE_MOVE_TABLE_FULL_SIZE];
17
18const uint8_t CHECK_FOR_WIN_PROCESSED_COLUMN_TABLE_SIZE = MAX_FULL_COLUMN + 1;
19uint8_t check_for_win_processed_column_table[2][CHECK_FOR_WIN_PROCESSED_COLUMN_TABLE_SIZE];
20WinningBoardCollection check_for_win_processed_winning_boards_table[NUM_ROWS][NUM_COLUMNS];
21
22void init_board(BoardState state)
23{
24 for (uint8_t col = 0; col < NUM_COLUMNS; ++col)
25 {
26 state[col] = 1;
27 }
28}
29
30inline int8_t get_board_value(BoardState state, uint8_t row, uint8_t col)
31{
32 assert(row < NUM_ROWS && col < NUM_COLUMNS);
33
34 return state[col] < (1 << (row + 1)) ? -1 : ((state[col] & (1 << row)) >> row);
35}
36
37int8_t make_move_column(uint8_t player, uint8_t* column_state)
38{
39 if (*column_state >= MIN_FULL_COLUMN)
40 return -1;
41
42 uint8_t mask = *column_state; // 0011 0000 (example)
43 mask |= mask >> 1; // 0011 1000
44 mask |= mask >> 2; // 0011 1110
45 mask |= mask >> 4; // 0011 1111
46 ++mask; // 0100 0000
47
48 // add 1 to top of stack
49 *column_state |= mask; // 0111 0000
50 if (player == 0)
51 {
52 // clear top piece of the stack for player 0
53 *column_state &= ~(mask >> 1); // 0101 0000
54 }
55
56 switch (mask)
57 {
58 case 0b00000010:
59 return 0;
60 case 0b00000100:
61 return 1;
62 case 0b00001000:
63 return 2;
64 case 0b00010000:
65 return 3;
66 case 0b00100000:
67 return 4;
68 case 0b01000000:
69 return 5;
70 default:
71 assert(false);
72 return -1;
73 }
74}
75
76inline binary_board bit_set(binary_board num, uint8_t row, uint8_t col)
77{
78 return num | ((binary_board)1 << (col * 8 + (row)));
79}
80
81void init_core()
82{
83 SDL_Init(0);
84
85 // Building make_move partial lookup table (skips full columns)
86 for (uint8_t player = 0; player < 2; ++player)
87 {
88 make_move_table_partial[player][0] = MakeMoveResult { -1, 0 };
89 for (uint8_t column_state = 1; column_state < MAKE_MOVE_TABLE_PARTIAL_SIZE; ++column_state)
90 {
91 MakeMoveResult result;
92 result.column_state = column_state;
93 result.row = make_move_column(player, &result.column_state);
94 make_move_table_partial[player][column_state] = result;
95 }
96 }
97
98 // Building make_move full lookup table (includes full columns)
99 for (uint8_t player = 0; player < 2; ++player)
100 {
101 make_move_table_full[player][0] = MakeMoveResult { -1, 0 };
102 for (uint8_t column_state = 1; column_state < MAKE_MOVE_TABLE_FULL_SIZE; ++column_state)
103 {
104 MakeMoveResult result;
105 result.column_state = column_state;
106 result.row = make_move_column(player, &result.column_state);
107 make_move_table_full[player][column_state] = result;
108 }
109 }
110
111 // Building check_for_win processed column lookup table
112 for (uint8_t player = 0; player < 2; ++player)
113 {
114 check_for_win_processed_column_table[player][0] = 0;
115 for (uint8_t in_column = 1; in_column < CHECK_FOR_WIN_PROCESSED_COLUMN_TABLE_SIZE; ++in_column)
116 {
117 // Remove top-of-stack bit
118 uint8_t mask = in_column; // 0011 0000 (example)
119 mask |= mask >> 1; // 0011 1000
120 mask |= mask >> 2; // 0011 1110
121 mask |= mask >> 4; // 0011 1111
122 mask >>= 1; // 0001 1111
123
124 uint8_t out_column = in_column;
125 if (player == 0)
126 {
127 out_column = ~out_column; // 1100 1111
128 out_column &= mask; // 0000 1111
129 }
130 else
131 {
132 out_column &= mask; // 0001 0000
133 }
134
135 check_for_win_processed_column_table[player][in_column] = out_column;
136 }
137 }
138
139 // Building check_for_win winning board lookup table
140 for (uint8_t table_row = 0; table_row < NUM_ROWS; ++table_row)
141 {
142 for (uint8_t table_col = 0; table_col < NUM_COLUMNS; ++table_col)
143 {
144 binary_board boards[32];
145 uint8_t num_boards = 0;
146
147 // Vertical
148 for (uint8_t row_start = 0; row_start <= (NUM_ROWS - NUM_TO_WIN); ++row_start)
149 {
150 binary_board winning_board_state = 0;
151 for (uint8_t row_offset = 0; row_offset < NUM_TO_WIN; ++row_offset)
152 {
153 winning_board_state = bit_set(winning_board_state, row_start + row_offset, table_col);
154 }
155
156 boards[num_boards] = winning_board_state;
157 ++num_boards;
158 }
159
160 // Horizontal
161 for (uint8_t col_start = 0; col_start <= (NUM_COLUMNS - NUM_TO_WIN); ++col_start)
162 {
163 binary_board winning_board_state = 0;
164 for (uint8_t col_offset = 0; col_offset < NUM_TO_WIN; ++col_offset)
165 {
166 winning_board_state = bit_set(winning_board_state, table_row, col_start + col_offset);
167 }
168
169 boards[num_boards] = winning_board_state;
170 ++num_boards;
171 }
172
173 // Diagonal (bottom-left to top-right)
174 {
175 uint8_t diag_row = table_row;
176 uint8_t diag_col = table_col;
177 while (diag_row > 0 && diag_col > 0)
178 {
179 --diag_row;
180 --diag_col;
181 }
182
183 while (diag_row + NUM_TO_WIN <= NUM_ROWS && diag_col + NUM_TO_WIN <= NUM_COLUMNS)
184 {
185 binary_board winning_board_state = 0;
186 for (uint8_t i = 0; i < NUM_TO_WIN; ++i)
187 {
188 winning_board_state = bit_set(winning_board_state, diag_row + i, diag_col + i);
189 }
190
191 boards[num_boards] = winning_board_state;
192 ++num_boards;
193
194 ++diag_row;
195 ++diag_col;
196 }
197 }
198
199 // Diagonal (top-left to bottom-right)
200 {
201 int8_t diag_row = table_row;
202 uint8_t diag_col = table_col;
203 while (diag_row + 1 < NUM_ROWS && diag_col > 0)
204 {
205 ++diag_row;
206 --diag_col;
207 }
208
209 while ((diag_row + 1) - NUM_TO_WIN >= 0 && diag_col + NUM_TO_WIN <= NUM_COLUMNS)
210 {
211 binary_board winning_board_state = 0;
212 for (uint8_t i = 0; i < NUM_TO_WIN; ++i)
213 {
214 winning_board_state = bit_set(winning_board_state, diag_row - i, diag_col + i);
215 }
216
217 boards[num_boards] = winning_board_state;
218 ++num_boards;
219
220 --diag_row;
221 ++diag_col;
222 }
223 }
224
225 WinningBoardCollection board_collection;
226 board_collection.num_boards = num_boards;
227 board_collection.boards = (binary_board*)malloc(num_boards * sizeof(binary_board));
228 memcpy(board_collection.boards, boards, num_boards * sizeof(binary_board));
229
230 check_for_win_processed_winning_boards_table[table_row][table_col] = board_collection;
231 }
232 }
233}
234
235int8_t make_move(uint8_t player, uint8_t column, BoardState state)
236{
237 assert(column >= 0 && column < NUM_COLUMNS);
238
239 return make_move_column(player, &state[column]);
240}
241
242bool check_for_win(BoardState state, uint8_t last_move_player, uint8_t last_move_row, uint8_t last_move_col)
243{
244 assert(last_move_player <= 1);
245 assert(last_move_row < NUM_ROWS && last_move_col < NUM_COLUMNS);
246
247 uint8_t processed_board_state[NUM_COLUMNS_PROCESSED] = { 0 };
248 for (uint8_t col = 0; col < NUM_COLUMNS; ++col)
249 {
250 assert(state[col] < MAX_FULL_COLUMN + 1);
251 processed_board_state[col] = check_for_win_processed_column_table[last_move_player][state[col]];
252 }
253
254 binary_board* processed_board_state_binary = (binary_board*)processed_board_state;
255
256 WinningBoardCollection winning_boards = check_for_win_processed_winning_boards_table[last_move_row][last_move_col];
257 for (uint8_t i = 0; i < winning_boards.num_boards; ++i)
258 {
259 binary_board winning_board_state = winning_boards.boards[i];
260 if ((winning_board_state & *processed_board_state_binary) == winning_board_state)
261 {
262 return true;
263 }
264 }
265
266 return false;
267}
268
269uint64_t total_moves_evaluated;
270uint64_t wins_found;
271uint64_t dead_ends_found;
272uint8_t min_depth;
273uint64_t time_of_last_print;
274uint64_t get_move_score_start_time;
275
276struct MoveEvalNode
277{
278 uint8_t curr_move_column = 0;
279 BoardState state;
280 int64_t score = 0;
281};
282
283void get_move_scores(int64_t final_scores[NUM_COLUMNS])
284{
285 MoveEvalNode nodes[44];
286 init_board(nodes[0].state);
287
288 get_move_score_start_time = SDL_GetTicks();
289 time_of_last_print = get_move_score_start_time;
290 total_moves_evaluated = 0;
291 wins_found = 0;
292 dead_ends_found = 0;
293 min_depth = 50;
294
295 int8_t depth = 0;
296 uint8_t player = 0;
297 uint8_t player_this_turn = 0;
298 while (depth >= 0)
299 {
300 // Print status update every 100 ms.
301 uint64_t time_current = SDL_GetTicks();
302 if (time_current - time_of_last_print >= 1000)
303 {
304 print_board(nodes[depth].state);
305
306 time_of_last_print = time_current;
307
308 double_t percent_completed = 100.0 * total_moves_evaluated / 4531985219092;
309 uint64_t time_elapsed = time_current - get_move_score_start_time;
310 double_t time_to_complete = (time_elapsed / 1000.0) * (100.0 / percent_completed);
311
312 printf("Total moves: %lu (%f%%), wins found: %lu, dead-ends found: %lu, depth: %d\n", total_moves_evaluated, percent_completed, wins_found, dead_ends_found, min_depth);
313
314 char friendly_time_string[256];
315 sprint_friendly_time(time_to_complete, friendly_time_string);
316 printf("- Time to complete: %s\n", friendly_time_string);
317 }
318
319 // Make move from current node to next node, based on curr_move_column.
320 memcpy(nodes[depth + 1].state, nodes[depth].state, sizeof(BoardState));
321 int8_t row = make_move_lookup_full(player_this_turn, nodes[depth].curr_move_column, nodes[depth + 1].state);
322
323 bool move_to_next_column = false;
324
325 if (row < 0)
326 {
327 // Move not possible.
328 ++dead_ends_found;
329
330 move_to_next_column = true;
331 }
332 else
333 {
334 ++total_moves_evaluated;
335 if (check_for_win(nodes[depth + 1].state, player_this_turn, row, nodes[depth].curr_move_column))
336 {
337 ++wins_found;
338
339 // Dumb little score function just to get the functionality right.
340 nodes[depth].score += player_this_turn == player ? 1 : -1;
341
342 move_to_next_column = true;
343 }
344 else
345 {
346 // If this is not a win or dead end, we'll move down to the next node.
347 ++depth;
348 nodes[depth].curr_move_column = 0;
349 nodes[depth].score = 0;
350 player_this_turn = 1 - player_this_turn;
351 }
352 }
353
354 // Move to next column, and backtrack if needed.
355 if (move_to_next_column)
356 {
357 // Next column.
358 ++nodes[depth].curr_move_column;
359
360 // If we've checked every column...
361 while (nodes[depth].curr_move_column >= NUM_COLUMNS)
362 {
363 min_depth = depth < min_depth ? depth : min_depth;
364
365 // Go back up a node (and exit out if we're going past the top).
366 --depth;
367 if (depth < 0)
368 break;
369
370 // If we're at the top...
371 if (depth == 0)
372 {
373 // Record this move's score.
374 final_scores[nodes[depth].curr_move_column] = nodes[depth + 1].score;
375 }
376 // Otherwise...
377 else
378 {
379 // Add score from child node.
380 nodes[depth].score += nodes[depth + 1].score;
381 }
382
383 // Reset and go to next column.
384 nodes[depth + 1].curr_move_column = 0;
385 nodes[depth + 1].score = 0;
386 ++nodes[depth].curr_move_column;
387 player_this_turn = 1 - player_this_turn;
388 }
389 }
390 }
391}
392
393void sprint_board(BoardState state, char* buffer)
394{
395 for (uint8_t i = 0; i < NUM_COLUMNS; ++i)
396 {
397 snprintf(buffer, 256, "_%d", i + 1);
398 buffer += 2;
399 }
400
401 snprintf(buffer, 256, "_\n");
402 buffer += 2;
403 for (int8_t row = NUM_ROWS - 1; row >= 0; --row)
404 {
405 snprintf(buffer, 256, "|");
406 buffer += 1;
407 for (uint8_t col = 0; col < NUM_COLUMNS; ++col)
408 {
409 switch (get_board_value(state, row, col))
410 {
411 case 0:
412 snprintf(buffer, 256, "O");
413 buffer += 1;
414 break;
415 case 1:
416 snprintf(buffer, 256, "X");
417 buffer += 1;
418 break;
419 default:
420 snprintf(buffer, 256, " ");
421 buffer += 1;
422 break;
423 }
424
425 snprintf(buffer, 256, "|");
426 buffer += 1;
427 }
428 snprintf(buffer, 256, "\n");
429 buffer += 1;
430 }
431 for (uint8_t i = 0; i < NUM_COLUMNS; ++i)
432 {
433 snprintf(buffer, 256, "--");
434 buffer += 2;
435 }
436 snprintf(buffer, 256, "‾\n");
437}
438
439void print_board(BoardState state)
440{
441 char* board = (char*)malloc(sizeof(char) * 256);
442 sprint_board(state, board);
443 printf("%s", board);
444 free(board);
445}