blob: 08f6c1149e103461be845bbe15151d7c94a9248b [file] [log] [blame]
 #include "globals.h" #define PRINT_DOES_X_WIN_INFO // If defined we just immediately return from each function with // a value of -1. (In other words no winner yet.) //#define NOTHING // If defined don't pack any protected moves onto the board. //#define NO_PROT // If defined pretend all (unpacked) squares are available to opponent. //#define NO_UNUSED // If defined pretend we didn't find any vulnerable moves with a prot square. //#define NO_VULN_W_PROT // If defined pretend we didn't find any vulnerable moves with a prot square. //#define NO_VULN_TYPE_1 // If defined pretend there were no vulnerable moves (note this also // means NO_VULN_W_PROT). //#define NO_VULN // If defined don't look for safe options. //#define NO_SAFE_OPT //################################################################# // This function tries to pack as many 'protective' areas onto // the board as it can. (no guarantee of optimality). //################################################################# static inline void pack_prot(u32bit tmp_board[32], s32bit player, s32bit *prot) { s32bit r = 0, p = 0; //row, and number of prot. areas we have placed. u32bit tmp, inter, walls; for(r = 0; r < g_board_size[player]; r++){ // set bit at each position where there is interference. inter = (tmp_board[r] | tmp_board[r+1] | tmp_board[r+2] | tmp_board[r+3] | g_board[player][r+1] | g_board[player][r+2]); inter = (inter >> 1) | inter; // set bit at each position which there is a wall. walls = ( ((g_board[player][r] >> 1) & g_board[player][r]) | ((g_board[player][r+3] >> 1) & g_board[player][r+3]) ); // combine (bit set at each position which we can place a prot. area). inter = walls & ~inter; // process the positions. while(inter){ tmp = (inter & -inter); // least sig bit of m inter &= ~(tmp | (tmp << 1)); // remove bit and next bit. tmp_board[r+1] |= tmp | (tmp << 1); //record where we put tmp_board[r+2] |= tmp | (tmp << 1); // the protective square. p++; // count it. } } *prot = p; } //################################################################# // This function tries to pack as many 'vuln. type 1 and 2' areas // onto the board as it can. (no guarantee of optimality). // It also counts the number of unused squares. //################################################################# static void pack_vuln(u32bit tmp_board[32], s32bit player, s32bit *vuln2, s32bit *vuln2_w_prot, s32bit *vuln1, s32bit *vuln1_w_prot, s32bit *unused) //, s32bit print) { u32bit curr_row, adj_rows, next_prev_row; u32bit tmp = 0, tmp_; s32bit v2 = 0, v2_p = 0, v1 = 0, v1_p = 0, u = 0; s32bit r, state; u32bit s_v = 0; //start of vulnerable for(r = 0; r < g_board_size[player]; r++){ next_prev_row = tmp_board[r]; next_prev_row |= ~(g_board[player][r+2] | (g_board[player][r+2] << 1)); next_prev_row |= ~(g_board[player][r+2] | (g_board[player][r+2] >> 1)); curr_row = ~(g_board[player][r+1] | tmp_board[r+1]); adj_rows = g_board[player][r] & g_board[player][r+2]; state = 0; //======================================================== // Three types of squares, prot, empty, occ. // // state = 0 // if(prot) -> state = 1 // if(empty) -> state = 2, c_t = c, // if(occ) -> state = 0 // // state = 1 // if(prot) -> state = 0, safe++ // if(empty) -> state = 0, v_p++, mark(c-1) // if(occ) -> state = 0, unu++ // // state = 2 // if(prot) -> state = 3, // if(empty) -> state = 0, vuln++, mark(c_t) // if(occ) -> state = 0, // // state = 3 // if(prot) -> state = 4, safe++ // if(empty) -> state = 2, v_p++, mark(c_t), c_t = c // if(occ) -> state = 0, v_p++, mark(c_t) // // state = 4 // if(prot) -> state = 3 // if(empty) -> state = 2, c_t = c // if(occ) -> state = 0 //======================================================== while(curr_row){ tmp_ = (curr_row & -curr_row); //get least sig bit of curr_row curr_row ^= tmp_; //remove least sig bit of curr_row. // if true then this iteration and last iteration are not contiguous. // Which means there was an occupied square. if ( ((tmp_ >> 1) & tmp) == 0 ) { if(state == 1) { u++; tmp_board[r+1] |= tmp; } else if(state == 3) { tmp_board[r+1] |= (s_v | (s_v << 1)); if((s_v & next_prev_row) || ((s_v << 1) & next_prev_row)) v2_p++; else v1_p++; } state = 0; } tmp = tmp_; // empty and protected if( tmp & adj_rows ){ if(state == 0) { state = 1; } else if(state == 1) { state = 0; //safe } else if(state == 2) { state = 3; } else if(state == 3) { state = 4; //safe } else if(state == 4) { state = 3; } } // unprotected else { if(state == 0) { state = 2; s_v = tmp; } else if(state == 1){ state = 0; // Check tmp >> 1 tmp_board[r+1] |= (tmp | (tmp >> 1)); if((tmp & next_prev_row) || ((tmp >> 1) & next_prev_row)) v2_p++; else v1_p++; } else if(state == 2){ state = 0; tmp_board[r+1] |= (s_v | (s_v << 1)); if((s_v & next_prev_row) || ((s_v << 1) & next_prev_row)) v2++; else v1++; } else if(state == 3){ state = 2; tmp_board[r+1] |= (s_v | (s_v << 1)); if((s_v & next_prev_row) || ((s_v << 1) & next_prev_row)) v2_p++; else v1_p++; s_v = tmp; } else if(state == 4){ state = 2; s_v = tmp; } } } if(state == 1) { u++; tmp_board[r+1] |= tmp; } else if(state == 3) { tmp_board[r+1] |= (s_v | (s_v << 1)); if((s_v & next_prev_row) || ((s_v << 1) & next_prev_row)) v2_p++; else v1_p++; } // if(print) // printf("%d %d %d %d %d - %X\n", v2, v2_p, v1, v1_p, u, // tmp_board[r+1]); } // if(print) printf("\n"); *vuln2 = v2 + v2_p; *vuln2_w_prot = v2_p; *vuln1 = v1 + v1_p; *vuln1_w_prot = v1_p; *unused = u; } //################################################################# // This function tries to pack as many 'option of vulnerability' areas // onto the board as it can. (no guarantee of optimality). //################################################################# static inline void pack_safe(u32bit tmp_board[32], s32bit player, s32bit *safe_op2, s32bit *safe_op1, s32bit *safe_op0) { u32bit guard, mask, curr, tmp; s32bit r; //row s32bit s2 = 0, s1 = 0, s0 = 0; for(r = 0; r < g_board_size[player]; r++){ guard = g_board[player][r] & g_board[player][r+2]; curr = g_board[player][r+1] | tmp_board[r+1]; // mask contains a bit for each safe move. mask = ( (~(curr | (curr >> 1))) & (guard & (guard >> 1)) ); while(mask){ tmp = (mask & -mask); // least sig bit of m mask &= ~(tmp | (tmp << 1)); // remove bit and next bit. // add these bits to current. curr |= (tmp | (tmp << 1)); if( ! ( (curr | tmp_board[r] | tmp_board[r+2]) & (tmp >> 1) ) ){ // we have an option to move vulnerably. (which option is it). curr |= (tmp >> 1); tmp_board[r+1] |= (tmp >> 1); // check up. if( (!(g_board[player][r] & (tmp >> 1))) && (g_board[player][r-1] & (tmp >> 1)) ){ // up is good now check down. if( (!(g_board[player][r+2] & (tmp >> 1))) && (g_board[player][r+3] & (tmp >> 1)) ){ s2++; } else { s1++; } } else if( (!(g_board[player][r+2] & (tmp >> 1))) && (g_board[player][r+3] & (tmp >> 1)) ){ s1++; } else { s0++; } } else if( ! ( (mask | curr | tmp_board[r] | tmp_board[r+2]) & (tmp << 2) ) ){ // we have an option to move vulnerably. (which option is it). curr |= (tmp << 2); tmp_board[r+1] |= (tmp << 2); // check up. if( (!(g_board[player][r] & (tmp << 2))) && (g_board[player][r-1] & (tmp << 2)) ){ // up is good now check down. if( (!(g_board[player][r+2] & (tmp << 2))) && (g_board[player][r+3] & (tmp << 2)) ){ s2++; } else { s1++; } } else if( (!(g_board[player][r+2] & (tmp << 2))) && (g_board[player][r+3] & (tmp << 2)) ){ s1++; } else { s0++; } } } // if(debug) printf("(%d,%d) ", s0, s1); } // if(debug) printf("\n"); *safe_op2 = s2; *safe_op1 = s1; *safe_op0 = s0; } //################################################################# // //################################################################# extern s32bit #ifdef PRINT_DOES_X_WIN_INFO does_next_player_win(s32bit next_player, s32bit print) #else does_next_player_win(s32bit next_player) #endif { // info we directly get from the board. s32bit prot; // This is the number of protective regions. s32bit vuln2; // Total number of vulnerable moves (includes vuln_w_prot). // Num of vuln moves which contain a square unavailable to the opponent. s32bit vuln2_w_prot; s32bit vuln1; // Total number of vulnerable moves (includes vuln_w_prot). // Num of vuln moves which contain a square unavailable to the opponent. s32bit vuln1_w_prot; s32bit safe; // Number of safe moves horizontal has. // Number of squares unused in our packing and unavailable for opponent. s32bit unused; s32bit empty; // Number of empty squares on board. s32bit safe_op2, safe_op1, safe_op0; //safe moves with options. // value we return and other variables. s32bit r_value = 0, i; // temporary board to store which positions have already been packed. u32bit tmp_board[32]; #ifdef NOTHING return -1; #endif //======================================================== // Initialize all of the values. //======================================================== for(i = 0; i < 32; i++) tmp_board[i] = 0; safe = g_info_totals[next_player].safe; empty = g_empty_squares; // Determine the number of protective regions that we have. #ifdef NO_PROT prot = 0; #else pack_prot(tmp_board, next_player, &prot); #endif // Determine the number of vuln, vuln_w_prot, and unused. pack_vuln(tmp_board, next_player, &vuln2, &vuln2_w_prot, &vuln1, &vuln1_w_prot, &unused); //, print); #ifdef NO_VULN_W_PROT vuln1_w_prot = vuln2_w_prot = 0; #endif #ifdef NO_VULN_TYPE_1 vuln2 += vuln1; vuln2_w_prot += vuln1_w_prot; vuln1 = vuln1_w_prot = 0; #endif #ifdef NO_UNUSED unused = 0; #endif #ifdef NO_VULN vuln2 = vuln1 = vuln2_w_prot = vuln1_w_prot = 0; #endif // Determine the number of safe moves with options we have. #ifdef NO_SAFE_OPT safe_op2 = safe_op1 = safe_op0 = 0; #else pack_safe(tmp_board, next_player, &safe_op2, &safe_op1, &safe_op0); #endif #ifdef PRINT_DOES_X_WIN_INFO if(print){ fprintf(stderr, "%d moves next, do they win?\n", next_player); fprintf(stderr, "prot %d, vuln2 %d(%d), vuln1 %d(%d), " "safe %d, unused %d, empty %d.\n", prot, vuln2, vuln2_w_prot, vuln1, vuln1_w_prot, safe, unused, empty); fprintf(stderr, "safe_op2 %d, safe_op1 %d, safe_op0 %d.\n", safe_op2, safe_op1, safe_op0); } #endif { s32bit moves, opp_moves, x = 0; if(prot % 2 == 1){ prot--; safe += 2; } else if(vuln2 % 3 != 0){ vuln2--; safe++; if(vuln2_w_prot > vuln2) vuln2_w_prot--; } else if(vuln1 % 2 != 0){ vuln1--; safe++; if(vuln1_w_prot > vuln1) vuln1_w_prot--; } else if(safe_op2 % 2 != 0){ safe_op2--; unused+=3; } else if(safe_op1 % 2 != 0){ safe_op1--; unused+=2; } else if(safe_op0 % 2 != 0){ safe_op0--; unused+=1; } else if(vuln2 > 0){ vuln2--; safe++; if(vuln2_w_prot > vuln2) vuln2_w_prot--; } else if(vuln1 > 0){ vuln1--; safe++; if(vuln1_w_prot > vuln1) vuln1_w_prot--; } else if(prot > 0){ prot--; safe += 2; } else { return -1; } if(prot % 2 == 1){ prot--; vuln2 += 2; } moves = (prot) + (vuln2/3) + (vuln1/2) + safe; if(vuln2 % 3 != 0 && vuln1 % 2 != 0){ moves++, unused--, x=1; // if(vuln2 > 0 || vuln1 > 0) unused--; } else if(vuln2 % 3 == 0 && vuln1 % 2 == 0) x=1; if(x == 1){ if(safe_op2%2 == 1) safe_op2--, safe_op1++; if(safe_op1%2 == 1) safe_op1--, safe_op0++; } else { if(safe_op2%2 == 1){ unused += 3; if(safe_op1%2==1) safe_op1--, safe_op0++; } else if(safe_op1%2 == 1) { unused += 2; } else if(safe_op0%2 == 1) { unused += 1; } } unused += vuln2_w_prot - ( (vuln2)/3 - (vuln2-vuln2_w_prot)/3 ); unused += vuln1_w_prot - ( (vuln1)/2 - (vuln1-vuln1_w_prot)/2 ); unused += (safe_op2/2) * 3; unused += (safe_op1/2) * 2; unused += (safe_op0/2) * 1; opp_moves = (empty - (moves*2) - unused)/2; //======================================================== // If r_value > 0 then next_player wins. //======================================================== r_value = moves - opp_moves; #ifdef PRINT_DOES_X_WIN_INFO if(print){ printf("moves:%d, opp:%d.\n", moves, opp_moves); if(moves - opp_moves >= 0) printf("H WINS\n"); } #endif } return r_value; } //################################################################# // //################################################################# extern s32bit #ifdef PRINT_DOES_X_WIN_INFO does_who_just_moved_win(s32bit who_just_moved, s32bit print) #else does_who_just_moved_win(s32bit who_just_moved) #endif { // info we directly get from the board. s32bit prot; // This is the number of protective regions. s32bit vuln2; // Total number of vulnerable moves (includes vuln_w_prot). // Num of vuln moves which contain a square unavailable to the opponent. s32bit vuln2_w_prot; s32bit vuln1; // Total number of vulnerable moves (includes vuln_w_prot). // Num of vuln moves which contain a square unavailable to the opponent. s32bit vuln1_w_prot; s32bit safe; // Number of safe moves horizontal has. // Number of squares unused in our packing and unavailable for opponent. s32bit unused; s32bit empty; // Number of empty squares on board. s32bit safe_op2, safe_op1, safe_op0; //safe moves with options. // value we return and other variables. s32bit r_value = 0, i; // temporary board to store which positions have already been packed. u32bit tmp_board[32]; #ifdef NOTHING return -1; #endif //======================================================== // Initialize all of the values. //======================================================== for(i = 0; i < 32; i++) tmp_board[i] = 0; safe = g_info_totals[who_just_moved].safe; empty = g_empty_squares; // Determine the number of protective regions that we have. #ifdef NO_PROT prot = 0; #else pack_prot(tmp_board, who_just_moved, &prot); #endif // Determine the number of vuln, vuln_w_prot, and unused. pack_vuln(tmp_board, who_just_moved, &vuln2, &vuln2_w_prot, &vuln1, &vuln1_w_prot, &unused); #ifdef NO_VULN_W_PROT vuln1_w_prot = vuln2_w_prot = 0; #endif #ifdef NO_VULN_TYPE_1 vuln2 += vuln1; vuln2_w_prot += vuln1_w_prot; vuln1 = vuln1_w_prot = 0; #endif #ifdef NO_UNUSED unused = 0; #endif #ifdef NO_VULN vuln2 = vuln1 = vuln2_w_prot = vuln1_w_prot = 0; #endif // Determine the number of safe moves with options we have. #ifdef NO_SAFE_OPT safe_op2 = safe_op1 = safe_op0 = 0; #else pack_safe(tmp_board, who_just_moved, &safe_op2, &safe_op1, &safe_op0); #endif /* if(prot % 2 == 1){ prot--; vuln2 += 2; } if(print == 1 && unused > 0 && prot >= 2 // && (vuln2%3 != 0 || vuln1%2 != 0) && vuln2 >= 3 && vuln1 >= 2 && safe_op1 + safe_op0 >= 2){ print_board(who_just_moved); } else { print = 0; } */ #ifdef PRINT_DOES_X_WIN_INFO if(print){ fprintf(stderr, "%d just moved, do they win?\n", who_just_moved); fprintf(stderr, "prot %d, vuln2 %d(%d), vuln1 %d(%d), " "safe %d, unused %d, empty %d.\n", prot, vuln2, vuln2_w_prot, vuln1, vuln1_w_prot, safe, unused, empty); fprintf(stderr, "safe_op2 %d, safe_op1 %d, safe_op0 %d.\n", safe_op2, safe_op1, safe_op0); } #endif { s32bit moves, opp_moves, x = 0; if(prot % 2 == 1){ prot--; vuln2 += 2; } moves = (prot) + (vuln2/3) + (vuln1/2) + safe; if(vuln2 % 3 != 0 && vuln1 % 2 != 0){ moves++, unused--, x=1; // if(vuln2 > 0 || vuln1 > 0) unused--; } else if(vuln2 % 3 == 0 && vuln1 % 2 == 0) x=1; if(x == 1){ if(safe_op2%2 == 1) safe_op2--, safe_op1++; if(safe_op1%2 == 1) safe_op1--, safe_op0++; } else { if(safe_op2%2 == 1){ unused += 3; if(safe_op1%2==1) safe_op1--, safe_op0++; } else if(safe_op1%2 == 1) { unused += 2; } else if(safe_op0%2 == 1) { unused += 1; } } unused += vuln2_w_prot - ( (vuln2)/3 - (vuln2-vuln2_w_prot)/3 ); unused += vuln1_w_prot - ( (vuln1)/2 - (vuln1-vuln1_w_prot)/2 ); unused += (safe_op2/2) * 3; unused += (safe_op1/2) * 2; unused += (safe_op0/2) * 1; opp_moves = (empty - (moves*2) - unused)/2; //======================================================== // If r_value >= 0 then who_just_moved wins. //======================================================== r_value = moves - opp_moves; #ifdef PRINT_DOES_X_WIN_INFO if(print){ printf("moves:%d, opp:%d.\n", moves, opp_moves); if(moves - opp_moves >= 0) printf("H WINS\n"); } #endif } return r_value; }