/* POTM ENTRY: fOrX */ /* Authors: Victor Udovenko & Igor Bely */ /* igor.bely@intel.com */ #include #include #include #define TABLE_SIZE 7 #define EMPTY 0 #define PLUS (1<<0) #define MINUS (1<<1) #define BUSY (1<<2) #define MIN_COUNT -50000 #define MAX_COUNT 50000 #define COUNT_BOUNDARY 60 #define SET_MINUS(cell) ((cell) |= MINUS) #define SET_PLUS(cell) ((cell) |= PLUS) #define SET_MOVE(cell, move) ((cell) |= (move)) #define SET_EMPTY(cell) ((cell) &= 0) #define IS_EMPTY(cell) (!(cell)) #define IS_PLUS(move) ((move) & PLUS) #define IS_MINUS(move) ((move) & MINUS) #define MOVE_REVERSE(move) ((move) ^ (PLUS | MINUS)) #define COUNT(bnum) (count_table[(bnum)].Count) #define COUNT_A(bnum) (count_table[(bnum)].CountX) #define COUNT_D(bnum) (count_table[(bnum)].CountO) #define COUNT_AD(bnum) (count_table[(bnum)].CountXO) #define COUNT_DA(bnum) (count_table[(bnum)].CountOX) #define MIN(a,b) ((a) < (b) ? (a) : (b)) #define MAX(a,b) ((a) > (b) ? (a) : (b)) typedef unsigned char uchar; typedef int Table[TABLE_SIZE][TABLE_SIZE]; typedef struct { int Count; int CountX; int CountO; int CountXO; int CountOX; } CountTable[256]; typedef struct { int countO; int countX; } CountOX; typedef struct { CountOX line_stcount; int bnumO; /* best from two */ int bnumX; /* best from two */ } Line; typedef struct { Table table; CountOX pos_stcount; Line Rows[TABLE_SIZE]; Line Cols[TABLE_SIZE]; } Position; typedef struct { int row; int col; int sort_count; CountOX full_count; CountOX move_stcount; CountOX move_dyncount; Line Col; Line Row; } Move; typedef struct { int cur_bnumO; int cur_bnumX; } LineData; typedef struct { int FirstX; int SecondX; int FirstO; int SecondO; } BestBnums; /* count_table.cpp */ CountTable count_table = { { 0, 0, 0, 0, 0}, /* */ { 0, 0, 0, 0, 0}, /* */ /*---------------------------------------------------------------*/ { 0, 0, 0, 0, 0}, /* - */ { 0, 0, 0, 0, 0}, /* X */ /*---------------------------------------------------------------*/ { 0, 0, 0, 0, 0}, /* -- */ { 0, 0, 0, 0, 0}, /* X- */ { 0, 0, 0, 0, 0}, /* -X */ { 0, 0, 0, 0, 0}, /* XX */ /*---------------------------------------------------------------*/ { 0, 10, -6, 0, 0}, /* --- */ { 6, 15, -6, -6, -6}, /* X-- */ { 10, 11, -10, -10, -10}, /* -X- */ { 21, 39, -21, 39, -21}, /* XX- */ { 6, 15, -6, -6, -6}, /* --X */ { 20, 40, -20, 40, -20}, /* X-X */ { 21, 39, -21, 39, -21}, /* -XX */ { 60, 0, 0, 0, 0}, /* XXX */ /*---------------------------------------------------------------*/ { 0, 23, -9, -6, 0}, /* ---- */ { 9, 28, -15, -9, -9}, /* X--- */ { 23, 26, -17, -2, -23}, /* -X-- */ { 23, 39, -23, 37, -23}, /* XX-- */ { 23, 26, -13, -2, -23}, /* --X- */ { 37, 25, -37, 23, -37}, /* X-X- */ { 49, 13, -28, 11, 11}, /* -XX- */ { 62, 138, -2, 138, -2}, /* XXX- */ { 9, 28, -9, -9, -9}, /* ---X */ { 17, 22, -17, -17, -17}, /* X--X */ { 37, 25, -37, 23, -37}, /* -X-X */ { 39, 161, -39, 161, -39}, /* XX-X */ { 23, 39, -23, 37, -23}, /* --XX */ { 39, 161, -39, 161, -39}, /* X-XX */ { 62, 138, -2, 138, -2}, /* -XXX */ { 200, 0, 0, 0, 0}, /* XXXX */ /*---------------------------------------------------------------*/ { 0, 53, -10, -9, -6}, /* ----- */ { 10, 57, -19, -16, -10}, /* X---- */ { 26, 28, -17, -3, -26}, /* -X--- */ { 26, 38, -32, 34, -26}, /* XX--- */ { 53, 14, -47, -30, -32}, /* --X-- */ { 67, 17, -61, -7, -46}, /* X-X-- */ { 52, 96, -29, 10, 8}, /* -XX-- */ { 64, 139, -4, 136, -4}, /* XXX-- */ { 26, 28, -26, 23, -26}, /* ---X- */ { 34, 32, -24, -13, -34}, /* X--X- */ { 54, 94, -54, 8, -54}, /* -X-X- */ { 56, 147, -56, 144, -56}, /* XX-X- */ { 52, 96, -3, 10, 8}, /* --XX- */ { 66, 137, -45, 134, -6}, /* X-XX- */ { 148, 55, -86, 52, 52}, /* -XXX- */ { 203, 297, -3, 297, -3}, /* XXXX- */ { 10, 57, -10, -10, -10}, /* ----X */ { 18, 66, -18, 2, -18}, /* X---X */ { 34, 32, -17, -13, -34}, /* -X--X */ { 34, 46, -34, 26, -34}, /* XX--X */ { 67, 17, -61, -47, -46}, /* --X-X */ { 84, -4, -64, -24, -24}, /* X-X-X */ { 66, 137, -45, 134, -6}, /* -XX-X */ { 80, 420, -20, 420, -20}, /* XXX-X */ { 26, 38, -32, 34, -26}, /* ---XX */ { 34, 46, -34, 26, -34}, /* X--XX */ { 56, 147, -56, 144, -56}, /* -X-XX */ { 58, 442, -58, 442, -58}, /* XX-XX */ { 64, 139, -4, 136, -4}, /* --XXX */ { 80, 420, -20, 420, -20}, /* X-XXX */ { 203, 297, -3, 297, -3}, /* -XXXX */ { 500, 0, 0, 0, 0}, /* XXXXX */ /*---------------------------------------------------------------*/ { 0, 56, -11, -10, 0}, /* ------ */ { 11, 59, -21, -20, -5}, /* X----- */ { 27, 57, -17, -1, -17}, /* -X---- */ { 27, 59, -36, 27, -17}, /* XX---- */ { 56, 28, -47, -30, -41}, /* --X--- */ { 70, 31, -61, -16, -33}, /* X-X--- */ { 55, 96, -29, 9, -1}, /* -XX--- */ { 67, 138, -13, 133, -7}, /* XXX--- */ { 56, 28, -43, -33, -41}, /* ---X-- */ { 64, 32, -58, -41, -43}, /* X--X-- */ { 84, 67, -78, -20, -63}, /* -X-X-- */ { 86, 119, -80, 114, -65}, /* XX-X-- */ { 82, 69, -59, -18, -20}, /* --XX-- */ { 96, 109, -73, 104, -34}, /* X-XX-- */ { 151, 208, -87, 52, 49}, /* -XXX-- */ { 205, 299, -5, 295, -5}, /* XXXX-- */ { 27, 57, -10, 12, -17}, /* ----X- */ { 35, 66, -35, 2, -14}, /* X---X- */ { 51, 32, -41, -30, -30}, /* -X--X- */ { 51, 46, -41, 9, -30}, /* XX--X- */ { 84, 67, -78, 64, -63}, /* --X-X- */ { 101, 64, -64, -39, -41}, /* X-X-X- */ { 83, 276, -62, 120, -23}, /* -XX-X- */ { 97, 407, -37, 403, -37}, /* XXX-X- */ { 55, 96, -16, 93, -1}, /* ---XX- */ { 63, 102, -14, -1, -3}, /* X--XX- */ { 83, 276, -62, 120, -23}, /* -X-XX- */ { 85, 419, -64, 415, -25}, /* XX-XX- */ { 151, 208, -3, 52, 49}, /* --XXX- */ { 165, 339, -103, 335, 35}, /* X-XXX- */ { 359, 145, -156, 141, 141}, /* -XXXX- */ { 504, 616, -4, 616, -4}, /* XXXXX- */ { 11, 59, -11, -11, -5}, /* -----X */ { 19, 59, -19, -19, 1}, /* X----X */ { 35, 66, -35, -1, -14}, /* -X---X */ { 35, 68, -35, 25, -14}, /* XX---X */ { 64, 32, -47, -30, -43}, /* --X--X */ { 78, 105, -61, -39, -39}, /* X-X--X */ { 63, 102, -29, -1, -3}, /* -XX--X */ { 75, 146, -15, 125, -15}, /* XXX--X */ { 70, 31, -61, 14, -33}, /* ---X-X */ { 78, 105, -61, -39, -39}, /* X--X-X */ { 101, 64, -17, -39, -41}, /* -X-X-X */ { 103, 118, -83, 97, -43}, /* XX-X-X */ { 96, 109, -73, -57, -34}, /* --XX-X */ { 183, 38, -144, 17, 17}, /* X-XX-X */ { 165, 339, -103, 335, 35}, /* -XXX-X */ { 221, 899, -21, 899, -21}, /* XXXX-X */ { 27, 59, -36, 27, -17}, /* ----XX */ { 35, 68, -35, -14, -14}, /* X---XX */ { 51, 46, -41, -30, -30}, /* -X--XX */ { 51, 48, -30, 9, 9}, /* XX--XX */ { 86, 119, -80, 114, -65}, /* --X-XX */ { 103, 118, -83, 97, -43}, /* X-X-XX */ { 85, 419, -64, 415, -25}, /* -XX-XX */ { 99, 1021, -39, 1021, -39}, /* XXX-XX */ { 67, 138, -13, 133, -7}, /* ---XXX */ { 75, 146, -15, 125, -15}, /* X--XXX */ { 97, 407, -37, 403, -37}, /* -X-XXX */ { 99, 1021, -39, 1021, -39}, /* XX-XXX */ { 205, 299, -5, 295, -5}, /* --XXXX */ { 221, 899, -21, 899, -21}, /* X-XXXX */ { 504, 616, -4, 616, -4}, /* -XXXXX */ {1120, 0, 0, 0, 0}, /* XXXXXX */ /*---------------------------------------------------------------*/ { 0, 59, -12, -11, -3}, /* ------- */ { 12, 59, -23, -22, -1}, /* X------ */ { 28, 59, -17, -1, -12}, /* -X----- */ { 28, 61, -38, 23, -5}, /* XX----- */ { 57, 57, -47, -30, -41}, /* --X---- */ { 71, 60, -61, -20, -32}, /* X-X---- */ { 56, 98, -29, 11, -5}, /* -XX---- */ { 68, 140, -17, 126, 2}, /* XXX---- */ { 59, 28, -56, -33, -28}, /* ---X--- */ { 67, 32, -58, -41, -34}, /* X--X--- */ { 87, 67, -78, -20, -50}, /* -X-X--- */ { 89, 119, -80, 105, -52}, /* XX-X--- */ { 85, 96, -59, -18, -29}, /* --XX--- */ { 99, 109, -73, 95, -35}, /* X-XX--- */ { 154, 208, -87, 51, 40}, /* -XXX--- */ { 208, 298, -14, 292, -8}, /* XXXX--- */ { 57, 57, -57, -40, -41}, /* ----X-- */ { 65, 66, -52, -42, -38}, /* X---X-- */ { 81, 32, -65, -58, -50}, /* -X--X-- */ { 81, 46, -58, -15, -32}, /* XX--X-- */ { 114, 67, -102, -50, -87}, /* --X-X-- */ { 131, 64, -64, -67, -65}, /* X-X-X-- */ { 113, 249, -86, 92, -47}, /* -XX-X-- */ { 127, 379, -61, 373, -46}, /* XXX-X-- */ { 85, 96, -68, -21, -29}, /* ---XX-- */ { 93, 102, -70, -29, -31}, /* X--XX-- */ { 113, 249, -90, 92, -51}, /* -X-XX-- */ { 115, 391, -92, 385, -53}, /* XX-XX-- */ { 181, 181, -117, 24, 22}, /* --XXX-- */ { 195, 311, -131, 305, 8}, /* X-XXX-- */ { 362, 432, -157, 142, 138}, /* -XXXX-- */ { 506, 619, -6, 614, -6}, /* XXXXX-- */ { 28, 59, -28, -2, -12}, /* -----X- */ { 36, 59, -19, -19, -6}, /* X----X- */ { 52, 91, -42, -35, -21}, /* -X---X- */ { 52, 93, -35, 18, -3}, /* XX---X- */ { 81, 32, -65, -47, -50}, /* --X--X- */ { 95, 105, -61, -39, -33}, /* X-X--X- */ { 80, 102, -29, -18, -18}, /* -XX--X- */ { 92, 146, -22, 108, -11}, /* XXX--X- */ { 87, 67, -78, 51, -50}, /* ---X-X- */ { 95, 105, -78, -39, -56}, /* X--X-X- */ { 143, 39, -106, -81, -81}, /* -X-X-X- */ { 145, 93, -108, 55, -83}, /* XX-X-X- */ { 113, 249, -90, 246, -51}, /* --XX-X- */ { 200, 176, -144, 3, 0}, /* X-XX-X- */ { 182, 612, -120, 322, 18}, /* -XXX-X- */ { 238, 887, -38, 882, -38}, /* XXXX-X- */ { 56, 98, -30, 82, -5}, /* ----XX- */ { 64, 98, -25, 84, -4}, /* X---XX- */ { 80, 102, -31, -18, -18}, /* -X--XX- */ { 80, 104, -31, -18, -18}, /* XX--XX- */ { 113, 249, -86, 246, -47}, /* --X-XX- */ { 130, 246, -89, 73, -49}, /* X-X-XX- */ { 112, 682, -70, 392, -31}, /* -XX-XX- */ { 126, 999, -45, 994, -6}, /* XXX-XX- */ { 154, 208, -16, 205, 40}, /* ---XXX- */ { 162, 214, -14, 41, 38}, /* X--XXX- */ { 182, 612, -120, 322, 18}, /* -X-XXX- */ { 184, 941, -122, 936, 16}, /* XX-XXX- */ { 362, 432, -3, 142, 138}, /* --XXXX- */ { 376, 749, -173, 744, 124}, /* X-XXXX- */ { 794, 331, -290, 326, 326}, /* -XXXXX- */ {1125, 1255, -5, 1255, -5}, /* XXXXXX- */ { 12, 59, -12, -12, -1}, /* ------X */ { 20, 59, -20, -2, 0}, /* X-----X */ { 36, 59, -17, -1, -6}, /* -X----X */ { 36, 61, -36, 24, 1}, /* XX----X */ { 65, 66, -59, -47, -38}, /* --X---X */ { 79, 69, -61, -19, -27}, /* X-X---X */ { 64, 98, -29, 11, -4}, /* -XX---X */ { 76, 140, -16, 124, 5}, /* XXX---X */ { 67, 32, -56, -33, -34}, /* ---X--X */ { 75, 32, -58, -41, -36}, /* X--X--X */ { 95, 105, -78, -20, -56}, /* -X-X--X */ { 97, 119, -80, 103, -58}, /* XX-X--X */ { 93, 102, -59, -18, -31}, /* --XX--X */ { 107, 287, -73, -27, -27}, /* X-XX--X */ { 162, 214, -87, 41, 38}, /* -XXX--X */ { 216, 306, -16, 284, -16}, /* XXXX--X */ { 71, 60, -61, -10, -32}, /* ----X-X */ { 79, 69, -18, -42, -27}, /* X---X-X */ { 95, 105, -58, 88, -33}, /* -X--X-X */ { 95, 107, -58, -56, -33}, /* XX--X-X */ { 131, 64, -47, -67, -65}, /* --X-X-X */ { 148, 246, -64, -68, -68}, /* X-X-X-X */ { 130, 246, -89, 73, -49}, /* -XX-X-X */ { 144, 378, -64, 356, -24}, /* XXX-X-X */ { 99, 109, -73, 84, -35}, /* ---XX-X */ { 107, 287, -73, -27, -27}, /* X--XX-X */ { 200, 176, -17, 3, 0}, /* -X-XX-X */ { 202, 320, -163, 298, -2}, /* XX-XX-X */ { 195, 311, -131, -115, 8}, /* --XXX-X */ { 394, 128, -314, 106, 106}, /* X-XXX-X */ { 376, 749, -173, 744, 124}, /* -XXXX-X */ { 522, 1858, -22, 1858, -22}, /* XXXXX-X */ { 28, 61, -38, 7, -5}, /* -----XX */ { 36, 61, -36, -19, 1}, /* X----XX */ { 52, 93, -17, -35, -3}, /* -X---XX */ { 52, 95, -35, -13, 10}, /* XX---XX */ { 81, 46, -30, -47, -32}, /* --X--XX */ { 95, 107, -61, -56, -33}, /* X-X--XX */ { 80, 104, -29, -18, -18}, /* -XX--XX */ { 92, 148, -11, 108, 28}, /* XXX--XX */ { 89, 119, -80, 105, -52}, /* ---X-XX */ { 97, 119, -80, -58, -58}, /* X--X-XX */ { 145, 93, -108, -106, -83}, /* -X-X-XX */ { 147, 93, -108, 53, 53}, /* XX-X-XX */ { 115, 391, -92, 385, -53}, /* --XX-XX */ { 202, 320, -163, 298, -2}, /* X-XX-XX */ { 184, 941, -122, 936, 16}, /* -XXX-XX */ { 240, 2140, -40, 2140, -40}, /* XXXX-XX */ { 68, 140, -17, 126, 2}, /* ----XXX */ { 76, 140, -16, 124, 5}, /* X---XXX */ { 92, 146, -22, 108, -11}, /* -X--XXX */ { 92, 148, -11, 108, 28}, /* XX--XXX */ { 127, 379, -61, 373, -46}, /* --X-XXX */ { 144, 378, -64, 356, -24}, /* X-X-XXX */ { 126, 999, -45, 994, -6}, /* -XX-XXX */ { 140, 2240, -20, 2240, -20}, /* XXX-XXX */ { 208, 298, -14, 292, -8}, /* ---XXXX */ { 216, 306, -16, 284, -16}, /* X--XXXX */ { 238, 887, -38, 882, -38}, /* -X-XXXX */ { 240, 2140, -40, 2140, -40}, /* XX-XXXX */ { 506, 619, -6, 614, -6}, /* --XXXXX */ { 522, 1858, -22, 1858, -22}, /* X-XXXXX */ {1125, 1255, -5, 1255, -5}, /* -XXXXXX */ {2380, 0, 0, 0, 0}, /* XXXXXXX */ }; /* count.cpp */ static void StatCount (Position *pos, Move *move); static void DynCount (Position *pos, Move *move, int cur_move); static void FindBest (Position *pos, BestBnums *bbnums, Move *move); static void ColData (Position *pos, Move *move); static void RowData (Position *pos, Move *move); static void eval_BUSY (Line *line, LineData *ld); static void eval_MINUS (Line *line, LineData *ld); static void eval_EMPTY (Line *line, LineData *ld); static void eval_PLUS (Line *line, LineData *ld); extern void MoveCount (Position *pos, Move *move, int cur_move); static int get_next_move (Position *pos, int *next_i, int *next_j); static int cmp_plus (const void *a, const void *b); static int cmp_minus (const void *a, const void *b); extern void PosInit (Position *pos); extern CountOX AlphaBeta (Position *pos, CountOX last_count, int cur_move, int deep, Move *r_move); static int GetPosition (Table table, FILE *in_file); static void PutPosition (Table table, int player, Move *move); typedef void (*FunEval) (Line *, LineData *); static FunEval FunEvalArray[5] = { eval_EMPTY, eval_PLUS, eval_MINUS, NULL, eval_BUSY, }; /*==========================================================================*/ void PosInit (Position *pos) /*==========================================================================*/ { int i; Move move; pos->pos_stcount.countO = 0; pos->pos_stcount.countX = 0; for (i=0; iCols[i] = move.Col; pos->Rows[i] = move.Row; pos->pos_stcount.countO += pos->Cols[i].line_stcount.countO + pos->Rows[i].line_stcount.countO; pos->pos_stcount.countX += pos->Cols[i].line_stcount.countX + pos->Rows[i].line_stcount.countX; } } /*==========================================================================*/ void MoveCount (Position *pos, Move *move, int cur_move) /*==========================================================================*/ { SET_MOVE(pos->table[move->row][move->col], cur_move); StatCount (pos, move); DynCount (pos, move, cur_move); SET_EMPTY(pos->table[move->row][move->col]); move->full_count.countO = move->move_stcount.countO + move->move_dyncount.countO; move->full_count.countX = move->move_stcount.countX + move->move_dyncount.countX; move->sort_count = move->full_count.countX - move->full_count.countO; move->move_stcount.countO += pos->pos_stcount.countO; move->move_stcount.countX += pos->pos_stcount.countX; move->full_count.countO += pos->pos_stcount.countO; move->full_count.countX += pos->pos_stcount.countX; } /*==========================================================================*/ static void DynCount (Position *pos, Move *move, int cur_move) /*==========================================================================*/ { BestBnums bbnums = {0, 0, 0, 0}; int countX, countO; int countOA, countOD, countXA, countXD; int countOAA, countOAD, countODA, countODD; int countXAA, countXAD, countXDA, countXDD; int FirstX, SecondX, FirstO, SecondO; FindBest (pos, &bbnums, move); if (IS_PLUS(cur_move)) /* Last move was X, now will be move O */ { FirstX = bbnums.FirstX; SecondX = bbnums.SecondX; FirstO = bbnums.FirstO; SecondO = bbnums.SecondO; } else { FirstX = bbnums.FirstO; SecondX = bbnums.SecondO; FirstO = bbnums.FirstX; SecondO = bbnums.SecondX; } /* main part - Attack:Attack, Attack:Defenc, ... */ /* Attack */ countXAA = COUNT_A(FirstX); countOAA = COUNT_A(FirstO); countXAD = 0; countOAD = MIN (COUNT_AD(FirstO), COUNT_A(FirstO) + COUNT_D(SecondO)); if ((countXAA - countOAA) >= (countXAD - countOAD)) { countXA = countXAA; countOA = countOAA; } else { countXA = countXAD; countOA = countOAD; } /* Defense */ countXDA = MAX (COUNT_DA(FirstX), COUNT_D(FirstX) + COUNT_A(SecondX)); countODA = 0; countXDD = COUNT_D(FirstX); countODD = COUNT_D(FirstO); if ((countXDA - countODA) >= (countXDD - countODD)) { countXD = countXDA; countOD = countODA; } else { countXD = countXDD; countOD = countODD; } /* Results */ if (countOA - countXA >= countOD - countXD) { countX = countXA; countO = countOA; } else { countX = countXD; countO = countOD; } if (IS_PLUS(cur_move)) /* Last move was X, now will be move O */ { move->move_dyncount.countX = countX; move->move_dyncount.countO = countO; } else { move->move_dyncount.countX = countO; move->move_dyncount.countO = countX; } } /*==========================================================================*/ static void StatCount (Position *pos, Move *move) /*==========================================================================*/ { int col = move->col; int row = move->row; ColData (pos, move); RowData (pos, move); move->move_stcount.countO = move->Col.line_stcount.countO + move->Row.line_stcount.countO - pos->Cols[col].line_stcount.countO - pos->Rows[row].line_stcount.countO; move->move_stcount.countX = move->Col.line_stcount.countX + move->Row.line_stcount.countX - pos->Cols[col].line_stcount.countX - pos->Rows[row].line_stcount.countX; } /*==========================================================================*/ static void FindBest (Position *pos, BestBnums *bbnums, Move *move) /*==========================================================================*/ { int i; int col_bnumO, row_bnumO, col_bnumX, row_bnumX; for (i=0; icol) {col_bnumO = pos->Cols[i].bnumO; col_bnumX = pos->Cols[i].bnumX;} else {col_bnumO = move->Col.bnumO; col_bnumX = move->Col.bnumX;} if (i != move->row) {row_bnumO = pos->Rows[i].bnumO; row_bnumX = pos->Rows[i].bnumX;} else {row_bnumO = move->Row.bnumO; row_bnumX = move->Row.bnumX;} if (COUNT_A(row_bnumO) > COUNT_A(bbnums->FirstO)) { bbnums->SecondO = bbnums->FirstO; bbnums->FirstO = row_bnumO; } else if (COUNT_A(row_bnumO) > COUNT_A(bbnums->SecondO)) bbnums->SecondO = row_bnumO; if (COUNT_A(col_bnumO) > COUNT_A(bbnums->FirstO)) { bbnums->SecondO = bbnums->FirstO; bbnums->FirstO = col_bnumO; } else if (COUNT_A(col_bnumO) > COUNT_A(bbnums->SecondO)) bbnums->SecondO = col_bnumO; if (COUNT_A(row_bnumX) > COUNT_A(bbnums->FirstX)) { bbnums->SecondX = bbnums->FirstX; bbnums->FirstX = row_bnumX; } else if (COUNT_A(row_bnumX) > COUNT_A(bbnums->SecondX)) bbnums->SecondX = row_bnumX; if (COUNT_A(col_bnumX) > COUNT_A(bbnums->FirstX)) { bbnums->SecondX = bbnums->FirstX; bbnums->FirstX = col_bnumX; } else if (COUNT_A(col_bnumX) > COUNT_A(bbnums->SecondX)) bbnums->SecondX = col_bnumX; } } /*==========================================================================*/ static void ColData (Position *pos, Move *move) /*==========================================================================*/ { static LineData ld = { 1, 1 }; int i; move->Col.bnumO = 0; move->Col.bnumX = 0; move->Col.line_stcount.countO = 0; move->Col.line_stcount.countX = 0; for (i=0; itable[i][move->col]] (&move->Col, &ld); eval_BUSY (&move->Col, &ld); } /*==========================================================================*/ static void RowData (Position *pos, Move *move) /*==========================================================================*/ { static LineData ld = { 1, 1 }; int i; move->Row.bnumO = 0; move->Row.bnumX = 0; move->Row.line_stcount.countO = 0; move->Row.line_stcount.countX = 0; for (i=0; itable[move->row][i]] (&move->Row, &ld); eval_BUSY (&move->Row, &ld); } /*==========================================================================*/ static void eval_BUSY (Line *line, LineData *ld) /*==========================================================================*/ { line->line_stcount.countO += COUNT(ld->cur_bnumO); line->line_stcount.countX += COUNT(ld->cur_bnumX); if (COUNT(ld->cur_bnumO) > COUNT(line->bnumO)) line->bnumO = ld->cur_bnumO; if (COUNT(ld->cur_bnumX) > COUNT(line->bnumX)) line->bnumX = ld->cur_bnumX; ld->cur_bnumO = ld->cur_bnumX = 1; } /*==========================================================================*/ static void eval_MINUS (Line *line, LineData *ld) /*==========================================================================*/ { ld->cur_bnumO <<= 1; ld->cur_bnumO |= 1; line->line_stcount.countX += COUNT(ld->cur_bnumX); if (COUNT(ld->cur_bnumX) > COUNT(line->bnumX)) line->bnumX = ld->cur_bnumX; ld->cur_bnumX = 1; } /*==========================================================================*/ static void eval_EMPTY (Line *line, LineData *ld) /*==========================================================================*/ { ld->cur_bnumO <<= 1; ld->cur_bnumX <<= 1; } /*==========================================================================*/ static void eval_PLUS (Line *line, LineData *ld) /*==========================================================================*/ { ld->cur_bnumX <<= 1; ld->cur_bnumX |= 1; line->line_stcount.countO += COUNT(ld->cur_bnumO); if (COUNT(ld->cur_bnumO) > COUNT(line->bnumO)) line->bnumO = ld->cur_bnumO; ld->cur_bnumO = 1; } /* AlphaBeta.cpp */ /*==========================================================================*/ CountOX AlphaBeta (Position *pos, CountOX last_count, int cur_move, int deep, Move *r_move) /*==========================================================================*/ { CountOX cur_count; CountOX tmp_count; int cur_fcount, tmp_fcount; int last_fcount = last_count.countX - last_count.countO; int next_i, next_j; Move move_array [TABLE_SIZE*TABLE_SIZE - 1]; Move *move_array_ptr [TABLE_SIZE*TABLE_SIZE - 1]; int move_num = TABLE_SIZE*TABLE_SIZE - 1; Line mem_col, mem_row; CountOX mem_stcount; int fst_count, lst_count; int i; int move_out; if (IS_PLUS (cur_move)) { cur_count.countO = MAX_COUNT; cur_count.countX = MIN_COUNT; } else { cur_count.countO = MIN_COUNT; cur_count.countX = MAX_COUNT; } cur_fcount = cur_count.countX - cur_count.countO; next_i = 0; next_j = -1; if (deep > 1) { for (move_num=0; get_next_move (pos, &next_i, &next_j); move_num++) { move_array[move_num].row = next_i; move_array[move_num].col = next_j; MoveCount (pos, &move_array[move_num], cur_move); move_array_ptr[move_num] = &move_array[move_num]; } if (IS_PLUS (cur_move)) /* PLUS */ { qsort (move_array_ptr, move_num, sizeof(Move *), cmp_plus); } else /* MINUS */ { qsort (move_array_ptr, move_num, sizeof(Move *), cmp_minus); fst_count = move_array_ptr[0]->sort_count; lst_count = move_array_ptr[move_num-1]->sort_count; } } for (i=0; irow; next_j = move_array_ptr[i]->col; } MoveCount (pos, &move_array[i], cur_move); tmp_count = move_array[i].full_count; tmp_fcount = tmp_count.countX - tmp_count.countO; } else { next_i = move_array_ptr[i]->row; next_j = move_array_ptr[i]->col; mem_row = pos->Rows[next_i]; mem_col = pos->Cols[next_j]; mem_stcount = pos->pos_stcount; pos->Rows[next_i] = move_array_ptr[i]->Row; pos->Cols[next_j] = move_array_ptr[i]->Col; pos->pos_stcount = move_array_ptr[i]->move_stcount; SET_MOVE (pos->table[next_i][next_j], cur_move); tmp_count = AlphaBeta (pos, cur_count, MOVE_REVERSE(cur_move), deep - 1, NULL); tmp_fcount = tmp_count.countX - tmp_count.countO; SET_EMPTY (pos->table[next_i][next_j]); pos->Rows[next_i] = mem_row; pos->Cols[next_j] = mem_col; pos->pos_stcount = mem_stcount; } if (IS_PLUS (cur_move)) /* PLUS */ { if ( (tmp_fcount > cur_fcount) || ((tmp_fcount == cur_fcount) && (tmp_count.countX > cur_count.countX)) ) { cur_fcount = tmp_fcount; cur_count = tmp_count; if (r_move != NULL) { r_move->row = next_i; r_move->col = next_j; move_out = i; } else /* don't leave root */ if ( (cur_fcount > last_fcount) || /* Alpha cutting */ ((cur_fcount == last_fcount) && (cur_count.countO <= last_count.countO)) ) break; } } else /* MINUS */ { if ( (tmp_fcount < cur_fcount) || ((tmp_fcount == cur_fcount) && (tmp_count.countO > cur_count.countO)) ) { cur_fcount = tmp_fcount; cur_count = tmp_count; if (r_move != NULL) { r_move->row = next_i; r_move->col = next_j; move_out = i; } else /* don't leave root */ if ( (cur_fcount < last_fcount) || /* Beta cutting */ ((cur_fcount == last_fcount) && (cur_count.countX <= last_count.countX)) ) break; } } } return cur_count; } /*==========================================================================*/ static int get_next_move (Position *pos, int *next_i, int *next_j) /*==========================================================================*/ { int i,j; j=*next_j + 1; for (i=*next_i; itable[i][j])) { *next_i = i; *next_j = j; return 1; } j = 0; } return 0; } /*==========================================================================*/ static int cmp_plus (const void *a, const void *b) /*==========================================================================*/ { Move *aa = *(Move **) a; Move *bb = *(Move **) b; if (aa->sort_count > bb->sort_count) return -1; if (aa->sort_count < bb->sort_count) return 1; return 0; } /*==========================================================================*/ static int cmp_minus (const void *a, const void *b) /*==========================================================================*/ { Move *aa = *(Move **) a; Move *bb = *(Move **) b; if (aa->sort_count < bb->sort_count) return -1; if (aa->sort_count > bb->sort_count) return 1; return 0; } /* main.cpp */ static int movesLeft = 0; static int GetDepth(int mleft) { return (mleft > 12) ? 6 : 12; } /*==========================================================================*/ int main (int argc, char *argv[]) /*==========================================================================*/ { Move move; CountOX count; int player; Position pos; FILE *in_file; if (argc > 1) { in_file = fopen (argv[1], "rt"); if (in_file == NULL) exit (1); } else in_file = stdin; player = GetPosition (pos.table, in_file); PosInit (&pos); if (IS_PLUS (player)) { count.countO = MIN_COUNT; count.countX = MAX_COUNT; } else { count.countO = MAX_COUNT; count.countX = MIN_COUNT; } count = AlphaBeta (&pos, count, player, GetDepth(movesLeft), &move); PutPosition (pos.table, player, &move); return 0; } /*==========================================================================*/ static int GetPosition (Table table, FILE *in_file) /*==========================================================================*/ { int player = 0; int c; int i, j; for (i=0; irow][move->col] = player; for (i=0; i