diff options
| -rw-r--r-- | include/actions.c | 130 | ||||
| -rw-r--r-- | include/actions.h | 24 | ||||
| -rw-r--r-- | include/negamax.c | 29 | ||||
| -rw-r--r-- | include/tt_llcht.c | 11 | ||||
| -rw-r--r-- | include/tt_llcht.h | 5 |
5 files changed, 93 insertions, 106 deletions
diff --git a/include/actions.c b/include/actions.c index 4f226e1..c926e52 100644 --- a/include/actions.c +++ b/include/actions.c @@ -26,14 +26,14 @@ #define CLR_STONE NUM_MASK static inline void -list_append(action_list_t *list, const enum A_TYPE type, - const int8_t loc, const uint8_t data0, - const uint8_t data1); +lq_append(action_lq_t *lq, const enum A_TYPE type, + const int8_t loc, const uint8_t data0, + const uint8_t data1); static inline void -list_prepend(action_list_t *list, const enum A_TYPE type, - const int8_t loc, const uint8_t data0, - const uint8_t data1); +lq_prepend(action_lq_t *lq, const enum A_TYPE type, + const int8_t loc, const uint8_t data0, + const uint8_t data1); static inline void inline_next_ply(void); @@ -45,42 +45,50 @@ inline_prev_ply(void); // Exported method implementations // =================================================================== -int action_move_to_front(const action_t action, - action_list_t *list) { - action_node_t *n = list->head; - - // TODO: what if it's not in the list? - - while (n) { - if (n->action == action) { - const action_t t = list->head->action; - list->head->action = action; - n->action = t; +int action_move_to_front(const action_t action, action_lq_t *lq) { + for (int k=lq->i_f; k<lq->i_b; k++) { + if (lq->actions[k] == action) { + for (int j=k; j>lq->i_f; j--) { + lq->actions[j] = lq->actions[j-1]; + } + lq->actions[lq->i_f] = action; return EXIT_SUCCESS; } - n = n->next; } - return EXIT_FAILURE; } +action_lq_t *action_lq_copy_with_mtf(action_lq_t *lq, action_t front) { + // Normalise, empty list ---> null + if (lq == NULL || lq->length == 0) return NULL; + action_lq_t *copy = malloc(sizeof(action_lq_t)); + + copy->length = lq->length; + copy->i_b = lq->i_b; + copy->i_f = lq->i_f; -void action_list_free(action_list_t *list) { - if (list) { - action_node_t *n = list->head, *nn; - while (n) { - nn = n->next; - free(n); - n = nn; + for (int source=lq->i_f, dest=copy->i_f+1; + source < lq->i_b; source++, dest++) { + if (lq->actions[source] == front) { + source++; + if (source >= lq->i_b) break; } - free(list); + copy->actions[dest] = lq->actions[source]; } + + copy->actions[copy->i_f] = front; + + return copy; +} + +void action_lq_free(action_lq_t *lq) { + free(lq); } // Keep track of move offsets int8_t move_deltas[4]; -void action_list_init(void) { +void action_lq_init(void) { move_deltas[0] = +board_size; move_deltas[1] = -board_size; move_deltas[2] = -1; @@ -89,12 +97,13 @@ void action_list_init(void) { // We bias place over move by prepending place actions and appending // move actions to the generated list -action_list_t *action_list_generate(void) { - action_list_t *list = malloc(sizeof(struct action_list_s)); +action_lq_t *action_lq_generate(void) { + action_lq_t *lq = malloc(sizeof(action_lq_t)); // TODO: trap errno - list->length = 0; - list->head = NULL; + lq->length = 0; + lq->i_f = ACTION_AR_LEN; + lq->i_b = ACTION_AR_LEN; /* * The check for whether it's a black piece to be played is actually @@ -183,9 +192,9 @@ action_list_t *action_list_generate(void) { (steps == end_stops[dir]) && crushes[dir]; // Store the move - list_append(list, A_MOVE, loc, - (crush << 7) | gaps, - (dir<<4) | num); + lq_append(lq, A_MOVE, loc, + (crush << 7) | gaps, + (dir<<4) | num); } /* * With thanks to @@ -205,16 +214,16 @@ action_list_t *action_list_generate(void) { else if (material) { // Empty square, generate placements if (flat) { - list_prepend(list, A_PLACE, loc, STONE_FLAT, 0); + lq_prepend(lq, A_PLACE, loc, STONE_FLAT, 0); if (standing) - list_prepend(list, A_PLACE, loc, STONE_STANDING,0); + lq_prepend(lq, A_PLACE, loc, STONE_STANDING,0); } if (cap) - list_prepend(list, A_PLACE, loc, STONE_CAPSTONE, 0); + lq_prepend(lq, A_PLACE, loc, STONE_CAPSTONE, 0); } } } - return list; + return lq; } void action_take(const action_t action) { @@ -383,42 +392,19 @@ void action_to_ptn(const action_t action, char* out_ptn) { // =================================================================== static inline void -list_append(action_list_t *list, const enum A_TYPE type, - const int8_t loc, const uint8_t data0, - const uint8_t data1) { - action_node_t *new = malloc(sizeof(action_node_t)); - // TODO: trap errno - - new->next = NULL; - new->action = A_BUILD(type, loc, data0, data1); - - if (list->length) { - list->tail->next = new; - list->tail = new; - } else { - list->head = new; - list->tail = new; - } - - list->length++; +lq_append(action_lq_t *lq, const enum A_TYPE type, + const int8_t loc, const uint8_t data0, + const uint8_t data1) { + lq->actions[lq->i_b++] = A_BUILD(type, loc, data0, data1); + lq->length++; } static inline void -list_prepend(action_list_t *list, const enum A_TYPE type, - const int8_t loc, const uint8_t data0, - const uint8_t data1) { - action_node_t *new = malloc(sizeof(action_list_t)); - // TODO: trap errno - - new->next = list->head; - list->head = new; - new->action = A_BUILD(type, loc, data0, data1); - - if (list->length == 0) { - list->tail = new; - } - - list->length++; +lq_prepend(action_lq_t *lq, const enum A_TYPE type, + const int8_t loc, const uint8_t data0, + const uint8_t data1) { + lq->actions[--lq->i_f] = A_BUILD(type, loc, data0, data1); + lq->length++; } static inline void diff --git a/include/actions.h b/include/actions.h index 75c881e..54b9077 100644 --- a/include/actions.h +++ b/include/actions.h @@ -44,15 +44,12 @@ typedef uint32_t action_t; | (data0) << A_DATA0_SHIFT \ | (data1) << A_DATA1_SHIFT) -typedef struct action_node_s { - struct action_node_s *next; - action_t action; -} action_node_t; - -typedef struct action_list_s { - struct action_node_s *head, *tail; - uint32_t length; -} action_list_t; +// lazy queue +#define ACTION_AR_LEN 256 +typedef struct action_lq_s { + action_t actions[ACTION_AR_LEN*2]; + int length, i_f, i_b; +} action_lq_t; // =================================================================== // Variables @@ -64,11 +61,12 @@ extern int8_t move_deltas[4]; // Methods // =================================================================== -void action_list_init(void); -void action_list_free(action_list_t *list); -action_list_t *action_list_generate(void); +void action_lq_init(void); +void action_lq_free(action_lq_t *lq); +action_lq_t *action_lq_generate(void); +action_lq_t *action_lq_copy_with_mtf(action_lq_t *lq, action_t front); -int action_move_to_front(const action_t action, action_list_t *list); +int action_move_to_front(const action_t action, action_lq_t *lq); void action_take(const action_t action); void action_undo(const action_t action); diff --git a/include/negamax.c b/include/negamax.c index 30aed05..8c06c5f 100644 --- a/include/negamax.c +++ b/include/negamax.c @@ -40,7 +40,7 @@ static float negamax(const uint8_t cur_depth, const uint8_t init_depth, void negamax_init(const uint8_t new_board_size) { board_size = new_board_size; - action_list_init(); + action_lq_init(); zobrist_init(); tt_init(); } @@ -82,10 +82,11 @@ static float negamax(const uint8_t cur_depth, const uint8_t init_depth, float alpha, float beta, const float colour, const uint64_t hash) { + action_lq_t *lq = NULL; tt_entry_t *entry = tt_seek(hash); - // CAUTION: ≥ breaks search stability (vs =) on shallow depths if (entry != NULL && entry->depth >= cur_depth) { + // CAUTION: ≥ breaks search stability (vs =) on shallow depths if (entry->flag == TT_EXACT) { return entry->value; } else if (entry->flag == TT_LOWERBOUND && entry->value > alpha) { @@ -95,27 +96,27 @@ static float negamax(const uint8_t cur_depth, const uint8_t init_depth, } if (alpha >= beta) return entry->value; } + // lq = action_lq_copy_with_mtf(entry->lq, entry->best); - action_list_t *list; - if ((list = action_list_generate()) == NULL) + if ((lq = action_lq_generate()) == NULL) return alpha; // should never happen! if (entry != NULL) { - action_move_to_front(entry->action, list); + action_move_to_front(entry->best, lq); } if (init_depth > 1 && cur_depth == init_depth) { - action_move_to_front(negamax_best_action, list); + action_move_to_front(negamax_best_action, lq); } // TODO: what to do if this is never written to? - action_t best_action = list->head->action; + action_t best_action = lq->actions[lq->i_f]; float best_value = -infty; - for (action_node_t *node=list->head; node!=NULL; node=node->next) { - negamax_display_progress(cur_depth, init_depth, list->length); + for (int k=lq->i_f; k<lq->i_b; k++) { + negamax_display_progress(cur_depth, init_depth, lq->length); - action_take(node->action); + action_take(lq->actions[k]); // Compute the value of the node float node_value; @@ -135,18 +136,18 @@ static float negamax(const uint8_t cur_depth, const uint8_t init_depth, } else { node_value = colour * cnn1986_evaluate_black_win(); } - action_undo(node->action); + action_undo(lq->actions[k]); if (node_value > best_value) { best_value = node_value; - best_action = node->action; + best_action = lq->actions[k]; } if (best_value > alpha) alpha = best_value; if (alpha >= beta) break; } - action_list_free(list); + action_lq_free(lq); if (cur_depth == init_depth) negamax_best_action = best_action; flag = TT_EXACT; @@ -157,9 +158,9 @@ static float negamax(const uint8_t cur_depth, const uint8_t init_depth, tt_insert(hash, flag, cur_depth, best_value, best_action); } else { entry->flag = flag; + entry->best = best_action; entry->value = best_value; entry->depth = cur_depth; - entry->action = best_action; } return best_value; diff --git a/include/tt_llcht.c b/include/tt_llcht.c index 60f8ccc..51ebad9 100644 --- a/include/tt_llcht.c +++ b/include/tt_llcht.c @@ -29,7 +29,7 @@ static tt_entry_t *table[TT_LLCHT_SIZE+1]; tt_entry_t * new_ll_node(const uint64_t key, const enum TT_FLAG flag, const uint8_t depth, const float value, - const action_t action); + const action_t best); // =================================================================== @@ -63,8 +63,9 @@ tt_entry_t *tt_seek(const uint64_t key) { int tt_insert(const uint64_t key, const enum TT_FLAG flag, const uint8_t depth, const float value, - const action_t action) { - tt_entry_t *new = new_ll_node(key, flag, depth, value, action), *n; + const action_t best) { + tt_entry_t *n, + *new = new_ll_node(key, flag, depth, value, best); // TODO: trap const uint32_t idx = key & TT_LLCHT_SIZE; @@ -84,14 +85,14 @@ int tt_insert(const uint64_t key, const enum TT_FLAG flag, tt_entry_t * new_ll_node(const uint64_t key, const enum TT_FLAG flag, const uint8_t depth, const float value, - const action_t action) { + const action_t best) { tt_entry_t *new = malloc(sizeof(struct tt_node_s)); // TODO: trap errno new->key = key; + new->best = best; new->next = NULL; new->flag = flag; new->depth = depth; new->value = value; - new->action = action; return new; } diff --git a/include/tt_llcht.h b/include/tt_llcht.h index 377de10..c1151a0 100644 --- a/include/tt_llcht.h +++ b/include/tt_llcht.h @@ -35,7 +35,8 @@ typedef struct tt_node_s { enum TT_FLAG flag; uint8_t depth; float value; - action_t action; + action_t best; + // action_lq_t *lq; } tt_entry_t; // =================================================================== @@ -55,6 +56,6 @@ tt_entry_t *tt_seek(const uint64_t key); int tt_insert(const uint64_t key, const enum TT_FLAG flag, const uint8_t depth, const float value, - const action_t action); + const action_t best); #endif |