From eab1d81df4455eb89b2663dcdd45a024f4633a2e Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Thu, 21 Jan 2021 14:56:55 -0500 Subject: Finally (?) fixed winning avoidance --- Makefile | 2 +- include/negamax_cnn1986.c | 68 ++++++++++++++++++++++++++++++++++++++--------- include/tak.c | 4 +-- include/tak.h | 2 +- 4 files changed, 60 insertions(+), 16 deletions(-) diff --git a/Makefile b/Makefile index c480e2f..530e339 100644 --- a/Makefile +++ b/Makefile @@ -1,6 +1,6 @@ IDIR=include DEFINES=-DDETERMINISTIC -CFLAGS=-O3 -Wall -Wextra -std=c99 -D_DEFAULT_SOURCE $(DEFINES) -I$(IDIR) +CFLAGS=-O3 -Wall -Wextra -Wpedantic -std=c99 -D_DEFAULT_SOURCE $(DEFINES) -I$(IDIR) LIBS= SRCS=$(wildcard include/*.c) $(wildcard 3rd-party/*.c) diff --git a/include/negamax_cnn1986.c b/include/negamax_cnn1986.c index 1a6d41a..3aa282f 100644 --- a/include/negamax_cnn1986.c +++ b/include/negamax_cnn1986.c @@ -156,16 +156,20 @@ static const int8_t deltas[4] = { +5, -5, -1, +1}; #define WIN_EVALUATE_OR_RECURSE(store,reset) { \ w = 0xFF; \ - if (ply >= 2*5 - 2) w = check_win(); \ + if (ply >= 2*5 - 3) w = check_win(); \ if (w < 0xFF) { \ - /* Somebody won, assign weights accordingly. Note in particular - that draws are only worth ∞/2 ;) - */ \ - if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) \ - val = infty; \ - else if (w == WIN_DRAW) val = infty/2.0; \ - else val = -infty; \ - val *= colour; \ + /* Somebody won, assign weights accordingly. */ \ + if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) { \ + val = colour*infty; \ + /* Always take the win */ \ + if (cur_depth == 0 && val > 0) { \ + { reset }; \ + { store }; \ + return infty; \ + } \ + /* Fix draw value to be completely neutral */ \ + } else if (w == WIN_DRAW) val = 0; \ + else val = -colour*infty; \ } else if (cur_depth == negamax_cnn1986_search_depth) { \ /* We're at the bottom, evaluate */ \ val = colour * cnn1986_evaluate_black_win(); \ @@ -263,7 +267,8 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta, for (uint8_t steps = 1; steps <= end_stops[dir][0] && steps <= num; steps++) { - gaps = 0b00000111 >> (4-steps); + gaps = 0x07 >> (4-steps); // 0b0000[0111] because 4-1=3 + // and 5-1=4 do { // Ensure legal move if we have to crush const uint8_t last_drop_check = (num > 1) ? (gaps & 1<<(num - 2)) : 1; @@ -336,6 +341,43 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta, else white_count--; colours[loc] = current_colour; celldat[loc] = NUM_INC | STONE_FLAT; + /* + * w = 0xFF; + * if (ply >= 2*5 - 3) w = check_win(); + * if (w < 0xFF) { + * /\* Somebody won, assign weights accordingly. Note in particular + * that draws are only worth ∞/2 ;) + * *\/ + * if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) + * val = infty; + * else if (w == WIN_DRAW) val = 0; + * else val = -infty; + * val *= colour; + * } else if (cur_depth == negamax_cnn1986_search_depth) { + * /\* We're at the bottom, evaluate *\/ + * val = colour * cnn1986_evaluate_black_win(); + * } else { + * /\* We're not at the bottom, recurse first *\/ + * next_ply(); + * val = -negamax_cnn1986(cur_depth + 1, -beta, -alpha, -colour); + * previous_ply(); + * } + * celldat[loc] = 0; + * if (black) black_count++; + * else white_count++; + * /\* Prune *\/ + * if (val >= beta) return beta; + * /\* Update the optimal value, which alpha carries *\/ + * if (val > alpha) { + * alpha = val; + * if (cur_depth == 0) { + * generate_place(loc, STONE_FLAT, negamax_cnn1986_ptn); + * /\* Did we win? *\/ + * if (alpha >= infty && w < 0xFF) + * return alpha; + * }; + * } + */ WIN_EVALUATE_OR_RECURSE({ // If we did update the optimal value, store generate_place(loc, STONE_FLAT, negamax_cnn1986_ptn); @@ -345,7 +387,6 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta, if (black) black_count++; else white_count++; }); - // Do the same for walls, can't happen without flats if (standing) { if (black) black_count--; @@ -385,5 +426,8 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta, inline float negamax_cnn1986_generate(void) { - return negamax_cnn1986(0, -infty, infty, (ply&1)?1.0:-1.0); + // We need to start with something outside of [-∞,∞] because those + // values are wins + const float safe_infty = infty + 1; + return negamax_cnn1986(0, -safe_infty, safe_infty, (ply&1)?1.0:-1.0); } diff --git a/include/tak.c b/include/tak.c index e400578..964225e 100644 --- a/include/tak.c +++ b/include/tak.c @@ -15,8 +15,8 @@ uint8_t white_count, black_count, ply; // Helpers // =================================================================== -#define DFS_MASK 0b00001100 -#define NOT_DFS_MASK 0b11110011 +#define DFS_MASK 0x0C // 0b00001100 +#define NOT_DFS_MASK 0xF3 // 0b11110011 #define NUM_SQUARES (board_size * board_size) diff --git a/include/tak.h b/include/tak.h index 1d49720..135e4eb 100644 --- a/include/tak.h +++ b/include/tak.h @@ -22,7 +22,7 @@ typedef uint16_t colour_stack_t; #define NUM_SHIFT 4 #define NUM_MASK (0xF<> NUM_SHIFT) #define THE_COORDS(col,row) ((col)+(row)*board_size) -- cgit v1.2.3