diff options
Diffstat (limited to 'include/minimax_cnn1986.c')
| -rw-r--r-- | include/minimax_cnn1986.c | 120 |
1 files changed, 62 insertions, 58 deletions
diff --git a/include/minimax_cnn1986.c b/include/minimax_cnn1986.c index e89e5a6..38edb33 100644 --- a/include/minimax_cnn1986.c +++ b/include/minimax_cnn1986.c @@ -36,7 +36,7 @@ static union u_f fudge; #define RELU(x) ((x) = ((x)<0)?0:(x)) float -ct1986_evaluate_black_win(void) { +ct1986_evaluate_win(void) { /* ------------------ * * Convolution layer * * ------------------ */ @@ -114,10 +114,16 @@ ct1986_evaluate_black_win(void) { DOXORSHIFT; output += fudge.f; #endif - if (output > 1.0) return 1.0; - else if (output < 0.0) return 0.0; + if (output > 1.0) { + if (ply & 1) return 1.0; + else return -1.0; + } + else if (output < 0.0) { + if (ply & 1) return -1.0; + else return 1.0; + } - return output; + return (ply & 1) ? 2.0*output-1.0 : 1.0-2*output; } // =================================================================== @@ -138,41 +144,41 @@ previous_ply(void) { static float val; static enum WIN_TYPE w; -#define WIN_EVALUATE_OR_RECURSE(store) { \ +#define WIN_EVALUATE_OR_RECURSE(store,reset) { \ w = 0xFF; \ if (ply >= 2*5 - 2) w = check_win(); \ if (w < 0xFF) { \ - /* Somebody won, assign weights accordingly */ \ - if (min == 0) { \ - if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) \ - val = infty; \ - else val = -infty; \ - } else { \ + /* Somebody won, assign weights accordingly. Note in particular + that draws are only worth ∞/2 ;) \ + */ \ + if (ply & 1) { \ if (w == WIN_ROAD_WHITE || w == WIN_FLAT_WHITE) \ val = -infty; \ + else if (w == WIN_DRAW) val = infty/2.0; \ + else val = infty; \ + } else { \ + if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) \ + val = -infty; \ + else if (w == WIN_DRAW) val = infty/2.0; \ else val = infty; \ } \ } else if (cur_depth == max_depth) { \ /* We're at the bottom, evaluate */ \ - val = ct1986_evaluate_black_win(); \ - if ((ply & 1) == 0) val = val - 1.0; \ + val = ct1986_evaluate_win(); \ } else { \ /* We're not at the bottom, recurse first */ \ next_ply(); \ - val = ct1986_minimax(cur_depth + 1, max_depth, 1-min, alpha, beta); \ + val = -ct1986_negamax(cur_depth + 1, max_depth, -beta, -alpha); \ previous_ply(); \ } \ - /* Update the optimal value */ \ - if (((min > 0) && (val <= optimal)) \ - || ((min == 0) && (val >= optimal))) { \ + { reset }; \ + /* Prune */ \ + if (val >= beta) return val; \ + /* Update the optimal value, which alpha carries */ \ + if (val > optimal) { \ optimal = val; \ - if (cur_depth == 0) (store); \ - } \ - /* Update alpha and beta */ \ - if (min) { \ - if (optimal < beta) beta = optimal; \ - } else { \ - if (optimal > alpha) alpha = optimal; \ + if (val > alpha) alpha = val; \ + if (cur_depth == 0) { store }; \ } \ } @@ -180,16 +186,15 @@ static enum WIN_TYPE w; static const int8_t deltas[4] = { +5, -5, -1, +1}; float -ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth, - const uint8_t min, float alpha, float beta) { +ct1986_negamax(const uint8_t cur_depth, const uint8_t max_depth, + float alpha, float beta) { const uint8_t black = (ply & 1), material = (black) ? black_count : white_count, flat = material & 127, cap = (ply > 2 && (material & 128)), standing = (ply > 2 && (material & 127)); - // 1.0 is a `certain' black win, -1.0 is a `certain' white win. - float optimal = (min) ? infty : -infty; + float optimal = -infty; // Step across the board for (uint8_t row = 0; row < 5; row++) { @@ -297,21 +302,21 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth, // If we did update the optimal value, store // this move generate_move(loc, dir, steps, drops, ct1986_ptn); + },{ + // Reset the board data after recursing or + // before returning + if (dir <= M_DOWN) { + for (uint8_t y = 0; y < 5; y++) { + colours[THE_COORDS(col, y)] = colours_backup[y]; + celldat[THE_COORDS(col, y)] = celldat_backup[y]; + } + } else { + for (uint8_t x = 0; x < 5; x++) { + colours[THE_COORDS(x, row)] = colours_backup[x]; + celldat[THE_COORDS(x, row)] = celldat_backup[x]; + } + } }); - // Reset the board data - if (dir <= M_DOWN) { - for (uint8_t y = 0; y < 5; y++) { - colours[THE_COORDS(col, y)] = colours_backup[y]; - celldat[THE_COORDS(col, y)] = celldat_backup[y]; - } - } else { - for (uint8_t x = 0; x < 5; x++) { - colours[THE_COORDS(x, row)] = colours_backup[x]; - celldat[THE_COORDS(x, row)] = celldat_backup[x]; - } - } - // Prune - if (alpha >= beta) return optimal; } /* * With thanks to @@ -337,13 +342,12 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth, WIN_EVALUATE_OR_RECURSE({ // If we did update the optimal value, store generate_place(loc, STONE_FLAT, ct1986_ptn); + },{ + // Reset the state + celldat[loc] = 0; + if (black) black_count++; + else white_count++; }); - // Reset the state - celldat[loc] = 0; - if (black) black_count++; - else white_count++; - // Prune - if (alpha >= beta) return optimal; // Do the same for walls, can't happen without flats if (standing) { @@ -353,11 +357,11 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth, celldat[loc] = NUM_INC | STONE_STANDING; WIN_EVALUATE_OR_RECURSE({ generate_place(loc, STONE_STANDING, ct1986_ptn); + },{ + celldat[loc] = 0; + if (black) black_count++; + else white_count++; }); - celldat[loc] = 0; - if (black) black_count++; - else white_count++; - if (alpha >= beta) return optimal; } } @@ -369,20 +373,20 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth, celldat[loc] = NUM_INC | STONE_CAPSTONE; WIN_EVALUATE_OR_RECURSE({ generate_place(loc, STONE_CAPSTONE, ct1986_ptn); + },{ + celldat[loc] = 0; + if (black) black_count |= 128; + else white_count |= 128; }); - celldat[loc] = 0; - if (black) black_count |= 128; - else white_count |= 128; - if (alpha >= beta) return optimal; } } ct1986_display_progress(cur_depth); } } - return optimal; + return alpha; } inline float ct1986_generate(const uint8_t max_depth) { - return ct1986_minimax(0, 1+2*max_depth, (ply & 1) ? 0 : 1, -infty, infty); + return ct1986_negamax(0, max_depth, -infty, infty); } |