From a77062ce3dc9a99ad0662010cc7eeb00dd5036a6 Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Thu, 28 Jan 2021 21:30:30 -0500 Subject: Added license information! --- include/actions.c | 41 +++++++++++++++++++++++++++++++++------- include/actions.h | 30 +++++++++++++++++++++++++++++ include/cnn1986.c | 17 +++++++++++++++++ include/cnn1986.h | 17 +++++++++++++++++ include/lcdlib.c | 17 +++++++++++++++++ include/lcdlib.h | 28 +++++++++++++++++++++++++-- include/negamax.c | 53 ++++++++++++++++++++++++++++++++++------------------ include/negamax.h | 48 ++++++++++++++++++++++++++++++++++------------- include/tak.c | 17 +++++++++++++++++ include/tak.h | 35 +++++++++++++++++++++++++++++++--- include/tt_llcht.c | 31 ++++++++++++++++++++++-------- include/tt_llcht.h | 19 ++++++++++++++++++- include/weights.c | 17 +++++++++++++++++ include/weights.h | 17 +++++++++++++++++ include/xorshift64.c | 17 +++++++++++++++++ include/xorshift64.h | 19 ++++++++++++++++++- include/zobrist.c | 35 ++++++++++++++++++++++------------ include/zobrist.h | 26 ++++++++++++++++++++------ 18 files changed, 413 insertions(+), 71 deletions(-) (limited to 'include') diff --git a/include/actions.c b/include/actions.c index 5085330..800a2d4 100644 --- a/include/actions.c +++ b/include/actions.c @@ -1,3 +1,20 @@ +/* + This file is part of ctak. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with Takwrap. If not, see . +*/ + #include "actions.h" // =================================================================== @@ -67,6 +84,7 @@ void action_list_init(void) { action_list_t *action_list_generate(void) { action_list_t *list = malloc(sizeof(struct action_list_s)); + // TODO: trap errno list->length = 0; list->head = NULL; @@ -129,16 +147,22 @@ action_list_t *action_list_generate(void) { * For each direction, generate all possible ordered integer * partitions of 1 ≤ num ≤ count whose number of summands is * exactly 1 ≤ summands ≤ min(end_stops[dir], num) -- we - * write summands as steps + * write summands as steps. + * + * We exploit the `gaps' bijection here and elsewhere + * between ordered {integer partitions of n with s summands} + * and {binary strings of length n-1 with s-1 set bits}. */ for (enum MOVE_DIRECTION dir=M_UP; dir<=M_RIGHT; dir++) { for (uint8_t num = 1; num <= count; num++) { for (uint8_t steps = 1; steps <= end_stops[dir] && steps <= num; steps++) { - // TODO: Generalise to board_size! - uint8_t gaps = 0x07 >> (board_size-steps-1); - // 0b0000[0111] because 4-1=3 and 5-1=4 + uint8_t gaps = + ((1<<(board_size - 2)) - 1) >> (board_size-steps-1); + // For 5x5 this givess 0b0000[0XXX] where steps-1 of + // those X's are 1s (starting with LSB) because 4-1=3 + // and 5-1=4 do { /* * We skip the partition if it calls for multiple @@ -214,9 +238,12 @@ void action_take(const action_t action) { } } } else { - // not interested in whether we crushed, it will work out by - // anyway because we overwrite the top stone type. See (*) later - // for when we do need to know. + /* + * See the discussion around line 135 for an explanation of the + * encoding. Here we are not interested in whether we crushed, it + * will work out by anyway because we overwrite the top stone + * type. See (*) later for when we do need to know. + */ const uint8_t gaps = A_GET_DATA0(action) & 0x7F, num = A_GET_DATA1(action) & 0x0F, // unpack dir = A_GET_DATA1(action) >> 4; diff --git a/include/actions.h b/include/actions.h index ced0315..a1c90cc 100644 --- a/include/actions.h +++ b/include/actions.h @@ -1,3 +1,20 @@ +/* + This file is part of ctak. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with Takwrap. If not, see . +*/ + #ifndef ACTIONS_H #define ACTIONS_H @@ -6,6 +23,10 @@ #include +// =================================================================== +// Types +// =================================================================== + enum A_TYPE { A_PLACE, A_MOVE }; typedef uint32_t action_t; @@ -33,11 +54,20 @@ typedef struct action_list_s { uint32_t length; } action_list_t; +// =================================================================== +// Variables +// =================================================================== + 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); + int action_move_to_front(const action_t action, action_list_t *list); void action_take(const action_t action); diff --git a/include/cnn1986.c b/include/cnn1986.c index ada1766..d4f6ad6 100644 --- a/include/cnn1986.c +++ b/include/cnn1986.c @@ -1,3 +1,20 @@ +/* + This file is part of ctak. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with Takwrap. If not, see . +*/ + #include "cnn1986.h" #include "weights.h" diff --git a/include/cnn1986.h b/include/cnn1986.h index c04a04e..fe3817a 100644 --- a/include/cnn1986.h +++ b/include/cnn1986.h @@ -1,3 +1,20 @@ +/* + This file is part of ctak. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with Takwrap. If not, see . +*/ + #include float cnn1986_evaluate_black_win(void); diff --git a/include/lcdlib.c b/include/lcdlib.c index 0933b2c..c956d5c 100644 --- a/include/lcdlib.c +++ b/include/lcdlib.c @@ -1,3 +1,20 @@ +/* + This file is part of ctak. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with Takwrap. If not, see . +*/ + #include "lcdlib.h" static char previous_lines[LCD_HEIGHT][LCD_WIDTH+1]; diff --git a/include/lcdlib.h b/include/lcdlib.h index fd28a0e..192b3a4 100644 --- a/include/lcdlib.h +++ b/include/lcdlib.h @@ -1,19 +1,43 @@ +/* + This file is part of ctak. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with Takwrap. If not, see . +*/ + #include #include #include #include +// =================================================================== +// Types +// =================================================================== + #define LCD_WIDTH 16 #define LCD_HEIGHT 2 enum LCD_WRITE_MODE { L_OVERWRITE, L_SCROLL }; +// =================================================================== +// Methods +// =================================================================== + int lcd_begin(void); void lcd_end(void); void lcd_clear(void); -void lcd_put_line(const enum LCD_WRITE_MODE mode, - const char *line); +void lcd_put_line(const enum LCD_WRITE_MODE mode, const char *line); void lcd_printf_line(const enum LCD_WRITE_MODE mode, const char *format, ...); diff --git a/include/negamax.c b/include/negamax.c index 3db5867..cdcfcf9 100644 --- a/include/negamax.c +++ b/include/negamax.c @@ -1,7 +1,24 @@ +/* + This file is part of ctak. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with Takwrap. If not, see . +*/ + #include "negamax.h" // =================================================================== -// Globals +// Variables // =================================================================== const float infty = 3.0; @@ -9,52 +26,52 @@ char negamax_ptn[9]; uint8_t negamax_search_depth = 3; // =================================================================== -// Helpers +// Helper declarations // =================================================================== -static float -negamax(const uint8_t cur_depth, float alpha, float beta, +static float negamax(const uint8_t cur_depth, float alpha, float beta, const float colour); // =================================================================== -// α-β negamax using the cnn1986 evaluation function and transposition -// tables using Zobrist hasing and a treap +// Exported functions // =================================================================== -void -negamax_init(const uint8_t new_board_size) { +void negamax_init(const uint8_t new_board_size) { board_size = new_board_size; action_list_init(); zobrist_init(); tt_init(); } -void -negamax_free(void) { +void negamax_free(void) { zobrist_free(); } -float -negamax_generate(void) { +float negamax_generate(void) { // We need to start with something outside of [-∞,∞] because those // values are wins const float safe_infty = infty + 1; tt_init(); - float result = negamax(negamax_search_depth, - -safe_infty, safe_infty, - (ply & 1) ? +1.0 : -1.0); + float result = + negamax(negamax_search_depth, + -safe_infty, safe_infty, + (ply & 1) ? +1.0 : -1.0); tt_free(); return result; } +// =================================================================== +// α-β negamax using the cnn1986 evaluation function and transposition +// tables using Zobrist hasing and a chaining hash table +// =================================================================== + static enum TT_FLAG flag; static enum WIN_TYPE w; -static float -negamax(const uint8_t cur_depth, float alpha, float beta, - const float colour) { +static float negamax(const uint8_t cur_depth, float alpha, float beta, + const float colour) { uint64_t hash = zobrist_compute(); tt_entry_t *entry = tt_seek(hash); diff --git a/include/negamax.h b/include/negamax.h index b41871e..77461b8 100644 --- a/include/negamax.h +++ b/include/negamax.h @@ -1,30 +1,52 @@ +/* + This file is part of ctak. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with Takwrap. If not, see . +*/ + #include #include #include - #include #include #include -#include #include +// =================================================================== +// Variables +// =================================================================== + extern const float infty; extern char negamax_ptn[9]; extern uint8_t negamax_search_depth; -extern inline void -negamax_display_progress(const uint8_t, const uint32_t length); +extern void negamax_display_progress(const uint8_t cur_depth, + const uint32_t length); + +// =================================================================== +// Methods +// =================================================================== -void -negamax_init(const uint8_t new_board_size); +void negamax_init(const uint8_t new_board_size); -void -negamax_free(void); +void negamax_free(void); -// Do negamax to depth negamax_search_depth and return PTN of best move -// in negamax_ptn, along with its value as the return. The -// negamax_display_progress function is called on every new square at -// the top level. +/* + * Do α-β negamax with transposition tables and naïve move ordering to + * depth `negamax_search_depth' and store the PTN of best move in + * `negamax_ptn', and return its value. The `negamax_display_progress' + * function is called on every new square at the top level. + */ float negamax_generate(void); -extern uint8_t yes; diff --git a/include/tak.c b/include/tak.c index 6d07ea0..c9c761c 100644 --- a/include/tak.c +++ b/include/tak.c @@ -1,3 +1,20 @@ +/* + This file is part of ctak. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with Takwrap. If not, see . +*/ + #include "tak.h" // =================================================================== diff --git a/include/tak.h b/include/tak.h index 135e4eb..8b40430 100644 --- a/include/tak.h +++ b/include/tak.h @@ -1,14 +1,32 @@ +/* + This file is part of ctak. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with Takwrap. If not, see . +*/ + #ifndef TAK_H #define TAK_H #include +// =================================================================== +// Types +// =================================================================== + enum E_RESULT {ACT_OK, ACT_ILLEGAL, ACT_OVERFLOW, PTN_VALID, PTN_INVALID, GAME_END }; -// ------------------------------------------------------------------- -// State management - enum COLOUR { C_WHITE, C_BLACK }; enum STONE_VARIANT { STONE_FLAT, STONE_STANDING, STONE_CAPSTONE }; enum MOVE_DIRECTION { M_UP, M_DOWN, M_LEFT, M_RIGHT }; @@ -27,6 +45,10 @@ typedef uint16_t colour_stack_t; #define COUNT_AT(l) (celldat[(l)] >> NUM_SHIFT) #define THE_COORDS(col,row) ((col)+(row)*board_size) +// =================================================================== +// Variables +// =================================================================== + extern enum WIN_TYPE won; extern uint8_t board_size; extern data_t celldat[36]; @@ -34,6 +56,13 @@ extern colour_stack_t colours[36]; extern enum COLOUR current_colour; extern uint8_t white_count, black_count, ply; +// =================================================================== +// Methods +// =================================================================== + +// ------------------------------------------------------------------- +// Game state + void reset_state(const uint8_t new_board_size); void next_ply(void); diff --git a/include/tt_llcht.c b/include/tt_llcht.c index 9cbf647..b898b23 100644 --- a/include/tt_llcht.c +++ b/include/tt_llcht.c @@ -1,3 +1,20 @@ +/* + This file is part of ctak. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with Takwrap. If not, see . +*/ + #include "tt_llcht.h" // =================================================================== @@ -11,10 +28,9 @@ static tt_entry_t *table[TT_LLCHT_SIZE+1]; // Helper declarations // =================================================================== -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); +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); // =================================================================== @@ -69,10 +85,9 @@ int tt_insert(const uint64_t key, const enum TT_FLAG flag, // Helper function implementations // =================================================================== -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) { +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) { tt_entry_t *new = malloc(sizeof(struct tt_node_s)); // TODO: trap errno new->key = key; diff --git a/include/tt_llcht.h b/include/tt_llcht.h index f9a7a78..90b4164 100644 --- a/include/tt_llcht.h +++ b/include/tt_llcht.h @@ -1,3 +1,20 @@ +/* + This file is part of ctak. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with Takwrap. If not, see . +*/ + #ifndef TT_LLCHT_H #define TT_LLCHT_H @@ -22,7 +39,7 @@ typedef struct tt_node_s { } tt_entry_t; // =================================================================== -// Globals +// Variables // =================================================================== #define TT_LLCHT_SIZE ((uint32_t)((1<<19) - 1)) diff --git a/include/weights.c b/include/weights.c index 905eb41..812a2eb 100644 --- a/include/weights.c +++ b/include/weights.c @@ -1,3 +1,20 @@ +/* + This file is part of ctak. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with Takwrap. If not, see . +*/ + #include "weights.h" const float conv2d_weights[KERN_NUM][KERN_SIZE][KERN_SIZE][KERN_CHAN] = diff --git a/include/weights.h b/include/weights.h index dd479e3..d6666e7 100644 --- a/include/weights.h +++ b/include/weights.h @@ -1,3 +1,20 @@ +/* + This file is part of ctak. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with Takwrap. If not, see . +*/ + #define KERN_SIZE 3 #define KERN_CHAN 6 #define KERN_NUM 12 diff --git a/include/xorshift64.c b/include/xorshift64.c index 516218a..fd2fb6e 100644 --- a/include/xorshift64.c +++ b/include/xorshift64.c @@ -1,3 +1,20 @@ +/* + This file is part of ctak. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with Takwrap. If not, see . +*/ + #include "xorshift64.h" uint64_t xors = (uint64_t)0xBF58476D1CE4E5B9; diff --git a/include/xorshift64.h b/include/xorshift64.h index 62a0a4e..4509772 100644 --- a/include/xorshift64.h +++ b/include/xorshift64.h @@ -1,8 +1,25 @@ -#include +/* + This file is part of ctak. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with Takwrap. If not, see . +*/ #ifndef XORSHIFT_H #define XORSHIFT_H +#include + extern uint64_t xors; #define XORSHIFT64 { \ diff --git a/include/zobrist.c b/include/zobrist.c index feff5fa..21a99af 100644 --- a/include/zobrist.c +++ b/include/zobrist.c @@ -1,25 +1,38 @@ -#include "zobrist.h" +/* + This file is part of ctak. -// =================================================================== -// Globals -// =================================================================== + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. -static uint64_t *zobrist; + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with Takwrap. If not, see . +*/ + +#include "zobrist.h" // =================================================================== -// Helpers +// Variables // =================================================================== +static uint64_t *zobrist; // =================================================================== // Exported method implementations // =================================================================== -int -zobrist_init(void) { +int zobrist_init(void) { if (zobrist != NULL) return EXIT_FAILURE; zobrist = malloc(sizeof(uint64_t)*board_size*board_size*(15*2*3)); + // TODO: trap errno + for (int k=0; k. +*/ + #include #include #include -void -zobrist_free(void); +void zobrist_free(void); -int -zobrist_init(void); +int zobrist_init(void); -uint64_t -zobrist_compute(void); +uint64_t zobrist_compute(void); -- cgit v1.2.3