diff options
| -rw-r--r-- | include/action_list.c | 4 | ||||
| -rw-r--r-- | include/negamax.c | 39 |
2 files changed, 29 insertions, 14 deletions
diff --git a/include/action_list.c b/include/action_list.c index 50eb266..66435dc 100644 --- a/include/action_list.c +++ b/include/action_list.c @@ -42,8 +42,8 @@ action_list_t *action_list_generate(void) { standing = (ply >= 2 && (material & 127)); // Step across the board - for (uint8_t row = 0; row < board_size; row++) { - for (uint8_t col = 0; col < board_size; col++) { + for (int8_t row = board_size - 1; row > 0; row--) { + for (int8_t col = board_size - 1; col > 0; col--) { // We'll need these at various points: the location of this // square and the maximum number of stones we could pick up const int8_t loc = THE_COORDS(col, row); diff --git a/include/negamax.c b/include/negamax.c index 757a648..16eba9a 100644 --- a/include/negamax.c +++ b/include/negamax.c @@ -108,39 +108,54 @@ negamax_generate(void) { return result; } +static enum WIN_TYPE w; static float negamax(const uint8_t cur_depth, float alpha, float beta, const float colour) { float value = -infty; - action_list_t *action_list = action_list_generate(); - action_list_t *action = action_list; + action_list_t *list = action_list_generate(); - while (action != NULL) { + for (action_list_t *node=list; node!=NULL; node=node->next) { negamax_display_progress(cur_depth); - action_take(action); - if (cur_depth > 1) { + action_take(node); + + // Somebody won? + if (ply >= 2*board_size - 3 && (w = check_win()) < 0xFF) { + if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) { + value = colour*infty; + if (value > 0) { + // Always take the win for ourselves + action_undo(node); + if (cur_depth == negamax_search_depth) + action_to_ptn(node, negamax_ptn); + goto prune; + } + } else if (w == WIN_DRAW) value = 0; // Draw is fixed at neutral + else value = -colour*infty; + } else if (cur_depth > 1) { + // Recurse away from the leaves value = fmax(value, -negamax(cur_depth - 1, -beta, -alpha, -colour)); } else { - value = fmax(value, colour*cnn1986_evaluate_black_win()); + // Evaluate a leaf + value = fmax(value, colour * cnn1986_evaluate_black_win()); } - action_undo(action); - // alpha = fmax(alpha, value); + action_undo(node); + if (value > alpha) { alpha = value; if (cur_depth == negamax_search_depth) - action_to_ptn(action, negamax_ptn); + action_to_ptn(node, negamax_ptn); } if (alpha >= beta) break; - - action = action->next; } - action_list_free(action_list); + action_list_free(list); + prune: return value; } |