/* POTM entry: Fast_and_Furious */ /* Creator: Gunnar Andersson */ /* Email: gunnar@nada.kth.se */ /* Compile with 'gcc Fast_and_Furious.c -lm' */ /* Source last modified April 24, 2000 */ #include #include #include #include #define HASH_SIZE 131072 #define HASH_REPLACE_DRAFT 3 #define EMPTY 0 #define CROSS 1 #define CIRCLE 2 #define UNAVAILABLE 3 #define OUTSIDE 4 #define OPP(player) (CROSS+CIRCLE-(player)) #define TRUE 1 #define FALSE 0 #define EXACT_VALUE 1 #define LOWER_BOUND 2 #define UPPER_BOUND 4 #define DEFAULT_MOVE_TIME 8.0 #define ENDGAME_OFFSET 5 #define INFINITY 12345678 #define TIME_CHECK_INTERVAL 65536 #define MIN(a,b) ((a) < (b) ? (a) : (b)) #define MAX(a,b) ((a) > (b) ? (a) : (b)) typedef struct MoveItem_ { unsigned int move; struct MoveItem_ *pred; struct MoveItem_ *succ; } MoveItem; typedef struct { unsigned int code2; int score; int move; short draft; short flags; } HashEntry; #define COEFF_COUNT 531 int coeffs[COEFF_COUNT] = { 7, 58, -38, 58, 158, -33, -127, 160, 0, 0, -134, 0, 11, 58, -39, 151, 260, -116, -225, 243, 53, 346, 326, -41, -209, -293, -251, 69, 6, 454, -125, 157, 0, -45, -345, 0, 15, 71, -39, 162, 263, -140, -208, 220, 274, 159, 487, 452, -186, -116, -265, -420, -244, 178, 81, 572, 694, 10, -62, 1029, 391, 831, 1250, -49, -136, 97, -291, -310, -324, -352, -646, -278, 113, 2, 219, -160, 471, 262, 1950, -39, -221, -312, 226, 2250, 22, 332, 0, -99, -224, 63, -270, -319, -282, 0, 15, 80, -29, 145, 148, -95, -186, 259, 368, 197, 579, 707, -215, -135, -335, -424, -369, 290, 157, 431, 919, 89, 19, 547, 897, 730, 1885, 1500, -95, -165, -37, -1, -407, -367, -538, -479, -564, -770, -387, 244, 76, 134, 414, 18, -63, 764, 281, 2185, 2200, 4, -101, -204, -248, 722, 508, 2500, 287, 262, 2200, 716, 1565, 2850, -61, -156, 51, -195, -206, 148, 11, 183, -312, -361, -268, -275, -328, -551, -216, -439, -545, -711, -1435, -250, 92, -5, 334, -147, 540, 110, 674, -55, -113, -135, 291, 1000, 18, 1065, 972, 4350, -124, 77, -285, -145, -519, -407, 218, 425, 61, 1000, 5050, 33, -18, 700, 427, 1250, 0, -43, -320, 96, -233, -229, -53, 175, -425, -887, -240, -328, -250, 0, 12, 73, -54, 142, 272, -106, -153, 238, 332, 137, 508, 810, -220, -104, -322, -347, -183, 276, 241, 165, 677, 909, 102, -24, 742, 962, 702, 1950, 1500, -219, -93, -237, -70, 66, -433, -443, -529, -554, -760, -575, -314, 418, 209, 417, 539, 85, -6, 388, 958, 737, 2250, 2200, 4, 46, -94, -175, -129, 967, 710, 2250, 2500, 574, 532, 1950, 2200, 1885, 4285, 3100, -132, -209, -56, 135, -288, -386, 89, -25, 176, 113, -422, -445, -719, -476, -441, -484, -510, -389, -113, -585, -582, -857, -756, -1231, -1500, -250, 196, 98, 378, 522, 18, -39, 752, 180, 854, 674, 34, -72, -389, -42, 705, 556, 827, 1000, 349, 428, 2250, 2185, 4985, 4600, -23, -63, 105, 185, -228, -349, -329, -471, -663, -219, 794, 559, 752, 301, 450, 2250, 2185, 5285, 5300, 237, 172, 99, 175, 1950, 1885, 5300, 785, 650, 4600, 1565, 3165, 6050, -69, -222, 130, -201, -500, 100, -14, 589, -178, -248, -467, -353, 136, 38, 889, -51, -173, 885, 293, 1250, -284, -315, -172, -263, -571, -442, -968, -835, -242, -321, -659, -109, -594, -100, -324, 122, -482, -579, -579, -439, -520, -706, -462, -700, -1435, -1500, -3035, -250, 52, 46, 384, -85, 387, 277, 678, 21, -200, -158, 381, 344, 1000, 166, 2185, 750, 1500, -6, -221, 51, -271, -255, -541, -139, 337, 728, 96, 2185, 750, 2200, 81, 24, -56, 889, 2500, 700, 2265, 2200, 9150, -278, 192, -252, 4, 426, -245, -427, -244, -420, -195, -439, -616, -700, -250, 233, 696, 78, 359, 700, 68, 0, 889, 1065, 700, 2500, 10650, -57, 342, -139, -317, 50, 589, 400, 2200, 11050, 253, 402, 1500, 1250, 2850, 0, -24, -237, 6, -297, -268, 60, -37, 685, -296, -407, -568, -242, -57, 663, -158, -168, 329, 765, -552, -579, -439, -1000, -2135, -250, -527, -439, -287, -935, -250, -250, 0 }; double move_start_time; int empties; int timeout; int selective; int coeff_index; int pow3[] = { 1, 3, 9, 27, 81, 243, 729, 2187 }; int row_pattern[7], col_pattern[7]; int best_pvs_move[50]; int board[64]; int cross_terminal_score[16384]; int cross_stat_score[16384], circle_stat_score[16384]; int influence_mask[16384]; int hit_count[64], fail_high_count[64]; int score3[27], score4[81], score5[243], score6[729], score7[2187]; int *score_table[8] = { NULL, NULL, NULL, score3, score4, score5, score6, score7 }; int *cross_table, *circle_table; unsigned int nodes, last_time_check; unsigned int hash1, hash2; unsigned int hash_code1[4][64], hash_code2[4][64]; HashEntry hash_table[HASH_SIZE]; MoveItem list_head, list_tail; MoveItem list_item[64]; void clear_hash_table( void ) { memset( (void *) hash_table, 0, HASH_SIZE * sizeof( HashEntry ) ); } void initialize_hash( void ) { int i, j; for ( i = 0; i < 4; i++ ) { for ( j = 0; j < 64; j++ ) { hash_code1[i][j] = abs( random() ); hash_code2[i][j] = abs( random() ); } } for ( i = 0; i < 64; i++ ) { hash_code1[EMPTY][i] = 0; hash_code2[EMPTY][i] = 0; } } void calculate_hash_codes( void ) { int i; hash1 = 0; hash2 = 0; for ( i = 0; i < 64; i++ ) { hash1 ^= hash_code1[board[i] & 3][i]; hash2 ^= hash_code2[board[i] & 3][i]; } } void calculate_patterns( void ) { int i, j; int pos; int pattern; for ( i = 0; i < 7; i++ ) { pattern = 0; for ( j = 0, pos = 8 * i; j < 7; j++, pos++ ) pattern += board[pos] << (j << 1); row_pattern[i] = pattern; pattern = 0; for ( j = 0, pos = i; j < 7; j++, pos += 8 ) pattern += board[pos] << (j << 1); col_pattern[i] = pattern; } } void score_block( int *array, int start, int inc, int *cross_score, int *circle_score ) { int i; int pos; int consecutive; int score[8] = { 0, 0, 0, 3, 10, 25, 56, 119 }; for ( i = 0, pos = start; i < 5; i++, pos += inc ) if ( array[pos] == CROSS ) { consecutive = 1; i++; pos += inc; while ( (i < 7) && (array[pos] == CROSS) ) { consecutive++; i++; pos += inc; } i--; pos -= inc; *cross_score += score[consecutive]; } else if ( array[pos] == CIRCLE ) { consecutive = 1; i++; pos += inc; while ( (i < 7) && (array[pos] == CIRCLE) ) { consecutive++; i++; pos += inc; } i--; pos -= inc; *circle_score += score[consecutive]; } } #define IS_ACTIVE(row,col) \ ((influence_mask[row_pattern[row]] & (1 << col)) || \ (influence_mask[col_pattern[col]] & (1 << row))) int count_active( void ) { int active_count; unsigned int move, row, col; calculate_patterns(); active_count = 0; for ( move = 0; move < 64; move++ ) if ( board[move] == EMPTY ) { row = move >> 3; col = move & 7; if ( IS_ACTIVE( row, col ) ) active_count++; } return active_count; } void initialize_score_patterns( void ) { int i, j; int cross_score, circle_score; int row[7]; for ( i = 0; i < 7; i++ ) row[i] = 0; for ( i = 0; i < 16384; i++ ) { cross_score = 0; circle_score = 0; score_block( row, 0, 1, &cross_score, &circle_score ); cross_terminal_score[i] = 100 * (cross_score - circle_score); j = 0; do { row[j] = (row[j] + 1) & 3; j++; } while ( row[j - 1] == 0 ); } } void expand_pattern( int width, int *table ) { int i, j; int connected; int mirror; int row[8]; for ( i = 0; i < width; i++ ) row[i] = 0; for ( i = 0; i < pow3[width]; i++ ) { connected = TRUE; for ( j = 0; j < width - 1; j++ ) if ( row[j] * row[j + 1] == CROSS * CIRCLE ) connected = FALSE; if ( connected ) { mirror = 0; for ( j = 0; j < width; j++ ) mirror += row[j] * pow3[width - j - 1]; if ( MIN( i, mirror ) == i ) table[i] = coeffs[coeff_index++]; else table[i] = table[mirror]; } else table[i] = 0; j = 0; do { row[j] = (row[j] + 1) % 3; j++; } while ( row[j - 1] == 0 ); } } void compute_line_patterns( void ) { int i, j, k; int left, right; int width; int mask; int cross_pattern, circle_pattern; int row[7]; for ( i = 0; i < 7; i++ ) row[i] = 0; for ( i = 0; i < 16384; i++ ) { cross_stat_score[i] = cross_terminal_score[i]; circle_stat_score[i] = cross_terminal_score[i]; influence_mask[i] = 0; for ( j = 0; j < 7; j++ ) if ( row[j] != UNAVAILABLE ) { left = j; right = j; while ( (right < 6) && (row[right + 1] != UNAVAILABLE) && (row[right] * row[right + 1] != CROSS * CIRCLE) ) right++; width = right - left + 1; if ( width >= 3 ) { cross_pattern = 0; circle_pattern = 0; mask = 0; for ( k = 0; k < width; k++ ) { if ( row[left + k] == EMPTY ) mask |= 1 << (left + k); cross_pattern += row[left + k] * pow3[k]; circle_pattern += ((2 * row[left + k]) % 3) * pow3[k]; } cross_stat_score[i] += score_table[width][cross_pattern]; circle_stat_score[i] -= score_table[width][circle_pattern]; if ( (width > 3) || (row[left + 1] != EMPTY) || (row[left] == row[left + 2]) || (row[left] == EMPTY) || (row[left + 2] == EMPTY) ) influence_mask[i] |= mask; } j = right; } j = 0; do { row[j] = (row[j] + 1) & 3; j++; } while ( row[j - 1] == 0 ); } } void initialize_new_score_patterns( void ) { coeff_index = 0; expand_pattern( 3, score3 ); expand_pattern( 4, score4 ); expand_pattern( 5, score5 ); expand_pattern( 6, score6 ); expand_pattern( 7, score7 ); if ( coeff_index != COEFF_COUNT ) { printf( "COEFF_COUNT = %d\n", COEFF_COUNT ); printf( "coeff_index = %d\n", coeff_index ); } compute_line_patterns(); } #define TABLE_EVAL( table ) \ (table[row_pattern[0]] + \ table[row_pattern[1]] + \ table[row_pattern[2]] + \ table[row_pattern[3]] + \ table[row_pattern[4]] + \ table[row_pattern[5]] + \ table[row_pattern[6]] + \ table[col_pattern[0]] + \ table[col_pattern[1]] + \ table[col_pattern[2]] + \ table[col_pattern[3]] + \ table[col_pattern[4]] + \ table[col_pattern[5]] + \ table[col_pattern[6]]) #define EVAL_POSITION( side_to_move ) \ (((side_to_move) == CROSS) ? TABLE_EVAL( cross_table ) : \ -TABLE_EVAL( circle_table ) ) #define MAKE_MOVE( move ) { \ row_pattern[row] += side_to_move << (col << 1); \ col_pattern[col] += side_to_move << (row << 1); \ } #define MAKE_MOVE_HASH( move ) { \ empties--; \ row_pattern[row] += side_to_move << (col << 1); \ col_pattern[col] += side_to_move << (row << 1); \ stored_hash1 = hash1; \ hash1 ^= hash_code1[side_to_move][move]; \ stored_hash2 = hash2; \ hash2 ^= hash_code2[side_to_move][move]; \ } #define UNMAKE_MOVE( move ) { \ row_pattern[row] -= side_to_move << (col << 1); \ col_pattern[col] -= side_to_move << (row << 1); \ } #define UNMAKE_MOVE_HASH( move ) { \ empties++; \ row_pattern[row] -= side_to_move << (col << 1); \ col_pattern[col] -= side_to_move << (row << 1); \ hash1 = stored_hash1; \ hash2 = stored_hash2; \ } #define ADD_HASH( new_score, new_move, new_draft, new_flags ) \ do { \ int index = hash1 & (HASH_SIZE - 1); \ if ( hash_table[index].draft <= (new_draft) + HASH_REPLACE_DRAFT ) { \ hash_table[index].code2 = hash2; \ hash_table[index].score = (new_score); \ hash_table[index].move = (new_move); \ hash_table[index].draft = (new_draft); \ hash_table[index].flags = (new_flags); \ } \ } while ( FALSE ) double get_timer( void ) { return (double) clock() / ((double) CLOCKS_PER_SEC); } int ab_search( int side_to_move, int draft, int alpha, int beta, int do_hash ) { int opponent = OPP( side_to_move ); int this_score, best_score; int found_active; unsigned int move, best_move, row, col; MoveItem *item; nodes++; best_score = -INFINITY; found_active = FALSE; for ( item = list_head.succ; item != &list_tail; item = item->succ ) { move = item->move; row = move >> 3; col = move & 7; if ( IS_ACTIVE( row, col ) ) { found_active = TRUE; hit_count[move]++; MAKE_MOVE( move ); if ( draft == 1 ) { this_score = -EVAL_POSITION( opponent ); nodes++; } else { item->pred->succ = item->succ; item->succ->pred = item->pred; this_score = -ab_search( opponent, draft - 1, -beta, -alpha, FALSE ); item->pred->succ = item; item->succ->pred = item; } UNMAKE_MOVE( move ); if ( this_score > best_score ) { if ( this_score > alpha ) { if ( this_score >= beta ) { fail_high_count[move]++; if ( do_hash ) ADD_HASH( this_score, move, draft, LOWER_BOUND ); return this_score; } alpha = this_score; } best_score = this_score; best_move = move; } } } if ( !found_active ) return EVAL_POSITION( side_to_move ); if ( do_hash ) ADD_HASH( best_score, best_move, draft, UPPER_BOUND ); return best_score; } int pvs_search( int side_to_move, int depth, int max_depth, int alpha, int beta ) { int i, j; int draft; int original_alpha, curr_alpha; int opponent; int hash_move; int this_score, best_score; int best_index, best_shallow_score; int move_count; int shallow_search; int score_list[49]; unsigned int stored_hash1, stored_hash2; unsigned int hash_index; unsigned int move, row, col; MoveItem *item, *last_inactive; MoveItem *move_ptr[49]; nodes++; if ( depth == max_depth ) return EVAL_POSITION( side_to_move ); draft = max_depth - depth; original_alpha = alpha; hash_move = -1; hash_index = hash1 & (HASH_SIZE - 1); if ( hash2 == hash_table[hash_index].code2 ) { if ( draft == hash_table[hash_index].draft ) { this_score = hash_table[hash_index].score; if ( hash_table[hash_index].flags & EXACT_VALUE ) return this_score; if ( (this_score <= alpha) && (hash_table[hash_index].flags & UPPER_BOUND) ) return this_score; if ( (this_score >= beta) && (hash_table[hash_index].flags & LOWER_BOUND) ) return this_score; } hash_move = hash_table[hash_index].move; } shallow_search = ((draft >= 3) && (empties >= 9)) || (depth == 0); if ( !shallow_search ) return ab_search( side_to_move, draft, alpha, beta, FALSE ); if ( selective && (draft >= 4) && (draft <= 8) && (depth > 0) ) { int bound; int shallow; int window; if ( draft == 4 ) { shallow = 2; window = 100; } else if ( draft == 5 ) { shallow = 3; window = 125; } else if ( draft == 6 ) { shallow = 2; window = 150; } else if ( draft == 7 ) { shallow = 3; window = 125; } else { shallow = 4; window = 125; } bound = beta + window; selective = FALSE; this_score = pvs_search( side_to_move, depth, depth + shallow, bound, bound + 1 ); selective = TRUE; if ( this_score >= bound + 1 ) { ADD_HASH( beta, best_pvs_move[depth], draft, LOWER_BOUND ); return beta; } bound = alpha - window; selective = FALSE; this_score = pvs_search( side_to_move, depth, depth + shallow, bound - 1, bound ); selective = TRUE; if ( this_score <= bound - 1 ) { ADD_HASH( alpha, best_pvs_move[depth], draft, UPPER_BOUND ); return alpha; } } opponent = OPP( side_to_move ); move_count = 0; last_inactive = NULL; for ( item = list_head.succ; item != &list_tail; item = item->succ ) { move = item->move; row = move >> 3; col = move & 7; if ( IS_ACTIVE( row, col ) ) { if ( move == hash_move ) score_list[move_count] = INFINITY; else { MAKE_MOVE( move ); score_list[move_count] = -EVAL_POSITION( opponent ); UNMAKE_MOVE( move ); nodes++; } move_ptr[move_count] = item; move_count++; } else last_inactive = item; } if ( move_count == 0 ) return EVAL_POSITION( side_to_move ); else { best_score = -INFINITY; curr_alpha = alpha; for ( i = 0; i < move_count; i++ ) { best_index = i; best_shallow_score = score_list[i]; for ( j = i; j < move_count; j++ ) if ( score_list[j] > best_shallow_score ) { best_index = j; best_shallow_score = score_list[j]; } item = move_ptr[best_index]; move_ptr[best_index] = move_ptr[i]; score_list[best_index] = score_list[i]; if ( nodes > last_time_check + TIME_CHECK_INTERVAL ) { last_time_check = nodes; if ( get_timer() - move_start_time >= DEFAULT_MOVE_TIME ) timeout = TRUE; } if ( timeout ) return 0; item->pred->succ = item->succ; item->succ->pred = item->pred; move = item->move; row = move >> 3; col = move & 7; MAKE_MOVE_HASH( move ); if ( i == 0 ) { best_score = this_score = -pvs_search( opponent, depth + 1, max_depth, -beta, -alpha ); best_pvs_move[depth] = move; } else { curr_alpha = MAX( best_score, curr_alpha ); this_score = -pvs_search( opponent, depth + 1, max_depth, -(curr_alpha + 1), -curr_alpha ); if ( (this_score > curr_alpha) && (this_score < beta) ) this_score = -pvs_search( opponent, depth + 1, max_depth, -beta, -this_score ); if ( this_score > best_score ) { best_score = this_score; best_pvs_move[depth] = move; } } UNMAKE_MOVE_HASH( move ); item->pred->succ = item; item->succ->pred = item; if ( best_score >= beta ) { ADD_HASH( best_score, best_pvs_move[depth], draft, LOWER_BOUND ); return this_score; } } } if ( best_score > original_alpha ) ADD_HASH( best_score, best_pvs_move[depth], draft, EXACT_VALUE ); else ADD_HASH( best_score, best_pvs_move[depth], draft, UPPER_BOUND ); return best_score; } int get_pseudorandom_move( void ) { int i; int move_count; int moves[49]; move_count = 0; for ( i = 0; i < 64; i++ ) if ( board[i] == EMPTY ) moves[move_count++] = i; return moves[6700417 % move_count]; } void prepare_search( void ) { double goodness[64]; int i; int change; int move_order[49] = { /* D4 */ 27, /* D3 */ 19 , 26, 28, 35, /* C3 */ 18, 20, 34, 36, /* D2 */ 11, 29, 43, 25, /* C2 */ 10, 12, 21, 37, 42, 44, 17, 33, /* B2 */ 9, 13, 41, 45, /* D1 */ 3, 30, 51, 24, /* C1 */ 2, 4, 22, 38, 50, 52, 16, 32, /* B1 */ 1, 5, 14, 46, 49, 53, 8, 40, /* A1 */ 0, 6, 54, 48 }; unsigned int move, row, col; MoveItem *ptr; for ( i = 0; i < 64; i++ ) goodness[i] = fail_high_count[i] / (hit_count[i] + 1.0); do { change = FALSE; for ( i = 0; i < 48; i++ ) if ( goodness[move_order[i]] < goodness[move_order[i + 1]] ) { int temp = move_order[i]; move_order[i] = move_order[i + 1]; move_order[i + 1] = temp; change = TRUE; } } while ( change ); ptr = &list_head; for ( i = 0; i < 49; i++ ) { move = move_order[i]; row = move >> 3; col = move & 7; if ( (board[move] == EMPTY) && IS_ACTIVE( row, col ) ) { ptr->succ = &(list_item[move]); list_item[move].pred = ptr; ptr = ptr->succ; ptr->move = move; } } ptr->succ = &list_tail; list_tail.pred = ptr; } int get_best_move( int side_to_move, int max_depth ) { int i; int best_move; int depth; int score; int active; best_move = get_pseudorandom_move(); active = count_active(); if ( (max_depth == 0) || (active == 0) ) return best_move; nodes = 0; last_time_check = 0; move_start_time = get_timer(); timeout = FALSE; calculate_patterns(); clear_hash_table(); calculate_hash_codes( ); for ( i = 0; i < 64; i++ ) { hit_count[i] = 0; fail_high_count[i] = 0; } max_depth = MIN( max_depth, active ); for ( depth = 1; depth <= max_depth; depth++ ) { if ( (max_depth >= active) && (depth + ENDGAME_OFFSET >= active) ) { selective = FALSE; depth = active; } prepare_search(); score = pvs_search( side_to_move, 0, depth, -INFINITY, INFINITY ); if ( timeout ) break; best_move = best_pvs_move[0]; } return best_move; } int main( void ) { char buffer[256]; int i, j; int pos; int move; int side_to_move; for ( i = 0; i < 64; i++ ) board[i] = OUTSIDE; for ( i = 0; i < 7; i++ ) for ( j = 0; j < 7; j++ ) board[8 * i + j] = EMPTY; empties = 0; for ( i = 0; i < 7; i++ ) { fgets( buffer, 256, stdin ); if ( strlen( buffer ) < 7 ) { fprintf( stderr, "Row %d contains < 7 characters\n", i + 1 ); exit( EXIT_FAILURE ); } for ( j = 0; j < 7; j++ ) { pos = 8 * i + j; switch ( buffer[j] ) { case '-': board[pos] = EMPTY; empties++; break; case 'X': board[pos] = CROSS; break; case 'O': board[pos] = CIRCLE; break; case '+': board[pos] = UNAVAILABLE; break; default: fprintf( stderr, "Character %d on row %d is invalid\n", j + 1, i + 1 ); exit( EXIT_FAILURE ); break; } } } srandom( time( NULL ) ); initialize_score_patterns(); initialize_new_score_patterns(); initialize_hash(); cross_table = cross_stat_score; circle_table = circle_stat_score; selective = TRUE; if ( (empties % 2) == 0 ) side_to_move = CROSS; else side_to_move = CIRCLE; move = get_best_move( side_to_move, INFINITY ); board[move] = side_to_move; for ( i = 0; i < 7; i++ ) { for ( j = 0; j < 7; j++ ) { pos = 8 * i + j; switch ( board[pos] ) { case EMPTY: putchar( '-' ); break; case CROSS: putchar( 'X' ); break; case CIRCLE: putchar( 'O' ); break; case UNAVAILABLE: putchar( '+' ); break; default: fputs( "Internal error in output\n", stderr ); break; } } puts( "" ); } return EXIT_SUCCESS; }