diff options
| -rw-r--r-- | Makefile | 7 | ||||
| -rw-r--r-- | include/actions.c | 722 | ||||
| -rw-r--r-- | include/actions.h | 38 | ||||
| -rw-r--r-- | include/cnn1986.c | 208 | ||||
| -rw-r--r-- | include/cnn1986.h | 22 | ||||
| -rw-r--r-- | include/lcdlib.c | 110 | ||||
| -rw-r--r-- | include/lcdlib.h | 24 | ||||
| -rw-r--r-- | include/negamax.h | 26 | ||||
| -rw-r--r-- | include/tak.c | 944 | ||||
| -rw-r--r-- | include/tak.h | 101 | ||||
| -rw-r--r-- | include/tps.c | 386 | ||||
| -rw-r--r-- | include/tt_llcht.c | 108 | ||||
| -rw-r--r-- | include/tt_llcht.h | 38 | ||||
| -rw-r--r-- | include/weights.h | 22 | ||||
| -rw-r--r-- | include/xorshift64.c | 22 | ||||
| -rw-r--r-- | include/xorshift64.h | 32 | ||||
| -rw-r--r-- | include/zobrist.c | 64 | ||||
| -rw-r--r-- | include/zobrist.h | 22 | ||||
| -rw-r--r-- | src/ct1986.c | 394 | ||||
| -rw-r--r-- | src/ctlm.c | 889 | ||||
| -rw-r--r-- | src/cttei.c | 242 | ||||
| -rw-r--r-- | src/geminict.c | 346 | ||||
| -rw-r--r-- | src/pptdb.c | 406 |
23 files changed, 2771 insertions, 2402 deletions
@@ -16,6 +16,9 @@ CROSS_STRIP=$(BUILDROOT_DIR)/output/host/bin/arm-linux-strip %.o: %.c $(CC) -c $< -o $@ $(CFLAGS) +geminict: src/geminict.o $(OBJS) + $(CC) $(CFLAGS) src/geminict.o $(OBJS) -o geminict + ctlm: src/ctlm.o $(OBJS) $(CC) $(CFLAGS) src/ctlm.o $(OBJS) -o ctlm @@ -26,10 +29,10 @@ pptdb: src/pptdb.o $(CTAK_OBJS) $(CC) $(CFLAGS) src/pptdb.o $(CTAK_OBJS) -o pptdb clean: - rm -f ctlm ct1986 cttei pptdb + rm -f ctlm ct1986 cttei pptdb geminict rm -f src/*.o include/*.o -native: clean ctlm cttei +native: clean ctlm cttei geminict $(CROSS_CC): ./resources/do_buildroot.sh $(BUILDROOT_DIR) diff --git a/include/actions.c b/include/actions.c index 4f226e1..795c135 100644 --- a/include/actions.c +++ b/include/actions.c @@ -1,18 +1,18 @@ /* - This file is part of ct. + This file is part of ct. - 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 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. + 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 ct. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with ct. If not, see <https://www.gnu.org/licenses/>. */ #include "actions.h" @@ -27,13 +27,13 @@ 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); + 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); + const int8_t loc, const uint8_t data0, + const uint8_t data1); static inline void inline_next_ply(void); @@ -46,336 +46,336 @@ inline_prev_ply(void); // =================================================================== 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; - return EXIT_SUCCESS; - } - n = n->next; - } - - return EXIT_FAILURE; + 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; + return EXIT_SUCCESS; + } + n = n->next; + } + + return EXIT_FAILURE; } 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; - } - free(list); - } + if (list) { + action_node_t *n = list->head, *nn; + while (n) { + nn = n->next; + free(n); + n = nn; + } + free(list); + } } // Keep track of move offsets int8_t move_deltas[4]; void action_list_init(void) { - move_deltas[0] = +board_size; - move_deltas[1] = -board_size; - move_deltas[2] = -1; - move_deltas[3] = +1; + move_deltas[0] = +board_size; + move_deltas[1] = -board_size; + move_deltas[2] = -1; + move_deltas[3] = +1; } // 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)); - - // TODO: trap errno - list->length = 0; - list->head = NULL; - - /* - * The check for whether it's a black piece to be played is actually - * black = (ply < 2) ? (ply==1) : (ply & 1), - * but material will always be sufficient in ply < 2 so we might as - * well save on the conditional. - */ - - const uint8_t material = (ply & 1) ? black_count : white_count, - flat = material & 0x7F, - cap = ((ply >= 2) && (material & 0x80)), - standing = ((ply >= 2) && flat); - - // Step across the board - for (int row = 0; row < board_size; row++) { - for (int col = 0; col < board_size; col++) { - // We'll need these at various points: the location of this - // square and the maximum number of stones we could pick up - const int loc = THE_COORDS(col, row); - const uint8_t count = DANGER_MIN(COUNT_AT(loc), board_size); - - // Only try moves after CPS and if the colour is correct - if (count) { - if (ply >= 2 && ((colours[loc] & 1) == current_colour)) { - - // Pre-compute end-stops and crushes - uint8_t end_stops[4], crushes[4] = {0, 0, 0, 0}; - - // These are upper bounds, not counting walls and such. - // UP DOWN LEFT RIGHT - end_stops[0] = DANGER_MIN(board_size - row - 1, count); - end_stops[1] = DANGER_MIN(row, count); - end_stops[2] = DANGER_MIN(col, count); - end_stops[3] = DANGER_MIN(board_size - col - 1, count); - - // Now we check for caps and walls - const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE; - for (int d = 0; d < 4; d++){ - const int delta = move_deltas[d]; - const int stop = end_stops[d]; - end_stops[d] = 0; - for (int k = 1; k <= stop; k++) { - const enum STONE_VARIANT stone = STONE_AT(loc+k*delta); - if (stone == STONE_STANDING) { - if (cap_top) { - crushes[d] = 0xFF; - end_stops[d]++; - } - break; - } else if (stone == STONE_CAPSTONE) { - break; - } - end_stops[d]++; - } - } - /* - * 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. - * - * 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++) { - 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 - * stones at the end with a crush. - */ - const uint8_t last_drop_check = - (num > 1) ? (gaps & (1 << (num - 2))) : 1; - if (crushes[dir] == 0 || last_drop_check) { - // We have to record a crush! - const uint8_t crush = - (steps == end_stops[dir]) && crushes[dir]; - // Store the move - - list_append(list, A_MOVE, loc, - (crush << 7) | gaps, - (dir<<4) | num); - } - /* - * With thanks to - * https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation - * we have the following magic to generate the next - * permutation of steps-many set bits - */ - uint8_t t = (gaps | (gaps - 1)); - gaps = (t + 1) - | (((~t & -~t) - 1) >> (__builtin_ctz(gaps) + 1)); - } while (gaps && (gaps + 1 <= (1 << (num - 1)))); - } - } - } - } - } // end of if (count) { ... } - else if (material) { - // Empty square, generate placements - if (flat) { - list_prepend(list, A_PLACE, loc, STONE_FLAT, 0); - if (standing) - list_prepend(list, A_PLACE, loc, STONE_STANDING,0); - } - if (cap) - list_prepend(list, A_PLACE, loc, STONE_CAPSTONE, 0); - } + action_list_t *list = malloc(sizeof(struct action_list_s)); + + // TODO: trap errno + list->length = 0; + list->head = NULL; + + /* + * The check for whether it's a black piece to be played is actually + * black = (ply < 2) ? (ply==1) : (ply & 1), + * but material will always be sufficient in ply < 2 so we might as + * well save on the conditional. + */ + + const uint8_t material = (ply & 1) ? black_count : white_count, + flat = material & 0x7F, + cap = ((ply >= 2) && (material & 0x80)), + standing = ((ply >= 2) && flat); + + // Step across the board + for (int row = 0; row < board_size; row++) { + for (int col = 0; col < board_size; col++) { + // We'll need these at various points: the location of this + // square and the maximum number of stones we could pick up + const int loc = THE_COORDS(col, row); + const uint8_t count = DANGER_MIN(COUNT_AT(loc), board_size); + + // Only try moves after CPS and if the colour is correct + if (count) { + if (ply >= 2 && ((colours[loc] & 1) == current_colour)) { + + // Pre-compute end-stops and crushes + uint8_t end_stops[4], crushes[4] = {0, 0, 0, 0}; + + // These are upper bounds, not counting walls and such. + // UP DOWN LEFT RIGHT + end_stops[0] = DANGER_MIN(board_size - row - 1, count); + end_stops[1] = DANGER_MIN(row, count); + end_stops[2] = DANGER_MIN(col, count); + end_stops[3] = DANGER_MIN(board_size - col - 1, count); + + // Now we check for caps and walls + const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE; + for (int d = 0; d < 4; d++){ + const int delta = move_deltas[d]; + const int stop = end_stops[d]; + end_stops[d] = 0; + for (int k = 1; k <= stop; k++) { + const enum STONE_VARIANT stone = STONE_AT(loc+k*delta); + if (stone == STONE_STANDING) { + if (cap_top) { + crushes[d] = 0xFF; + end_stops[d]++; } + break; + } else if (stone == STONE_CAPSTONE) { + break; + } + end_stops[d]++; + } + } + /* + * 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. + * + * 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++) { + 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 + * stones at the end with a crush. + */ + const uint8_t last_drop_check = + (num > 1) ? (gaps & (1 << (num - 2))) : 1; + if (crushes[dir] == 0 || last_drop_check) { + // We have to record a crush! + const uint8_t crush = + (steps == end_stops[dir]) && crushes[dir]; + // Store the move + + list_append(list, A_MOVE, loc, + (crush << 7) | gaps, + (dir<<4) | num); + } + /* + * With thanks to + * https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation + * we have the following magic to generate the next + * permutation of steps-many set bits + */ + uint8_t t = (gaps | (gaps - 1)); + gaps = (t + 1) + | (((~t & -~t) - 1) >> (__builtin_ctz(gaps) + 1)); + } while (gaps && (gaps + 1 <= (1 << (num - 1)))); + } + } + } + } + } // end of if (count) { ... } + else if (material) { + // Empty square, generate placements + if (flat) { + list_prepend(list, A_PLACE, loc, STONE_FLAT, 0); + if (standing) + list_prepend(list, A_PLACE, loc, STONE_STANDING,0); } - return list; + if (cap) + list_prepend(list, A_PLACE, loc, STONE_CAPSTONE, 0); + } + } + } + return list; } void action_take(const action_t action) { - const int8_t loc = A_GET_LOC(action); - if (A_GET_TYPE(action) == A_PLACE) { - const uint8_t black = (current_colour == C_BLACK); - switch (A_GET_DATA0(action)) { - case STONE_FLAT: { - if (black) black_count--; - else white_count--; - colours[loc] = current_colour; - celldat[loc] = NUM_INC | STONE_FLAT; - break; - } - case STONE_STANDING: { - if (black) black_count--; - else white_count--; - colours[loc] = current_colour; - celldat[loc] = NUM_INC | STONE_STANDING; - break; - } - default: { - if (black) black_count &= 0x7F; - else white_count &= 0x7F; - colours[loc] = current_colour; - celldat[loc] = NUM_INC | STONE_CAPSTONE; - break; - } - } - } else { - /* - * 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; - int8_t delta = move_deltas[dir]; - - // Use the Kernighan method to count the set bits - int8_t steps = 1; - for (uint8_t _gaps = gaps; _gaps; steps++) _gaps &= _gaps - 1; - - // Move top stone type to destination - celldat[loc+steps*delta] &= CLR_STONE; // necessary for crushing - celldat[loc+steps*delta] |= STONE_AT(loc); - celldat[loc] &= CLR_STONE; - celldat[loc] |= STONE_FLAT; // should be optimised out - - uint8_t total = 1, gap_bit = 1 << (num - 2); // it's not important - // what negative - // shifts do here, we - // don't use gap_bit - // if num < 2 - // move stuff starting at destination - for (uint8_t d = 1; d < num; d++, total++, gap_bit >>= 1) { - // We took a step, move everything over so far - if (gaps & gap_bit) { - colours[loc+steps*delta] <<= total; - colours[loc+steps*delta] |= colours[loc] & ((1 << total) - 1); - colours[loc] >>= total; - celldat[loc+steps*delta] += total*NUM_INC; - celldat[loc] -= total*NUM_INC; - // Reset for next step - total = 0; - steps--; - } - } - // Move what remains (steps == 1 here always, so we simplify) - colours[loc+delta] <<= total; - colours[loc+delta] |= colours[loc] & ((1 << total) - 1); - colours[loc] >>= total; - celldat[loc+delta] += total*NUM_INC; - celldat[loc] -= total*NUM_INC; - } - // Next ply - inline_next_ply(); + const int8_t loc = A_GET_LOC(action); + if (A_GET_TYPE(action) == A_PLACE) { + const uint8_t black = (current_colour == C_BLACK); + switch (A_GET_DATA0(action)) { + case STONE_FLAT: { + if (black) black_count--; + else white_count--; + colours[loc] = current_colour; + celldat[loc] = NUM_INC | STONE_FLAT; + break; + } + case STONE_STANDING: { + if (black) black_count--; + else white_count--; + colours[loc] = current_colour; + celldat[loc] = NUM_INC | STONE_STANDING; + break; + } + default: { + if (black) black_count &= 0x7F; + else white_count &= 0x7F; + colours[loc] = current_colour; + celldat[loc] = NUM_INC | STONE_CAPSTONE; + break; + } + } + } else { + /* + * 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; + int8_t delta = move_deltas[dir]; + + // Use the Kernighan method to count the set bits + int8_t steps = 1; + for (uint8_t _gaps = gaps; _gaps; steps++) _gaps &= _gaps - 1; + + // Move top stone type to destination + celldat[loc+steps*delta] &= CLR_STONE; // necessary for crushing + celldat[loc+steps*delta] |= STONE_AT(loc); + celldat[loc] &= CLR_STONE; + celldat[loc] |= STONE_FLAT; // should be optimised out + + uint8_t total = 1, gap_bit = 1 << (num - 2); // it's not important + // what negative + // shifts do here, we + // don't use gap_bit + // if num < 2 + // move stuff starting at destination + for (uint8_t d = 1; d < num; d++, total++, gap_bit >>= 1) { + // We took a step, move everything over so far + if (gaps & gap_bit) { + colours[loc+steps*delta] <<= total; + colours[loc+steps*delta] |= colours[loc] & ((1 << total) - 1); + colours[loc] >>= total; + celldat[loc+steps*delta] += total*NUM_INC; + celldat[loc] -= total*NUM_INC; + // Reset for next step + total = 0; + steps--; + } + } + // Move what remains (steps == 1 here always, so we simplify) + colours[loc+delta] <<= total; + colours[loc+delta] |= colours[loc] & ((1 << total) - 1); + colours[loc] >>= total; + celldat[loc+delta] += total*NUM_INC; + celldat[loc] -= total*NUM_INC; + } + // Next ply + inline_next_ply(); } void action_undo(const action_t action) { - // Previous ply - inline_prev_ply(); - - const int8_t loc = A_GET_LOC(action); - if (A_GET_TYPE(action) == A_PLACE) { - const uint8_t black = (current_colour == C_BLACK); - celldat[loc] = 0; - if (A_GET_DATA0(action) == STONE_CAPSTONE) { - if (black) black_count |= 0x80; - else white_count |= 0x80; - } else { - if (black) black_count++; - else white_count++; - } - } else { - // See action_take for comments, this is the time reversal, but - // there is one caveat -- undoing a crush! (*) - const uint8_t gaps = A_GET_DATA0(action) & 0x7F, - crush = A_GET_DATA0(action) & 0x80, - num = A_GET_DATA1(action) & 0x0F, - dir = A_GET_DATA1(action) >> 4; - const int8_t delta = move_deltas[dir]; - - int8_t steps = 1; - uint8_t gap_bit = 1, total = 1; - for (int8_t d = 1; d < num; d++, total++, gap_bit <<= 1) { - if (gaps & gap_bit) { - colours[loc] <<= total; - colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1); - colours[loc+steps*delta] >>= total; - celldat[loc] += total*NUM_INC; - celldat[loc+steps*delta] -= total*NUM_INC; - total = 0; - steps++; - } - } - colours[loc] <<= total; - colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1); - colours[loc+steps*delta] >>= total; - - celldat[loc] += total*NUM_INC; - // celldat[loc] &= CLR_STONE; is not necessary, as STONE_FLAT == 0 - celldat[loc] |= STONE_AT(loc+steps*delta); - celldat[loc+steps*delta] -= total*NUM_INC; - celldat[loc+steps*delta] &= CLR_STONE; - if (crush) { - celldat[loc+steps*delta] |= STONE_STANDING; - } else { - celldat[loc+steps*delta] |= STONE_FLAT; // should be optimised out - } - } + // Previous ply + inline_prev_ply(); + + const int8_t loc = A_GET_LOC(action); + if (A_GET_TYPE(action) == A_PLACE) { + const uint8_t black = (current_colour == C_BLACK); + celldat[loc] = 0; + if (A_GET_DATA0(action) == STONE_CAPSTONE) { + if (black) black_count |= 0x80; + else white_count |= 0x80; + } else { + if (black) black_count++; + else white_count++; + } + } else { + // See action_take for comments, this is the time reversal, but + // there is one caveat -- undoing a crush! (*) + const uint8_t gaps = A_GET_DATA0(action) & 0x7F, + crush = A_GET_DATA0(action) & 0x80, + num = A_GET_DATA1(action) & 0x0F, + dir = A_GET_DATA1(action) >> 4; + const int8_t delta = move_deltas[dir]; + + int8_t steps = 1; + uint8_t gap_bit = 1, total = 1; + for (int8_t d = 1; d < num; d++, total++, gap_bit <<= 1) { + if (gaps & gap_bit) { + colours[loc] <<= total; + colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1); + colours[loc+steps*delta] >>= total; + celldat[loc] += total*NUM_INC; + celldat[loc+steps*delta] -= total*NUM_INC; + total = 0; + steps++; + } + } + colours[loc] <<= total; + colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1); + colours[loc+steps*delta] >>= total; + + celldat[loc] += total*NUM_INC; + // celldat[loc] &= CLR_STONE; is not necessary, as STONE_FLAT == 0 + celldat[loc] |= STONE_AT(loc+steps*delta); + celldat[loc+steps*delta] -= total*NUM_INC; + celldat[loc+steps*delta] &= CLR_STONE; + if (crush) { + celldat[loc+steps*delta] |= STONE_STANDING; + } else { + celldat[loc+steps*delta] |= STONE_FLAT; // should be optimised out + } + } } void action_to_ptn(const action_t action, char* out_ptn) { - const int8_t loc = A_GET_LOC(action); - if (A_GET_TYPE(action) == A_PLACE) { - generate_place(loc, A_GET_DATA0(action), out_ptn); - } else { - const uint8_t gaps = A_GET_DATA0(action) & 0x7F, - num = A_GET_DATA1(action) & 0x0F, // unpack - dir = A_GET_DATA1(action) >> 4; - - uint8_t drops[board_size]; // we only ever need board_size-1 in - // drops actually, the last spot is to - // skip a bounds check at (**) - uint8_t mask = 1, steps = 0; - // Translate to a drop sequence - drops[0] = 1; mask = 1; - for (uint8_t d = 1; d < num; d++) { - if (gaps & mask) { - steps++; - drops[steps] = 1; // (**) no bounds check - } else { - drops[steps] += 1; - } - mask <<= 1; - } - generate_move(loc, dir, steps+1, drops, out_ptn); - } + const int8_t loc = A_GET_LOC(action); + if (A_GET_TYPE(action) == A_PLACE) { + generate_place(loc, A_GET_DATA0(action), out_ptn); + } else { + const uint8_t gaps = A_GET_DATA0(action) & 0x7F, + num = A_GET_DATA1(action) & 0x0F, // unpack + dir = A_GET_DATA1(action) >> 4; + + uint8_t drops[board_size]; // we only ever need board_size-1 in + // drops actually, the last spot is to + // skip a bounds check at (**) + uint8_t mask = 1, steps = 0; + // Translate to a drop sequence + drops[0] = 1; mask = 1; + for (uint8_t d = 1; d < num; d++) { + if (gaps & mask) { + steps++; + drops[steps] = 1; // (**) no bounds check + } else { + drops[steps] += 1; + } + mask <<= 1; + } + generate_move(loc, dir, steps+1, drops, out_ptn); + } } // =================================================================== @@ -384,61 +384,61 @@ 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++; + 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++; } 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 + 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); + new->next = list->head; + list->head = new; + new->action = A_BUILD(type, loc, data0, data1); - if (list->length == 0) { - list->tail = new; - } + if (list->length == 0) { + list->tail = new; + } - list->length++; + list->length++; } static inline void inline_next_ply(void) { - ply++; - if (ply == 2) { - current_colour = C_WHITE; - } else { - if (current_colour == C_BLACK) current_colour = C_WHITE; - else current_colour = C_BLACK; - } + ply++; + if (ply == 2) { + current_colour = C_WHITE; + } else { + if (current_colour == C_BLACK) current_colour = C_WHITE; + else current_colour = C_BLACK; + } } static inline void inline_prev_ply(void) { - if (ply>0) ply--; - if (ply == 1) { - current_colour = C_WHITE; - } else { - if (current_colour == C_BLACK) current_colour = C_WHITE; - else current_colour = C_BLACK; - } + if (ply>0) ply--; + if (ply == 1) { + current_colour = C_WHITE; + } else { + if (current_colour == C_BLACK) current_colour = C_WHITE; + else current_colour = C_BLACK; + } } diff --git a/include/actions.h b/include/actions.h index 75c881e..8df9392 100644 --- a/include/actions.h +++ b/include/actions.h @@ -1,18 +1,18 @@ /* - This file is part of ct. + This file is part of ct. - 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 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. + 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 ct. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with ct. If not, see <https://www.gnu.org/licenses/>. */ #ifndef ACTIONS_H @@ -39,19 +39,19 @@ typedef uint32_t action_t; #define A_GET_DATA0(a) (int8_t)(((a)>>A_DATA0_SHIFT) & 0xFF) #define A_GET_LOC(a) (uint8_t)(((a)>>A_LOC_SHIFT) & 0xFF) #define A_GET_TYPE(a) (uint8_t)((a) & 0xFF) -#define A_BUILD(type,loc,data0,data1) ((type) \ - | (loc) << A_LOC_SHIFT \ - | (data0) << A_DATA0_SHIFT \ - | (data1) << A_DATA1_SHIFT) +#define A_BUILD(type,loc,data0,data1) ((type) \ + | (loc) << A_LOC_SHIFT \ + | (data0) << A_DATA0_SHIFT \ + | (data1) << A_DATA1_SHIFT) typedef struct action_node_s { - struct action_node_s *next; - action_t action; + 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; + struct action_node_s *head, *tail; + uint32_t length; } action_list_t; // =================================================================== diff --git a/include/cnn1986.c b/include/cnn1986.c index b5bedfa..7c7dbcb 100644 --- a/include/cnn1986.c +++ b/include/cnn1986.c @@ -1,18 +1,18 @@ /* - This file is part of ct. + This file is part of ct. - 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 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. + 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 ct. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with ct. If not, see <https://www.gnu.org/licenses/>. */ #include "cnn1986.h" @@ -29,103 +29,103 @@ static float dense2[DENSE2_NUM]; #define RELU(x) ((x) = ((x)<0)?0:(x)) float cnn1986_evaluate_black_win(void) { - /* --------------- * - * Populate input * - * --------------- */ - for (unsigned int y = 0; y < board_size; y++) { - for (unsigned int x = 0; x < board_size; x++) { - const unsigned int loc = x+y*board_size; - const unsigned int count = COUNT_AT(loc); - colour_stack_t colour = colours[loc]; + /* --------------- * + * Populate input * + * --------------- */ + for (unsigned int y = 0; y < board_size; y++) { + for (unsigned int x = 0; x < board_size; x++) { + const unsigned int loc = x+y*board_size; + const unsigned int count = COUNT_AT(loc); + colour_stack_t colour = colours[loc]; - if (count > 0) { - float lookup = 0; - if (STONE_AT(loc) == STONE_STANDING) { - lookup = (colour & 1) ? +0.25 : -0.25; - } else if (STONE_AT(loc) == STONE_CAPSTONE) { - lookup = (colour & 1) ? +1.00 : -1.00; - } else { - lookup = (colour & 1) ? +0.50 : -0.50; - } - cur_board[loc][0] = lookup; - - colour>>=1; - for (unsigned int c = 1; c < count && c < KERN_CHAN; c++, colour>>=1) { - cur_board[loc][c] = (colour & 1) ? +0.50 : -0.50; - } - - for (unsigned int c = count; c < KERN_CHAN; c++) { - cur_board[loc][c] = 0; - } - } else { - for (unsigned int c = 0; c < KERN_CHAN; c++) { - cur_board[loc][c] = 0; - } - } - } - } - /* ------------------ * - * Convolution layer * - * ------------------ */ - // for each kernel - for (unsigned int kern = 0; kern < KERN_NUM; kern++) { - // the stride is 1, march across the board - for (unsigned int bx = 0; bx < KERN_OSIZE; bx++) { - for (unsigned int by = 0; by < KERN_OSIZE; by++) { - flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)] = - conv2d_biases[kern]; - // Compute the convolution for this position - for (unsigned int ky = 0; ky < KERN_SIZE; ky++) { - for (unsigned int kx = 0; kx < KERN_SIZE; kx++) { - for (unsigned int c = 0; c < KERN_CHAN; c++) { - // Where we are on the board - const unsigned int loc = kx+bx+(ky+by)*board_size; - flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)] - += cur_board[loc][c]*conv2d_weights[kern][ky][kx][c]; - } - } - } - RELU(flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)]); - } - } + if (count > 0) { + float lookup = 0; + if (STONE_AT(loc) == STONE_STANDING) { + lookup = (colour & 1) ? +0.25 : -0.25; + } else if (STONE_AT(loc) == STONE_CAPSTONE) { + lookup = (colour & 1) ? +1.00 : -1.00; + } else { + lookup = (colour & 1) ? +0.50 : -0.50; } - // Add input of flat counts - flattened[CONV_NUM] = (float)(white_count & 127)/21.0; - flattened[CONV_NUM+1] = (float)(black_count & 127)/21.0; - /* ------------------ * - * First dense layer * - * ------------------ */ - for (unsigned int d1 = 0; d1 < DENSE1_NUM; d1++) { - dense1[d1] = dense1_biases[d1]; - for (unsigned int fl = 0; fl < CONV_NUM+2; fl++) { - dense1[d1] += flattened[fl]*dense1_weights[d1][fl]; - } - RELU(dense1[d1]); - } - /* ------------------- * - * Second dense layer * - * ------------------- */ - for (unsigned int d2 = 0; d2 < DENSE2_NUM; d2++) { - dense2[d2] = dense2_biases[d2]; - for (unsigned int d1 = 0; d1 < DENSE1_NUM; d1++) { - dense2[d2] += dense1[d1]*dense2_weights[d2][d1]; - } - RELU(dense2[d2]); + cur_board[loc][0] = lookup; + + colour>>=1; + for (unsigned int c = 1; c < count && c < KERN_CHAN; c++, colour>>=1) { + cur_board[loc][c] = (colour & 1) ? +0.50 : -0.50; } - /* ------------- * - * Output layer * - * ------------- */ - float output = output_bias; - for (unsigned int d2 = 0; d2 < DENSE2_NUM; d2++) { - output += dense2[d2]*output_weights[d2]; + + for (unsigned int c = count; c < KERN_CHAN; c++) { + cur_board[loc][c] = 0; } - // 2*(clamped Pade approximant of logistic function) - 1 - output = (12.0+output+50.0*output/(output*output+10.0))/12.0 - 1.0; - if (output > 1.0) { - return 1.0; + } else { + for (unsigned int c = 0; c < KERN_CHAN; c++) { + cur_board[loc][c] = 0; } - else if (output < -1.0) { - return -1.0; + } + } + } + /* ------------------ * + * Convolution layer * + * ------------------ */ + // for each kernel + for (unsigned int kern = 0; kern < KERN_NUM; kern++) { + // the stride is 1, march across the board + for (unsigned int bx = 0; bx < KERN_OSIZE; bx++) { + for (unsigned int by = 0; by < KERN_OSIZE; by++) { + flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)] = + conv2d_biases[kern]; + // Compute the convolution for this position + for (unsigned int ky = 0; ky < KERN_SIZE; ky++) { + for (unsigned int kx = 0; kx < KERN_SIZE; kx++) { + for (unsigned int c = 0; c < KERN_CHAN; c++) { + // Where we are on the board + const unsigned int loc = kx+bx+(ky+by)*board_size; + flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)] + += cur_board[loc][c]*conv2d_weights[kern][ky][kx][c]; + } + } } - return output; + RELU(flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)]); + } + } + } + // Add input of flat counts + flattened[CONV_NUM] = (float)(white_count & 127)/21.0; + flattened[CONV_NUM+1] = (float)(black_count & 127)/21.0; + /* ------------------ * + * First dense layer * + * ------------------ */ + for (unsigned int d1 = 0; d1 < DENSE1_NUM; d1++) { + dense1[d1] = dense1_biases[d1]; + for (unsigned int fl = 0; fl < CONV_NUM+2; fl++) { + dense1[d1] += flattened[fl]*dense1_weights[d1][fl]; + } + RELU(dense1[d1]); + } + /* ------------------- * + * Second dense layer * + * ------------------- */ + for (unsigned int d2 = 0; d2 < DENSE2_NUM; d2++) { + dense2[d2] = dense2_biases[d2]; + for (unsigned int d1 = 0; d1 < DENSE1_NUM; d1++) { + dense2[d2] += dense1[d1]*dense2_weights[d2][d1]; + } + RELU(dense2[d2]); + } + /* ------------- * + * Output layer * + * ------------- */ + float output = output_bias; + for (unsigned int d2 = 0; d2 < DENSE2_NUM; d2++) { + output += dense2[d2]*output_weights[d2]; + } + // 2*(clamped Pade approximant of logistic function) - 1 + output = (12.0+output+50.0*output/(output*output+10.0))/12.0 - 1.0; + if (output > 1.0) { + return 1.0; + } + else if (output < -1.0) { + return -1.0; + } + return output; } diff --git a/include/cnn1986.h b/include/cnn1986.h index 40a0920..3cfde31 100644 --- a/include/cnn1986.h +++ b/include/cnn1986.h @@ -1,18 +1,18 @@ /* - This file is part of ct. + This file is part of ct. - 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 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. + 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 ct. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with ct. If not, see <https://www.gnu.org/licenses/>. */ #include <tak.h> diff --git a/include/lcdlib.c b/include/lcdlib.c index 4d8c33e..69d6df0 100644 --- a/include/lcdlib.c +++ b/include/lcdlib.c @@ -1,18 +1,18 @@ /* - This file is part of ct. + This file is part of ct. - 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 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. + 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 ct. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with ct. If not, see <https://www.gnu.org/licenses/>. */ #include "lcdlib.h" @@ -24,74 +24,74 @@ static int line_idx; int lcd_begin(void) { - lcd = fopen("/dev/lcd", "w"); - if (lcd == NULL) return EXIT_FAILURE; - lcd_clear(); - return EXIT_SUCCESS; + lcd = fopen("/dev/lcd", "w"); + if (lcd == NULL) return EXIT_FAILURE; + lcd_clear(); + return EXIT_SUCCESS; } void lcd_end(void) { - fclose(lcd); + fclose(lcd); } void lcd_set_blink(void) { - fprintf(lcd, "%sB", esc); - fflush(lcd); + fprintf(lcd, "%sB", esc); + fflush(lcd); } void lcd_stop_blink(void) { - fprintf(lcd, "%sb", esc); - fflush(lcd); + fprintf(lcd, "%sb", esc); + fflush(lcd); } void lcd_clear(void) { - line_idx = 0; - for (int y = 0; y + 1 < LCD_HEIGHT; y++) { - fprintf(lcd, "%sy%dx0;%sk", esc, y, esc); - previous_lines[y][0] = 0; - } - fflush(lcd); + line_idx = 0; + for (int y = 0; y + 1 < LCD_HEIGHT; y++) { + fprintf(lcd, "%sy%dx0;%sk", esc, y, esc); + previous_lines[y][0] = 0; + } + fflush(lcd); } void lcd_put_line(const enum LCD_WRITE_MODE mode, const char *line) { - char last_line = 0; - if (line_idx == LCD_HEIGHT) { - if (mode == L_SCROLL) { - // If we're at the bottom, ``shift'' everything up - for (int y = 1; y < LCD_HEIGHT; y++) { - // Go to the start of row y, clear the line, and print the - // previous string there - fprintf(lcd, "%sy%dx0;%sk%s", esc, y-1, esc, previous_lines[y]); - // Overwrite the stored previous line with the next - strncpy(previous_lines[y-1], previous_lines[y], LCD_WIDTH+1); - } - } - last_line = 1; - } - // Go to the correct line, clear it, and write the input. - fprintf(lcd, "%sy%dx0;%sk%s", esc, line_idx, esc, line); - fflush(lcd); - // Store this line, null-terminate! - if (last_line) line_idx--; - strncpy(previous_lines[line_idx], line, LCD_WIDTH+1); - previous_lines[line_idx][LCD_WIDTH] = 0; - if (mode == L_SCROLL && line_idx < LCD_HEIGHT) line_idx++; + char last_line = 0; + if (line_idx == LCD_HEIGHT) { + if (mode == L_SCROLL) { + // If we're at the bottom, ``shift'' everything up + for (int y = 1; y < LCD_HEIGHT; y++) { + // Go to the start of row y, clear the line, and print the + // previous string there + fprintf(lcd, "%sy%dx0;%sk%s", esc, y-1, esc, previous_lines[y]); + // Overwrite the stored previous line with the next + strncpy(previous_lines[y-1], previous_lines[y], LCD_WIDTH+1); + } + } + last_line = 1; + } + // Go to the correct line, clear it, and write the input. + fprintf(lcd, "%sy%dx0;%sk%s", esc, line_idx, esc, line); + fflush(lcd); + // Store this line, null-terminate! + if (last_line) line_idx--; + strncpy(previous_lines[line_idx], line, LCD_WIDTH+1); + previous_lines[line_idx][LCD_WIDTH] = 0; + if (mode == L_SCROLL && line_idx < LCD_HEIGHT) line_idx++; } void lcd_printf_line(const enum LCD_WRITE_MODE mode, - const char *format, ...) { - char buf[LCD_WIDTH+1]; + const char *format, ...) { + char buf[LCD_WIDTH+1]; - va_list(args); - va_start(args, format); - vsnprintf(buf, LCD_WIDTH+1, format, args); - va_end(args); + va_list(args); + va_start(args, format); + vsnprintf(buf, LCD_WIDTH+1, format, args); + va_end(args); - lcd_put_line(mode, buf); + lcd_put_line(mode, buf); } diff --git a/include/lcdlib.h b/include/lcdlib.h index 87aef12..c514ba0 100644 --- a/include/lcdlib.h +++ b/include/lcdlib.h @@ -1,18 +1,18 @@ /* - This file is part of ct. + This file is part of ct. - 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 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. + 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 ct. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with ct. If not, see <https://www.gnu.org/licenses/>. */ #include <stdlib.h> @@ -43,4 +43,4 @@ void lcd_stop_blink(void); 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, ...); + const char *format, ...); diff --git a/include/negamax.h b/include/negamax.h index f56f405..47f4ede 100644 --- a/include/negamax.h +++ b/include/negamax.h @@ -1,18 +1,18 @@ /* - This file is part of ct. + This file is part of ct. - 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 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. + 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 ct. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with ct. If not, see <https://www.gnu.org/licenses/>. */ #include <stdint.h> @@ -33,8 +33,8 @@ extern char negamax_ptn[9]; extern uint8_t negamax_search_depth; extern void negamax_display_progress(const uint8_t cur_depth, - const uint8_t init_depth, - const uint32_t length); + const uint8_t init_depth, + const uint32_t length); // =================================================================== // Methods diff --git a/include/tak.c b/include/tak.c index 6505bb1..5fd8e9a 100644 --- a/include/tak.c +++ b/include/tak.c @@ -1,18 +1,18 @@ /* - This file is part of ct. + This file is part of ct. - 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 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. + 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 ct. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with ct. If not, see <https://www.gnu.org/licenses/>. */ #include "tak.h" @@ -40,34 +40,34 @@ uint8_t white_count, black_count, ply; void reset_state(const uint8_t new_board_size) { - if (new_board_size == 6) { - board_size = 6; - white_count = 128 | 30; - black_count = 128 | 30; - } else { - board_size = 5; - white_count = 128 | 21; - black_count = 128 | 21; - } - - ply = 0; - won = 0xFF; // i may live to regret this hack - current_colour = C_BLACK; - - for (uint8_t k = 0; k < NUM_SQUARES; k++ ) { - celldat[k] = 0; - } + if (new_board_size == 6) { + board_size = 6; + white_count = 128 | 30; + black_count = 128 | 30; + } else { + board_size = 5; + white_count = 128 | 21; + black_count = 128 | 21; + } + + ply = 0; + won = 0xFF; // i may live to regret this hack + current_colour = C_BLACK; + + for (uint8_t k = 0; k < NUM_SQUARES; k++ ) { + celldat[k] = 0; + } } void next_ply(void) { - ply++; - if (ply == 2) { - current_colour = C_WHITE; - } else { - if (current_colour == C_BLACK) current_colour = C_WHITE; - else current_colour = C_BLACK; - } + ply++; + if (ply == 2) { + current_colour = C_WHITE; + } else { + if (current_colour == C_BLACK) current_colour = C_WHITE; + else current_colour = C_BLACK; + } } // =================================================================== @@ -76,47 +76,47 @@ next_ply(void) { enum ACT_RESULT try_place(const int8_t location, const enum COLOUR colour, - const enum STONE_VARIANT stone) + const enum STONE_VARIANT stone) { - // Game is over? - if (won < 0xFF) return GAME_END; - // Can't place on an occupied square - if (COUNT_AT(location)) { - return ACT_ILLEGAL; + // Game is over? + if (won < 0xFF) return GAME_END; + // Can't place on an occupied square + if (COUNT_AT(location)) { + return ACT_ILLEGAL; + } else { + switch (stone) { + case STONE_STANDING: + if (ply < 2) return ACT_ILLEGAL; + // behold the magic GCC comment which defeates + // -Wimplicit-fallthrough: + // fall through + case STONE_FLAT: { + if (colour == C_BLACK) { + if (black_count & 127) black_count--; + else return ACT_ILLEGAL; + } else { + if (white_count & 127) white_count--; + else return ACT_ILLEGAL; + } + break; + } + case STONE_CAPSTONE: { + if (ply < 2) return ACT_ILLEGAL; + if (colour == C_BLACK) { + if (black_count & 128) black_count &= 127; + else return ACT_ILLEGAL; } else { - switch (stone) { - case STONE_STANDING: - if (ply < 2) return ACT_ILLEGAL; - // behold the magic GCC comment which defeates - // -Wimplicit-fallthrough: - // fall through - case STONE_FLAT: { - if (colour == C_BLACK) { - if (black_count & 127) black_count--; - else return ACT_ILLEGAL; - } else { - if (white_count & 127) white_count--; - else return ACT_ILLEGAL; - } - break; - } - case STONE_CAPSTONE: { - if (ply < 2) return ACT_ILLEGAL; - if (colour == C_BLACK) { - if (black_count & 128) black_count &= 127; - else return ACT_ILLEGAL; - } else { - if (white_count & 128) white_count &= 127; - else return ACT_ILLEGAL; - } - break; - } - } - - colours[location] = colour; - celldat[location] = NUM_INC | stone; - return ACT_OK; + if (white_count & 128) white_count &= 127; + else return ACT_ILLEGAL; } + break; + } + } + + colours[location] = colour; + celldat[location] = NUM_INC | stone; + return ACT_OK; + } } // =================================================================== @@ -125,105 +125,105 @@ try_place(const int8_t location, const enum COLOUR colour, static inline void push_stones(const int8_t location, const uint8_t count, - const uint8_t new_colours, - const enum STONE_VARIANT top_stone) { - colours[location] = (colours[location] << count) | new_colours; - celldat[location] = top_stone - | ((celldat[location] + ((count << NUM_SHIFT))) & NUM_MASK); + const uint8_t new_colours, + const enum STONE_VARIANT top_stone) { + colours[location] = (colours[location] << count) | new_colours; + celldat[location] = top_stone + | ((celldat[location] + ((count << NUM_SHIFT))) & NUM_MASK); } enum ACT_RESULT try_move(const int8_t location, const enum MOVE_DIRECTION direction, - const uint8_t steps, const uint8_t drops[5]) { - // Game is over? - if (won < 0xFF) return GAME_END; - // Can't do this - if (steps == 0 || steps > board_size) return ACT_ILLEGAL; - // Check for stones at all - const uint8_t avail = COUNT_AT(location); - if (avail == 0) return ACT_ILLEGAL; - // Does the current player own the pile? - if ((colours[location] & 1) != current_colour) return ACT_ILLEGAL; - // Is the desired direction and count on the board? - int8_t delta = 0; - switch (direction) { - case M_UP: { - delta = +board_size; - if (location + delta * steps > NUM_SQUARES) - return ACT_ILLEGAL; - break; - }; - case M_DOWN: { - delta = -board_size; - if (location + delta * steps < 0) - return ACT_ILLEGAL; - break; - }; - case M_RIGHT: { - delta = +1; - if ((location + steps * delta) / board_size - > location / board_size) - return ACT_ILLEGAL; - break; - }; - case M_LEFT: { - delta = -1; - // We need the extra check for zero here because, irritatingly, - // -1 / board_size == 1 / board_size - if ((location + steps * delta < 0) || - ((location + steps * delta) / board_size - < location / board_size)) - return ACT_ILLEGAL; - break; - }; - }; - - // For every square in the direction - uint8_t total = 0; - for (uint8_t k = 0; k < steps; k++) { - // Can't drop 0 anywhere because we're past the first square - if (drops[k] == 0) - return ACT_ILLEGAL; - // Can't drop more than BOARD_SIZE stones in a square - if (drops[k] > board_size) - return ACT_ILLEGAL; - // Check for overflows - if (COUNT_AT(location+(k+1)*delta) + drops[k] > 0x0F) - return ACT_OVERFLOW; - // Check for capstone - if (STONE_AT(location+(k+1)*delta) == STONE_CAPSTONE) - return ACT_ILLEGAL; - // Check for wall - if ( (STONE_AT(location+(k+1)*delta) == STONE_STANDING) - // If not last drop, or not dropping just one, or not a cap - && ( (k+1 < steps) - || (drops[k] != 1) - || (STONE_AT(location) != STONE_CAPSTONE) ) - ) - return ACT_ILLEGAL; - total += drops[k]; - } - - // Can't ask to move 0, more than board_size, or stones available - if ( (total == 0) || (total > board_size) || (total > avail) ) - return ACT_ILLEGAL; - - // Nothing illegal, do it. First we add the stones to the - // destination squares - uint8_t j = total; - for (uint8_t k = 0; k < steps; k++) { - j -= drops[k]; - push_stones(location+(k+1)*delta, - drops[k], - (colours[location] >> j) & (0xFFFF >> (0x10 - drops[k])), - (k == steps - 1) ? STONE_AT(location) : STONE_FLAT); - } - // Then we drop them from the source - colours[location] >>= total; - const uint8_t dec_count = celldat[location] - (total << NUM_SHIFT); - celldat[location] = dec_count & NUM_MASK; - - return ACT_OK; + const uint8_t steps, const uint8_t drops[5]) { + // Game is over? + if (won < 0xFF) return GAME_END; + // Can't do this + if (steps == 0 || steps > board_size) return ACT_ILLEGAL; + // Check for stones at all + const uint8_t avail = COUNT_AT(location); + if (avail == 0) return ACT_ILLEGAL; + // Does the current player own the pile? + if ((colours[location] & 1) != current_colour) return ACT_ILLEGAL; + // Is the desired direction and count on the board? + int8_t delta = 0; + switch (direction) { + case M_UP: { + delta = +board_size; + if (location + delta * steps > NUM_SQUARES) + return ACT_ILLEGAL; + break; + }; + case M_DOWN: { + delta = -board_size; + if (location + delta * steps < 0) + return ACT_ILLEGAL; + break; + }; + case M_RIGHT: { + delta = +1; + if ((location + steps * delta) / board_size + > location / board_size) + return ACT_ILLEGAL; + break; + }; + case M_LEFT: { + delta = -1; + // We need the extra check for zero here because, irritatingly, + // -1 / board_size == 1 / board_size + if ((location + steps * delta < 0) || + ((location + steps * delta) / board_size + < location / board_size)) + return ACT_ILLEGAL; + break; + }; + }; + + // For every square in the direction + uint8_t total = 0; + for (uint8_t k = 0; k < steps; k++) { + // Can't drop 0 anywhere because we're past the first square + if (drops[k] == 0) + return ACT_ILLEGAL; + // Can't drop more than BOARD_SIZE stones in a square + if (drops[k] > board_size) + return ACT_ILLEGAL; + // Check for overflows + if (COUNT_AT(location+(k+1)*delta) + drops[k] > 0x0F) + return ACT_OVERFLOW; + // Check for capstone + if (STONE_AT(location+(k+1)*delta) == STONE_CAPSTONE) + return ACT_ILLEGAL; + // Check for wall + if ( (STONE_AT(location+(k+1)*delta) == STONE_STANDING) + // If not last drop, or not dropping just one, or not a cap + && ( (k+1 < steps) + || (drops[k] != 1) + || (STONE_AT(location) != STONE_CAPSTONE) ) + ) + return ACT_ILLEGAL; + total += drops[k]; + } + + // Can't ask to move 0, more than board_size, or stones available + if ( (total == 0) || (total > board_size) || (total > avail) ) + return ACT_ILLEGAL; + + // Nothing illegal, do it. First we add the stones to the + // destination squares + uint8_t j = total; + for (uint8_t k = 0; k < steps; k++) { + j -= drops[k]; + push_stones(location+(k+1)*delta, + drops[k], + (colours[location] >> j) & (0xFFFF >> (0x10 - drops[k])), + (k == steps - 1) ? STONE_AT(location) : STONE_FLAT); + } + // Then we drop them from the source + colours[location] >>= total; + const uint8_t dec_count = celldat[location] - (total << NUM_SHIFT); + celldat[location] = dec_count & NUM_MASK; + + return ACT_OK; } // =================================================================== @@ -233,140 +233,140 @@ try_move(const int8_t location, const enum MOVE_DIRECTION direction, // Check for the presence of a road connecting opposite sides static enum WIN_TYPE check_road_colour(const enum COLOUR colour) { - int component[NUM_SQUARES], touching[NUM_SQUARES]; - - /* - We're doing a poor version of a disjoint set data structure to - track and merge connected components. The array `component' stores - indices to the representative cells of each connected component. A - cell is representative if component[cell] = cell. We track only - whether representatives are touching sides, and do a 2-dimensional - DP approach to forming these from the board. - - Note: we don't track the rank/size of each tree, because we're not - interested in good asymptotic complexity in the size of the board, - merely good performance for a single board size in practice. For - the same reason we also don't do path flattening/halving or - anything. - */ - for (int k=0; k<NUM_SQUARES; k++) { - component[k] = k; // every square is in its own connected - // component initially - touching[k] = 0; // and not connected to any sides - } - - // touching is the bit mask for connectivity, - // bottom | top | left | right - // 1 2 4 8 - - int touch = 5; - for (int row = 0; row < board_size; row++) { - for (int col = 0; col < board_size; col++) { - const int cur = THE_COORDS(col, row); - if (COUNT_AT(cur) - && (colours[cur] & 1) == colour - && STONE_AT(cur) != STONE_STANDING) { - - // do we have any neighbours to the left and below? - const int left_neighbour = ((cur % board_size > 0) - && (COUNT_AT(cur - 1)) // wont ever be out of bounds - && ((colours[cur - 1] & 1) == colour) - && (STONE_AT(cur - 1) != STONE_STANDING)); - - const int lowr_neighbour = ((cur >= board_size) - && (COUNT_AT(cur - board_size)) - && ((colours[cur - board_size] & 1) == colour) - && (STONE_AT(cur - board_size) != STONE_STANDING)); - - // always take the component of the lower neighbour if - // possible, failing that take the left neighbour, otherwise - // we're not yet connected, so update our own component. - if (lowr_neighbour) { - // look up the root of the lower neighbour - int root = cur - board_size; - while (root != component[root]) - root = component[root]; - // join the set - component[cur] = root; - if (touch) { - // something new - touching[root] |= touch; - // are we done? - if ( (touching[root] & 0x3) == 0x3 || (touching[root] & 0xC) == 0xC) - return (colour == C_BLACK) ? WIN_ROAD_BLACK : WIN_ROAD_WHITE; - } - // if we also have a left neighbour then we should `merge' - // sets, and here we assume that the left neighbour set is - // always smaller (may not be) for the direction of merge - if (left_neighbour) { - int left_root = cur - 1; - while (left_root != component[left_root]) - left_root = component[left_root]; - // merge - const int left_touch = touching[left_root]; - if (left_touch) { - touching[root] |= left_touch; - if ( (touching[root] & 0x3) == 0x3 || (touching[root] & 0xC) == 0xC) - return (colour == C_BLACK) ? WIN_ROAD_BLACK : WIN_ROAD_WHITE; - } - component[left_root] = root; - } - } else if (left_neighbour) { - int root = cur - 1; - while (root != component[root]) - root = component[root]; - component[cur] = root; - if (touch) { - touching[root] |= touch; - if ( (touching[root] & 0x3) == 0x3 || (touching[root] & 0xC) == 0xC) - return (colour == C_BLACK) ? WIN_ROAD_BLACK : WIN_ROAD_WHITE; - } - } else if (touch) { - // we had no left or lower neighbour, so we're on our own - touching[cur] = touch; - } - } - if (col + 2 == board_size) touch |= 8; - else touch &= 0x3; - } - if (row + 2 == board_size) touch = 6; - else touch = 4; + int component[NUM_SQUARES], touching[NUM_SQUARES]; + + /* + We're doing a poor version of a disjoint set data structure to + track and merge connected components. The array `component' stores + indices to the representative cells of each connected component. A + cell is representative if component[cell] = cell. We track only + whether representatives are touching sides, and do a 2-dimensional + DP approach to forming these from the board. + + Note: we don't track the rank/size of each tree, because we're not + interested in good asymptotic complexity in the size of the board, + merely good performance for a single board size in practice. For + the same reason we also don't do path flattening/halving or + anything. + */ + for (int k=0; k<NUM_SQUARES; k++) { + component[k] = k; // every square is in its own connected + // component initially + touching[k] = 0; // and not connected to any sides + } + + // touching is the bit mask for connectivity, + // bottom | top | left | right + // 1 2 4 8 + + int touch = 5; + for (int row = 0; row < board_size; row++) { + for (int col = 0; col < board_size; col++) { + const int cur = THE_COORDS(col, row); + if (COUNT_AT(cur) + && (colours[cur] & 1) == colour + && STONE_AT(cur) != STONE_STANDING) { + + // do we have any neighbours to the left and below? + const int left_neighbour = ((cur % board_size > 0) + && (COUNT_AT(cur - 1)) // wont ever be out of bounds + && ((colours[cur - 1] & 1) == colour) + && (STONE_AT(cur - 1) != STONE_STANDING)); + + const int lowr_neighbour = ((cur >= board_size) + && (COUNT_AT(cur - board_size)) + && ((colours[cur - board_size] & 1) == colour) + && (STONE_AT(cur - board_size) != STONE_STANDING)); + + // always take the component of the lower neighbour if + // possible, failing that take the left neighbour, otherwise + // we're not yet connected, so update our own component. + if (lowr_neighbour) { + // look up the root of the lower neighbour + int root = cur - board_size; + while (root != component[root]) + root = component[root]; + // join the set + component[cur] = root; + if (touch) { + // something new + touching[root] |= touch; + // are we done? + if ( (touching[root] & 0x3) == 0x3 || (touching[root] & 0xC) == 0xC) + return (colour == C_BLACK) ? WIN_ROAD_BLACK : WIN_ROAD_WHITE; + } + // if we also have a left neighbour then we should `merge' + // sets, and here we assume that the left neighbour set is + // always smaller (may not be) for the direction of merge + if (left_neighbour) { + int left_root = cur - 1; + while (left_root != component[left_root]) + left_root = component[left_root]; + // merge + const int left_touch = touching[left_root]; + if (left_touch) { + touching[root] |= left_touch; + if ( (touching[root] & 0x3) == 0x3 || (touching[root] & 0xC) == 0xC) + return (colour == C_BLACK) ? WIN_ROAD_BLACK : WIN_ROAD_WHITE; + } + component[left_root] = root; + } + } else if (left_neighbour) { + int root = cur - 1; + while (root != component[root]) + root = component[root]; + component[cur] = root; + if (touch) { + touching[root] |= touch; + if ( (touching[root] & 0x3) == 0x3 || (touching[root] & 0xC) == 0xC) + return (colour == C_BLACK) ? WIN_ROAD_BLACK : WIN_ROAD_WHITE; + } + } else if (touch) { + // we had no left or lower neighbour, so we're on our own + touching[cur] = touch; } - return 0xFF; + } + if (col + 2 == board_size) touch |= 8; + else touch &= 0x3; + } + if (row + 2 == board_size) touch = 6; + else touch = 4; + } + return 0xFF; } enum WIN_TYPE check_win(void) { - // Road? - enum WIN_TYPE rb, rw; - rb = check_road_colour(C_BLACK); - rw = check_road_colour(C_WHITE); - - if (rb == WIN_ROAD_BLACK && rw == WIN_ROAD_WHITE) { - return (ply & 1) ? rb : rw; // Dragons - } else if (rw == WIN_ROAD_WHITE) { - return rw; - } else if (rb == WIN_ROAD_BLACK) { - return rb; - } - - // Do we do a flat count? - int8_t total = 0, board_full = 1; - for (uint8_t k = 0; k < NUM_SQUARES; k++) { - if (COUNT_AT(k) == 0) { - board_full = 0; - } else if (STONE_AT(k) == STONE_FLAT) { - total += ((colours[k] & 1) == C_BLACK) ? +1 : -1 ; - } - } - if (black_count == 0 || white_count == 0 || board_full) { - // Decide based on count - if (total > 0) return WIN_FLAT_BLACK; - else if (total < 0) return WIN_FLAT_WHITE; - else return WIN_DRAW; - } - - return 0xFF; + // Road? + enum WIN_TYPE rb, rw; + rb = check_road_colour(C_BLACK); + rw = check_road_colour(C_WHITE); + + if (rb == WIN_ROAD_BLACK && rw == WIN_ROAD_WHITE) { + return (ply & 1) ? rb : rw; // Dragons + } else if (rw == WIN_ROAD_WHITE) { + return rw; + } else if (rb == WIN_ROAD_BLACK) { + return rb; + } + + // Do we do a flat count? + int8_t total = 0, board_full = 1; + for (uint8_t k = 0; k < NUM_SQUARES; k++) { + if (COUNT_AT(k) == 0) { + board_full = 0; + } else if (STONE_AT(k) == STONE_FLAT) { + total += ((colours[k] & 1) == C_BLACK) ? +1 : -1 ; + } + } + if (black_count == 0 || white_count == 0 || board_full) { + // Decide based on count + if (total > 0) return WIN_FLAT_BLACK; + else if (total < 0) return WIN_FLAT_WHITE; + else return WIN_DRAW; + } + + return 0xFF; } // =================================================================== // PTN place parser @@ -374,38 +374,38 @@ check_win(void) { #define NULL 0 -#define ASSERT_NONEMPTY { \ - if (ptn == NULL || *ptn == 0) return PTN_INVALID; \ - } +#define ASSERT_NONEMPTY { \ + if (ptn == NULL || *ptn == 0) return PTN_INVALID; \ + } #define ASSERT_MORE { if (*ptn == 0) return PTN_INVALID; } enum PTN_RESULT parse_place(char *ptn, uint8_t *out_location, - enum STONE_VARIANT *out_stone) { + enum STONE_VARIANT *out_stone) { - ASSERT_NONEMPTY; + ASSERT_NONEMPTY; - *out_stone = STONE_FLAT; - switch (*ptn) { - case 'C' : { ptn++; *out_stone = STONE_CAPSTONE; break; }; - case 'S' : { ptn++; *out_stone = STONE_STANDING; break; }; - case 'F' : { ptn++; break; }; - } + *out_stone = STONE_FLAT; + switch (*ptn) { + case 'C' : { ptn++; *out_stone = STONE_CAPSTONE; break; }; + case 'S' : { ptn++; *out_stone = STONE_STANDING; break; }; + case 'F' : { ptn++; break; }; + } - ASSERT_MORE; + ASSERT_MORE; - if ( (*ptn < 'a') || (*ptn > '`' + board_size) ) return PTN_INVALID; - *out_location = *ptn - 'a'; + if ( (*ptn < 'a') || (*ptn > '`' + board_size) ) return PTN_INVALID; + *out_location = *ptn - 'a'; - ptn++; ASSERT_MORE; + ptn++; ASSERT_MORE; - if ( (*ptn < '1') || (*ptn > board_size + '0') ) return PTN_INVALID; - *out_location += board_size * (*ptn - '1'); + if ( (*ptn < '1') || (*ptn > board_size + '0') ) return PTN_INVALID; + *out_location += board_size * (*ptn - '1'); - if (*(++ptn) > 0) return PTN_INVALID; + if (*(++ptn) > 0) return PTN_INVALID; - return PTN_OK; + return PTN_OK; } // =================================================================== @@ -414,72 +414,72 @@ parse_place(char *ptn, uint8_t *out_location, enum PTN_RESULT parse_move(char *ptn, uint8_t *out_location, - enum MOVE_DIRECTION *out_direction, - uint8_t *out_steps, uint8_t out_drops[5]) { - - ASSERT_NONEMPTY; - - uint8_t picked_up = 1; - - // Optionally indicate how many stones picked up - if ( (*ptn >= '1') && (*ptn <= '0' + board_size)) { - picked_up = *ptn - '0'; - ptn++; ASSERT_MORE; - } - - // column must be on the board - if ( (*ptn < 'a') || (*ptn > '`' + board_size) ) return PTN_INVALID; - *out_location = *ptn - 'a'; - - ptn++; ASSERT_MORE; - - // row must be on the board - if ( (*ptn < '1') || (*ptn > board_size + '0') ) return PTN_INVALID; - *out_location += board_size * (*ptn - '1'); - - ptn++; ASSERT_MORE; - - // valid direction - switch (*ptn) { - case '+': { *out_direction = M_UP; break; } - case '-': { *out_direction = M_DOWN; break; } - case '<': { *out_direction = M_LEFT; break; } - case '>': { *out_direction = M_RIGHT; break; } - default: return PTN_INVALID; - } - - // Handle the case 'n<column><row><direction>' as - // 'n<column><row><direction>n' for convenience, if n is omitted - // assume n = 1 - ptn++; - if (*ptn == 0) { - *out_steps = 1; - out_drops[0] = picked_up; - return PTN_OK; - } - - // Parse the drops in each subsequent square - *out_steps = 0; - uint8_t total = 0; - while (*ptn) { - // can't drop more than the carry limit, or less than 1 - if ( (*ptn < '1') || (*ptn > '0' + board_size) ) - return PTN_INVALID; - - // can't move more than the size of the board in any direction - if ( (*out_steps + 1 >= board_size) && *ptn) - return PTN_INVALID; - - out_drops[*out_steps] = *ptn - '0'; - total += out_drops[*out_steps]; - *out_steps += 1; - ptn++; - } - - // Mismatch between number of stones picked up and total dropped - if ( total != picked_up ) return PTN_INVALID; - - return PTN_OK; + enum MOVE_DIRECTION *out_direction, + uint8_t *out_steps, uint8_t out_drops[5]) { + + ASSERT_NONEMPTY; + + uint8_t picked_up = 1; + + // Optionally indicate how many stones picked up + if ( (*ptn >= '1') && (*ptn <= '0' + board_size)) { + picked_up = *ptn - '0'; + ptn++; ASSERT_MORE; + } + + // column must be on the board + if ( (*ptn < 'a') || (*ptn > '`' + board_size) ) return PTN_INVALID; + *out_location = *ptn - 'a'; + + ptn++; ASSERT_MORE; + + // row must be on the board + if ( (*ptn < '1') || (*ptn > board_size + '0') ) return PTN_INVALID; + *out_location += board_size * (*ptn - '1'); + + ptn++; ASSERT_MORE; + + // valid direction + switch (*ptn) { + case '+': { *out_direction = M_UP; break; } + case '-': { *out_direction = M_DOWN; break; } + case '<': { *out_direction = M_LEFT; break; } + case '>': { *out_direction = M_RIGHT; break; } + default: return PTN_INVALID; + } + + // Handle the case 'n<column><row><direction>' as + // 'n<column><row><direction>n' for convenience, if n is omitted + // assume n = 1 + ptn++; + if (*ptn == 0) { + *out_steps = 1; + out_drops[0] = picked_up; + return PTN_OK; + } + + // Parse the drops in each subsequent square + *out_steps = 0; + uint8_t total = 0; + while (*ptn) { + // can't drop more than the carry limit, or less than 1 + if ( (*ptn < '1') || (*ptn > '0' + board_size) ) + return PTN_INVALID; + + // can't move more than the size of the board in any direction + if ( (*out_steps + 1 >= board_size) && *ptn) + return PTN_INVALID; + + out_drops[*out_steps] = *ptn - '0'; + total += out_drops[*out_steps]; + *out_steps += 1; + ptn++; + } + + // Mismatch between number of stones picked up and total dropped + if ( total != picked_up ) return PTN_INVALID; + + return PTN_OK; } // =================================================================== @@ -488,15 +488,15 @@ parse_move(char *ptn, uint8_t *out_location, void generate_place(const uint8_t in_location, - const enum STONE_VARIANT in_stone, char out_ptn[4]) { - switch (in_stone) { - case STONE_FLAT: { break; } - case STONE_STANDING: { *out_ptn = 'S'; out_ptn++; break; } - case STONE_CAPSTONE: { *out_ptn = 'C'; out_ptn++; break; } - } - *out_ptn = 'a' + (in_location % board_size); out_ptn++; - *out_ptn = '1' + (in_location / board_size); out_ptn++; - *out_ptn = 0; + const enum STONE_VARIANT in_stone, char out_ptn[4]) { + switch (in_stone) { + case STONE_FLAT: { break; } + case STONE_STANDING: { *out_ptn = 'S'; out_ptn++; break; } + case STONE_CAPSTONE: { *out_ptn = 'C'; out_ptn++; break; } + } + *out_ptn = 'a' + (in_location % board_size); out_ptn++; + *out_ptn = '1' + (in_location / board_size); out_ptn++; + *out_ptn = 0; } // =================================================================== @@ -505,30 +505,30 @@ generate_place(const uint8_t in_location, void generate_move(const uint8_t in_location, - const enum MOVE_DIRECTION in_direction, - const uint8_t in_steps, const uint8_t in_drops[5], - char out_ptn[10]) { - uint8_t total = 0; - for (uint8_t k = 0; k<in_steps; k++) total+=in_drops[k]; - if (total > 1) { - *out_ptn = '0' + total; out_ptn++; - } - - *out_ptn = 'a' + (in_location % board_size); out_ptn++; - *out_ptn = '1' + (in_location / board_size); out_ptn++; - - switch (in_direction) { - case M_UP: { *out_ptn = '+'; break; } - case M_DOWN: { *out_ptn = '-'; break; } - case M_LEFT: { *out_ptn = '<'; break; } - case M_RIGHT: { *out_ptn = '>'; break; } - }; out_ptn++; - - for (uint8_t k = 0; (total > 1) && (k < in_steps); k++) { - *out_ptn = '0' + in_drops[k]; out_ptn++; - } - - *out_ptn = 0; + const enum MOVE_DIRECTION in_direction, + const uint8_t in_steps, const uint8_t in_drops[5], + char out_ptn[10]) { + uint8_t total = 0; + for (uint8_t k = 0; k<in_steps; k++) total+=in_drops[k]; + if (total > 1) { + *out_ptn = '0' + total; out_ptn++; + } + + *out_ptn = 'a' + (in_location % board_size); out_ptn++; + *out_ptn = '1' + (in_location / board_size); out_ptn++; + + switch (in_direction) { + case M_UP: { *out_ptn = '+'; break; } + case M_DOWN: { *out_ptn = '-'; break; } + case M_LEFT: { *out_ptn = '<'; break; } + case M_RIGHT: { *out_ptn = '>'; break; } + }; out_ptn++; + + for (uint8_t k = 0; (total > 1) && (k < in_steps); k++) { + *out_ptn = '0' + in_drops[k]; out_ptn++; + } + + *out_ptn = 0; } // =================================================================== @@ -537,65 +537,65 @@ generate_move(const uint8_t in_location, static uint8_t is_not_placement(char *ptn) { - if (ptn == 0) return 0; - for (;;ptn++) { - switch (*ptn) { - case '+': - case '-': - case '>': - case '<': return 1; - case 0: return 0; - } - } + if (ptn == 0) return 0; + for (;;ptn++) { + switch (*ptn) { + case '+': + case '-': + case '>': + case '<': return 1; + case 0: return 0; + } + } } enum ACT_RESULT do_ptn(char *ptn) { - // Game over? - if (won < 0xFF) return GAME_END; - - enum PTN_RESULT ptn_res; - enum ACT_RESULT act_res; - uint8_t location; - - // Placing or moving? - if (is_not_placement(ptn)) { - uint8_t steps, drops[5]; - enum MOVE_DIRECTION direction; - // Parse it as a move - ptn_res = parse_move(ptn, &location, &direction, &steps, drops); - // If valid PTN, try to do it - if (ptn_res == PTN_OK) { - if (ply < 2) return ACT_ILLEGAL; - act_res = try_move(location, direction, steps, drops); - } else { - return ACT_INVALID_PTN; - } - } else { - // It was not a move - enum STONE_VARIANT stone; - // Was it a valid placement? - ptn_res = parse_place(ptn, &location, &stone); - // If so, try it - if (ptn_res == PTN_OK) - act_res = try_place(location, current_colour, stone); - else - return ACT_INVALID_PTN; - } - // A valid ply occured - if (act_res == ACT_OK) { - // Don't bother checking that the game was won early on, could be - // more conservative here :) - if (ply >= board_size) { - won = check_win(); - if (won < 0xFF) { - // Winning move, but no need to update current colour - ply++; - return GAME_END; - } - } - // Only step if the game isn't over yet - next_ply(); - } - return act_res; + // Game over? + if (won < 0xFF) return GAME_END; + + enum PTN_RESULT ptn_res; + enum ACT_RESULT act_res; + uint8_t location; + + // Placing or moving? + if (is_not_placement(ptn)) { + uint8_t steps, drops[5]; + enum MOVE_DIRECTION direction; + // Parse it as a move + ptn_res = parse_move(ptn, &location, &direction, &steps, drops); + // If valid PTN, try to do it + if (ptn_res == PTN_OK) { + if (ply < 2) return ACT_ILLEGAL; + act_res = try_move(location, direction, steps, drops); + } else { + return ACT_INVALID_PTN; + } + } else { + // It was not a move + enum STONE_VARIANT stone; + // Was it a valid placement? + ptn_res = parse_place(ptn, &location, &stone); + // If so, try it + if (ptn_res == PTN_OK) + act_res = try_place(location, current_colour, stone); + else + return ACT_INVALID_PTN; + } + // A valid ply occured + if (act_res == ACT_OK) { + // Don't bother checking that the game was won early on, could be + // more conservative here :) + if (ply >= board_size) { + won = check_win(); + if (won < 0xFF) { + // Winning move, but no need to update current colour + ply++; + return GAME_END; + } + } + // Only step if the game isn't over yet + next_ply(); + } + return act_res; } diff --git a/include/tak.h b/include/tak.h index 8a1d8be..26f4ae6 100644 --- a/include/tak.h +++ b/include/tak.h @@ -1,18 +1,18 @@ /* - This file is part of ct. + This file is part of ct. - 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 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. + 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 ct. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with ct. If not, see <https://www.gnu.org/licenses/>. */ #ifndef TAK_H @@ -24,28 +24,38 @@ // Types // =================================================================== -enum ACT_RESULT { ACT_OK, ACT_ILLEGAL, ACT_OVERFLOW, ACT_INVALID_PTN, GAME_END }; +enum ACT_RESULT { + ACT_OK, + ACT_ILLEGAL, + ACT_OVERFLOW, + ACT_INVALID_PTN, + GAME_END +}; enum PTN_RESULT { PTN_OK, PTN_INVALID }; enum TPS_RESULT { TPS_OK, TPS_INVALID }; -enum COLOUR { C_WHITE, C_BLACK }; -enum STONE_VARIANT { STONE_FLAT, STONE_STANDING, STONE_CAPSTONE }; +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 }; -enum WIN_TYPE { WIN_DRAW, - WIN_FLAT_WHITE, WIN_FLAT_BLACK, - WIN_ROAD_WHITE, WIN_ROAD_BLACK }; +enum WIN_TYPE { + WIN_DRAW, + WIN_FLAT_WHITE, + WIN_FLAT_BLACK, + WIN_ROAD_WHITE, + WIN_ROAD_BLACK +}; typedef uint8_t data_t; typedef uint16_t colour_stack_t; -#define NUM_SHIFT 4 -#define NUM_MASK (0xF<<NUM_SHIFT) // 0b11110000 -#define NUM_INC (0x1<<NUM_SHIFT) // 0b00010000 -#define STONE_MASK 3 // 0b00000011 -#define STONE_AT(l) (celldat[(l)] & STONE_MASK) -#define COUNT_AT(l) (celldat[(l)] >> NUM_SHIFT) -#define THE_COORDS(col,row) ((col)+(row)*board_size) +#define NUM_SHIFT 4 +#define NUM_MASK (0xF << NUM_SHIFT) // 0b11110000 +#define NUM_INC (0x1 << NUM_SHIFT) // 0b00010000 +#define STONE_MASK 3 // 0b00000011 +#define STONE_AT(l) (celldat[(l)] & STONE_MASK) +#define COUNT_AT(l) (celldat[(l)] >> NUM_SHIFT) +#define THE_COORDS(col, row) ((col) + (row)*board_size) // =================================================================== // Variables @@ -70,42 +80,35 @@ extern uint8_t white_count, black_count, ply; void reset_state(const uint8_t new_board_size); void next_ply(void); -enum ACT_RESULT -try_place(const int8_t location, const enum COLOUR colour, - const enum STONE_VARIANT stone); +enum ACT_RESULT try_place(const int8_t location, const enum COLOUR colour, + const enum STONE_VARIANT stone); -enum ACT_RESULT -try_move(const int8_t location, const enum MOVE_DIRECTION direction, - const uint8_t steps, const uint8_t drops[5]); +enum ACT_RESULT try_move(const int8_t location, + const enum MOVE_DIRECTION direction, + const uint8_t steps, const uint8_t drops[5]); -enum WIN_TYPE -check_win(void); +enum WIN_TYPE check_win(void); // ------------------------------------------------------------------- // PTN related -enum PTN_RESULT -parse_place(char *in_ptn, uint8_t *out_location, - enum STONE_VARIANT *out_stone); +enum PTN_RESULT parse_place(char *in_ptn, uint8_t *out_location, + enum STONE_VARIANT *out_stone); -enum PTN_RESULT -parse_move(char *in_ptn, uint8_t *out_location, - enum MOVE_DIRECTION *out_direction, - uint8_t *out_steps, uint8_t out_drops[5]); +enum PTN_RESULT parse_move(char *in_ptn, uint8_t *out_location, + enum MOVE_DIRECTION *out_direction, + uint8_t *out_steps, uint8_t out_drops[5]); -void -generate_place(const uint8_t in_location, - const enum STONE_VARIANT in_stone, char out_ptn[4]); +void generate_place(const uint8_t in_location, + const enum STONE_VARIANT in_stone, char out_ptn[4]); -void -generate_move(const uint8_t in_location, - const enum MOVE_DIRECTION in_direction, - const uint8_t in_steps, const uint8_t in_drops[5], - char out_ptn[10]); +void generate_move(const uint8_t in_location, + const enum MOVE_DIRECTION in_direction, + const uint8_t in_steps, const uint8_t in_drops[5], + char out_ptn[10]); // ------------------------------------------------------------------- // Game driver -enum ACT_RESULT -do_ptn(char *ptn); +enum ACT_RESULT do_ptn(char *ptn); #endif diff --git a/include/tps.c b/include/tps.c index be25c4f..7be0e8d 100644 --- a/include/tps.c +++ b/include/tps.c @@ -8,155 +8,155 @@ enum TPS_RESULT load_tps(char* tps) { - // TODO: Ensure NULL termination? - if (tps == NULL) return TPS_INVALID; - - uint8_t prefix = 0; - // Check if we're likely of the form [TPS "blah"] - if (!strncmp(tps, "[TPS \"", 6)) { - prefix=1; - // Now we can worry about just the TPS part - tps += 6; - } - - // Reset everything - reset_state(board_size); - - // Parse squares, NOTE: We assume that board_size matches TPS size. - int col = 0, row = board_size-1, skip, parsing = 1; - while (parsing) { - switch (*tps) { - case ' ': { - // we're done - parsing = 0; - tps++; TPS_ASSERT_MORE; - break; - } - case 'x': { - // empty squares - tps++; TPS_ASSERT_MORE; - skip = 0; - if (*tps >= '2' && *tps <= '0'+board_size) { - skip = *tps - '1'; - tps++; TPS_ASSERT_MORE; - } else if (*tps != ',' && *tps != '/' && *tps != ' ') { - return TPS_INVALID; - } - col += skip; - if (col >= board_size + 1) return TPS_INVALID; - break; - } - case '/': { - // next row - if (col + 1 != board_size) return TPS_INVALID; - row--; col = 0; - if (row < 0) return TPS_INVALID; - tps++; TPS_ASSERT_MORE; - break; - } - case ',': { - // next column - col++; - if (col >= board_size) return TPS_INVALID; - tps++; TPS_ASSERT_MORE; - break; - } - default: { - const int l = THE_COORDS(col, row); - uint8_t num_read = 0, reading = 1; - // Read in a stack of colours, optionally terminated by an S - // or C to change the top stone type - while (reading) { - switch (*tps) { - // Reading a stone colour - case '2': { - // check next letter to make sure we have the material - tps++; TPS_ASSERT_MORE; - if (*tps == 'C') { - if (black_count & 128) black_count &= 127; - else return TPS_INVALID; - } else if (black_count & 127) { - black_count--; - } else return TPS_INVALID; - colours[l] <<= 1; - celldat[l] += NUM_INC; - colours[l] |= 1; - num_read++; - break; - } - case '1': { - tps++; TPS_ASSERT_MORE; - if (*tps == 'C') { - if (white_count & 128) white_count &= 127; - else return TPS_INVALID; - } else if (white_count & 127) { - white_count--; - } else return TPS_INVALID; - colours[l] <<= 1; - celldat[l] += NUM_INC; - num_read++; - break; - } - case 'S': { - // Have we already read a stone type? - if (STONE_AT(l) != STONE_FLAT) return TPS_INVALID; - celldat[l] |= STONE_STANDING; - tps++; TPS_ASSERT_MORE; - break; - } - case 'C': { - if (STONE_AT(l) != STONE_FLAT) return TPS_INVALID; - celldat[l] |= STONE_CAPSTONE; - tps++; TPS_ASSERT_MORE; - break; - } - case ',': // fall-through - case '/': { - // done here - reading=0; - break; - } - default: return TPS_INVALID; - } - if (num_read > 0xF) return TPS_INVALID; - } - } - } + // TODO: Ensure NULL termination? + if (tps == NULL) return TPS_INVALID; + + uint8_t prefix = 0; + // Check if we're likely of the form [TPS "blah"] + if (!strncmp(tps, "[TPS \"", 6)) { + prefix=1; + // Now we can worry about just the TPS part + tps += 6; + } + + // Reset everything + reset_state(board_size); + + // Parse squares, NOTE: We assume that board_size matches TPS size. + int col = 0, row = board_size-1, skip, parsing = 1; + while (parsing) { + switch (*tps) { + case ' ': { + // we're done + parsing = 0; + tps++; TPS_ASSERT_MORE; + break; + } + case 'x': { + // empty squares + tps++; TPS_ASSERT_MORE; + skip = 0; + if (*tps >= '2' && *tps <= '0'+board_size) { + skip = *tps - '1'; + tps++; TPS_ASSERT_MORE; + } else if (*tps != ',' && *tps != '/' && *tps != ' ') { + return TPS_INVALID; } - - // Now it's time to parse the ply number. First, the active player - if (*tps != '1' && *tps != '2') return TPS_INVALID; - ply += *tps - '1'; + col += skip; + if (col >= board_size + 1) return TPS_INVALID; + break; + } + case '/': { + // next row + if (col + 1 != board_size) return TPS_INVALID; + row--; col = 0; + if (row < 0) return TPS_INVALID; tps++; TPS_ASSERT_MORE; - - // Space - if (*tps != ' ') return TPS_INVALID; + break; + } + case ',': { + // next column + col++; + if (col >= board_size) return TPS_INVALID; tps++; TPS_ASSERT_MORE; - - // Turn number, atoi doesn't detect errors so let's do it ourselves - uint8_t p = 0; - do { - p *= 10; - if (*tps >= '0' && *tps <= '9') { - p += *tps - '0'; - } else return TPS_INVALID; - tps++; - } while ( (prefix && *tps && *tps != '"') || (!prefix && *tps) ); - if (p == 0) return TPS_INVALID; - ply += 2*(p - 1); - - current_colour = (ply & 1) ? C_BLACK : C_WHITE; - if (ply < 2) current_colour = C_BLACK - current_colour; - - if (prefix) { - tps++; TPS_ASSERT_MORE; - if (*tps != ']' ) return TPS_INVALID; - - tps++; - if (*tps != 0) return TPS_INVALID; + break; + } + default: { + const int l = THE_COORDS(col, row); + uint8_t num_read = 0, reading = 1; + // Read in a stack of colours, optionally terminated by an S + // or C to change the top stone type + while (reading) { + switch (*tps) { + // Reading a stone colour + case '2': { + // check next letter to make sure we have the material + tps++; TPS_ASSERT_MORE; + if (*tps == 'C') { + if (black_count & 128) black_count &= 127; + else return TPS_INVALID; + } else if (black_count & 127) { + black_count--; + } else return TPS_INVALID; + colours[l] <<= 1; + celldat[l] += NUM_INC; + colours[l] |= 1; + num_read++; + break; + } + case '1': { + tps++; TPS_ASSERT_MORE; + if (*tps == 'C') { + if (white_count & 128) white_count &= 127; + else return TPS_INVALID; + } else if (white_count & 127) { + white_count--; + } else return TPS_INVALID; + colours[l] <<= 1; + celldat[l] += NUM_INC; + num_read++; + break; + } + case 'S': { + // Have we already read a stone type? + if (STONE_AT(l) != STONE_FLAT) return TPS_INVALID; + celldat[l] |= STONE_STANDING; + tps++; TPS_ASSERT_MORE; + break; + } + case 'C': { + if (STONE_AT(l) != STONE_FLAT) return TPS_INVALID; + celldat[l] |= STONE_CAPSTONE; + tps++; TPS_ASSERT_MORE; + break; + } + case ',': // fall-through + case '/': { + // done here + reading=0; + break; + } + default: return TPS_INVALID; + } + if (num_read > 0xF) return TPS_INVALID; } - - return TPS_OK; + } + } + } + + // Now it's time to parse the ply number. First, the active player + if (*tps != '1' && *tps != '2') return TPS_INVALID; + ply += *tps - '1'; + tps++; TPS_ASSERT_MORE; + + // Space + if (*tps != ' ') return TPS_INVALID; + tps++; TPS_ASSERT_MORE; + + // Turn number, atoi doesn't detect errors so let's do it ourselves + uint8_t p = 0; + do { + p *= 10; + if (*tps >= '0' && *tps <= '9') { + p += *tps - '0'; + } else return TPS_INVALID; + tps++; + } while ( (prefix && *tps && *tps != '"') || (!prefix && *tps) ); + if (p == 0) return TPS_INVALID; + ply += 2*(p - 1); + + current_colour = (ply & 1) ? C_BLACK : C_WHITE; + if (ply < 2) current_colour = C_BLACK - current_colour; + + if (prefix) { + tps++; TPS_ASSERT_MORE; + if (*tps != ']' ) return TPS_INVALID; + + tps++; + if (*tps != 0) return TPS_INVALID; + } + + return TPS_OK; } // =================================================================== @@ -165,53 +165,53 @@ load_tps(char* tps) { void generate_tps(char *out_tps) { - strcpy(out_tps, "[TPS \""); - out_tps += 6; - - for (int8_t row = board_size - 1; row >= 0; row--) { - for (int8_t col = 0; col < board_size; col++) { - const int8_t l = THE_COORDS(col, row); - const uint8_t count = COUNT_AT(l); - if (count) { - colour_stack_t c = colours[l], s = 1<<(count - 1); - for (int k=0; k<count; k++, s >>=1, out_tps++) { - if (c & s) *out_tps = '2'; - else *out_tps = '1'; - } - switch (STONE_AT(l)) { - case STONE_CAPSTONE: { - *out_tps = 'C'; out_tps++; break; - } - case STONE_STANDING: { - *out_tps = 'S'; out_tps++; break; - } - default: break; - } - } else { - int8_t skip = 1; - while (col < board_size && COUNT_AT(l+skip) == 0) { - skip++; - col++; - } - *out_tps = 'x'; out_tps++; - if (skip > 1) { - *out_tps = '0'+skip; out_tps++; - } - } - if (col + 1 < board_size) { - *out_tps = ','; out_tps++; - } - } - if (row > 0) { - *out_tps = '/'; out_tps++; - } + strcpy(out_tps, "[TPS \""); + out_tps += 6; + + for (int8_t row = board_size - 1; row >= 0; row--) { + for (int8_t col = 0; col < board_size; col++) { + const int8_t l = THE_COORDS(col, row); + const uint8_t count = COUNT_AT(l); + if (count) { + colour_stack_t c = colours[l], s = 1<<(count - 1); + for (int k=0; k<count; k++, s >>=1, out_tps++) { + if (c & s) *out_tps = '2'; + else *out_tps = '1'; } - - *out_tps = ' '; out_tps++; - *out_tps = '1' + (ply & 1); out_tps++; - *out_tps = ' '; out_tps++; - - out_tps += sprintf(out_tps, "%d", ply/2 + 1); - - strcpy(out_tps, "\"]"); + switch (STONE_AT(l)) { + case STONE_CAPSTONE: { + *out_tps = 'C'; out_tps++; break; + } + case STONE_STANDING: { + *out_tps = 'S'; out_tps++; break; + } + default: break; + } + } else { + int8_t skip = 1; + while (col < board_size && COUNT_AT(l+skip) == 0) { + skip++; + col++; + } + *out_tps = 'x'; out_tps++; + if (skip > 1) { + *out_tps = '0'+skip; out_tps++; + } + } + if (col + 1 < board_size) { + *out_tps = ','; out_tps++; + } + } + if (row > 0) { + *out_tps = '/'; out_tps++; + } + } + + *out_tps = ' '; out_tps++; + *out_tps = '1' + (ply & 1); out_tps++; + *out_tps = ' '; out_tps++; + + out_tps += sprintf(out_tps, "%d", ply/2 + 1); + + strcpy(out_tps, "\"]"); } diff --git a/include/tt_llcht.c b/include/tt_llcht.c index 60f8ccc..b80da39 100644 --- a/include/tt_llcht.c +++ b/include/tt_llcht.c @@ -1,18 +1,18 @@ /* - This file is part of ct. + This file is part of ct. - 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 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. + 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 ct. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with ct. If not, see <https://www.gnu.org/licenses/>. */ #include "tt_llcht.h" @@ -28,8 +28,8 @@ 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 uint8_t depth, const float value, + const action_t action); // =================================================================== @@ -37,45 +37,45 @@ tt_entry_t * new_ll_node(const uint64_t key, const enum TT_FLAG flag, // =================================================================== int tt_init(void) { - for (uint32_t k=0; k<=TT_LLCHT_SIZE; k++) - table[k] = NULL; - return EXIT_SUCCESS; + for (uint32_t k=0; k<=TT_LLCHT_SIZE; k++) + table[k] = NULL; + return EXIT_SUCCESS; } void tt_free(void) { - tt_entry_t *n, *nn; - for (uint32_t k=0; k<=TT_LLCHT_SIZE; k++) { - n = table[k]; - while (n) { - nn = n->next; - free(n); - n = nn; - } - } + tt_entry_t *n, *nn; + for (uint32_t k=0; k<=TT_LLCHT_SIZE; k++) { + n = table[k]; + while (n) { + nn = n->next; + free(n); + n = nn; + } + } } tt_entry_t *tt_seek(const uint64_t key) { - tt_entry_t *lookup = table[key & TT_LLCHT_SIZE]; - while (lookup && lookup->key != key) - lookup = lookup->next; - return lookup; + tt_entry_t *lookup = table[key & TT_LLCHT_SIZE]; + while (lookup && lookup->key != key) + lookup = lookup->next; + return lookup; } 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; - // TODO: trap - - const uint32_t idx = key & TT_LLCHT_SIZE; - if ((n = table[idx]) != NULL) { - for (; n->next != NULL; n = n->next); - n->next = new; - } else { - table[idx] = new; - } - - return EXIT_SUCCESS; + const uint8_t depth, const float value, + const action_t action) { + tt_entry_t *new = new_ll_node(key, flag, depth, value, action), *n; + // TODO: trap + + const uint32_t idx = key & TT_LLCHT_SIZE; + if ((n = table[idx]) != NULL) { + for (; n->next != NULL; n = n->next); + n->next = new; + } else { + table[idx] = new; + } + + return EXIT_SUCCESS; } // =================================================================== @@ -83,15 +83,15 @@ 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) { - tt_entry_t *new = malloc(sizeof(struct tt_node_s)); - // TODO: trap errno - new->key = key; - new->next = NULL; - new->flag = flag; - new->depth = depth; - new->value = value; - new->action = action; - return new; + 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; + 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..40d8bdb 100644 --- a/include/tt_llcht.h +++ b/include/tt_llcht.h @@ -1,18 +1,18 @@ /* - This file is part of ct. + This file is part of ct. - 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 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. + 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 ct. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with ct. If not, see <https://www.gnu.org/licenses/>. */ #ifndef TT_LLCHT_H @@ -30,12 +30,12 @@ enum TT_FLAG { TT_EXACT, TT_LOWERBOUND, TT_UPPERBOUND }; typedef struct tt_node_s { - uint64_t key; - struct tt_node_s *next; - enum TT_FLAG flag; - uint8_t depth; - float value; - action_t action; + uint64_t key; + struct tt_node_s *next; + enum TT_FLAG flag; + uint8_t depth; + float value; + action_t action; } tt_entry_t; // =================================================================== @@ -54,7 +54,7 @@ void tt_free(void); 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 uint8_t depth, const float value, + const action_t action); #endif diff --git a/include/weights.h b/include/weights.h index eff0a68..ac5ede8 100644 --- a/include/weights.h +++ b/include/weights.h @@ -1,18 +1,18 @@ /* - This file is part of ct. + This file is part of ct. - 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 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. + 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 ct. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with ct. If not, see <https://www.gnu.org/licenses/>. */ #define KERN_SIZE 3 diff --git a/include/xorshift64.c b/include/xorshift64.c index 6fd8577..0a68c71 100644 --- a/include/xorshift64.c +++ b/include/xorshift64.c @@ -1,18 +1,18 @@ /* - This file is part of ct. + This file is part of ct. - 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 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. + 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 ct. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with ct. If not, see <https://www.gnu.org/licenses/>. */ #include "xorshift64.h" diff --git a/include/xorshift64.h b/include/xorshift64.h index 54392a0..b9ba97a 100644 --- a/include/xorshift64.h +++ b/include/xorshift64.h @@ -1,18 +1,18 @@ /* - This file is part of ct. + This file is part of ct. - 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 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. + 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 ct. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with ct. If not, see <https://www.gnu.org/licenses/>. */ #ifndef XORSHIFT_H @@ -22,11 +22,11 @@ extern uint64_t xors; -#define XORSHIFT64 { \ - xors ^= xors >> 12; \ - xors ^= xors << 25; \ - xors ^= xors >> 27; \ - } +#define XORSHIFT64 { \ + xors ^= xors >> 12; \ + xors ^= xors << 25; \ + xors ^= xors >> 27; \ + } #define RANDOM64 (xors*0x2545F4914F6CDD1D) #define RANDOM32 ((uint32_t)RANDOM64) diff --git a/include/zobrist.c b/include/zobrist.c index 48a115b..1fdd8a9 100644 --- a/include/zobrist.c +++ b/include/zobrist.c @@ -1,18 +1,18 @@ /* - This file is part of ct. + This file is part of ct. - 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 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. + 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 ct. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with ct. If not, see <https://www.gnu.org/licenses/>. */ #include "zobrist.h" @@ -28,34 +28,34 @@ static uint64_t *zobrist; // =================================================================== int zobrist_init(void) { - if (zobrist != NULL) return EXIT_FAILURE; + if (zobrist != NULL) return EXIT_FAILURE; - zobrist = malloc(sizeof(uint64_t)*board_size*board_size*(15*2*3)); - // TODO: trap errno + zobrist = malloc(sizeof(uint64_t)*board_size*board_size*(15*2*3)); + // TODO: trap errno - for (int k=0; k<board_size*board_size*(15*2*3); k++) { - XORSHIFT64; - zobrist[k] = RANDOM64; - } + for (int k=0; k<board_size*board_size*(15*2*3); k++) { + XORSHIFT64; + zobrist[k] = RANDOM64; + } - return EXIT_SUCCESS; + return EXIT_SUCCESS; } void zobrist_free(void) { - if (zobrist != NULL) { - free(zobrist); - zobrist = NULL; - } + if (zobrist != NULL) { + free(zobrist); + zobrist = NULL; + } } uint64_t zobrist_compute(void) { - uint64_t hash = 0; - for (uint8_t l=0; l<board_size*board_size; l++) { - colour_stack_t c = colours[l]; - const uint8_t count = COUNT_AT(l); - enum STONE_VARIANT s = STONE_AT(l); - for (uint8_t h=0; h<count; h++, c >>= 1) - hash ^= zobrist[l*(15*2*3)+h*2*3+(c&1)*3+s]; - } - return hash; + uint64_t hash = 0; + for (uint8_t l=0; l<board_size*board_size; l++) { + colour_stack_t c = colours[l]; + const uint8_t count = COUNT_AT(l); + enum STONE_VARIANT s = STONE_AT(l); + for (uint8_t h=0; h<count; h++, c >>= 1) + hash ^= zobrist[l*(15*2*3)+h*2*3+(c&1)*3+s]; + } + return hash; } diff --git a/include/zobrist.h b/include/zobrist.h index be657fc..be93910 100644 --- a/include/zobrist.h +++ b/include/zobrist.h @@ -1,18 +1,18 @@ /* - This file is part of ct. + This file is part of ct. - 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 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. + 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 ct. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with ct. If not, see <https://www.gnu.org/licenses/>. */ #include <xorshift64.h> diff --git a/src/ct1986.c b/src/ct1986.c index 93dd7b9..f9046ce 100644 --- a/src/ct1986.c +++ b/src/ct1986.c @@ -1,21 +1,21 @@ /* - ct1986, an interface to the ct library designed to be embedded on - a Raspberry Pi Zero + ct1986, an interface to the ct library designed to be embedded on + a Raspberry Pi Zero - Copyright (C) 2021, tslil clingman + Copyright (C) 2021, tslil clingman - 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 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. + 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 this program. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ #include <stdlib.h> @@ -33,92 +33,92 @@ static char *gamelog = 0; static void new_game(uint8_t size) { - reset_state(size); - lcd_printf_line(L_SCROLL, "New 5s game @ D%d", - negamax_search_depth); - if (gamelog) gamelog = realloc(gamelog, sizeof(char)); - else gamelog = malloc(sizeof(char)); - gamelog[0] = 0; + reset_state(size); + lcd_printf_line(L_SCROLL, "New 5s game @ D%d", + negamax_search_depth); + if (gamelog) gamelog = realloc(gamelog, sizeof(char)); + else gamelog = malloc(sizeof(char)); + gamelog[0] = 0; } static int append_to_gamelog(const char *line, const uint8_t win_line) { - // I _could_ dynamically compute the size but ... don't let - // `perfect' be the enemy of `good' ? - - if (gamelog == NULL) return EXIT_FAILURE; - - char prepend[8]; - - if (win_line) { - prepend[0] = '\n'; - prepend[1] = 0; - } else if (ply & 1) { - snprintf(prepend, 7, "%s%d. ", - (ply == 1) ? "" : "\n", ply/2+1); - } else { - strcpy(prepend, " "); - } - // Make room for this line - gamelog = realloc(gamelog, - strlen(gamelog) - + strlen(prepend) - + strlen(line) + 1); - // TODO: trap errno - strcat(gamelog, prepend); - strcat(gamelog, line); - - return EXIT_SUCCESS; + // I _could_ dynamically compute the size but ... don't let + // `perfect' be the enemy of `good' ? + + if (gamelog == NULL) return EXIT_FAILURE; + + char prepend[8]; + + if (win_line) { + prepend[0] = '\n'; + prepend[1] = 0; + } else if (ply & 1) { + snprintf(prepend, 7, "%s%d. ", + (ply == 1) ? "" : "\n", ply/2+1); + } else { + strcpy(prepend, " "); + } + // Make room for this line + gamelog = realloc(gamelog, + strlen(gamelog) + + strlen(prepend) + + strlen(line) + 1); + // TODO: trap errno + strcat(gamelog, prepend); + strcat(gamelog, line); + + return EXIT_SUCCESS; } static void end_game(char *line, char *win) { - append_to_gamelog(line, 0); - append_to_gamelog(win, 1); - lcd_printf_line(L_SCROLL, "Game over: %s", win); + append_to_gamelog(line, 0); + append_to_gamelog(win, 1); + lcd_printf_line(L_SCROLL, "Game over: %s", win); } static int handle_turn(char *line) { - // Track win state - uint8_t new_win = (won == 0xFF); - switch (do_ptn(line)) { - // Errors - case ACT_INVALID_PTN: { - lcd_put_line(L_SCROLL, "Invalid PTN."); - break; - } - case ACT_ILLEGAL: { - lcd_put_line(L_SCROLL, "Illegal ply."); - break; } - case ACT_OVERFLOW: { - lcd_put_line(L_SCROLL, "Overflow."); - break; - } - // Game has ended - case GAME_END: { - // Did it end this turn? - if (new_win) { - switch (won) { - case WIN_DRAW: { end_game(line,"1/2-1/2"); break; } - case WIN_FLAT_BLACK: { end_game(line,"0-F"); break; } - case WIN_FLAT_WHITE: { end_game(line,"F-0"); break; } - case WIN_ROAD_BLACK: { end_game(line,"0-R"); break; } - case WIN_ROAD_WHITE: { end_game(line,"R-0"); break; } - } - return EXIT_SUCCESS; - } else { - lcd_put_line(L_SCROLL, "Game over."); - break; - } - } - // Valid, append to game log - default: { - append_to_gamelog(line, 0); - return EXIT_SUCCESS; - } + // Track win state + uint8_t new_win = (won == 0xFF); + switch (do_ptn(line)) { + // Errors + case ACT_INVALID_PTN: { + lcd_put_line(L_SCROLL, "Invalid PTN."); + break; + } + case ACT_ILLEGAL: { + lcd_put_line(L_SCROLL, "Illegal ply."); + break; } + case ACT_OVERFLOW: { + lcd_put_line(L_SCROLL, "Overflow."); + break; + } + // Game has ended + case GAME_END: { + // Did it end this turn? + if (new_win) { + switch (won) { + case WIN_DRAW: { end_game(line,"1/2-1/2"); break; } + case WIN_FLAT_BLACK: { end_game(line,"0-F"); break; } + case WIN_FLAT_WHITE: { end_game(line,"F-0"); break; } + case WIN_ROAD_BLACK: { end_game(line,"0-R"); break; } + case WIN_ROAD_WHITE: { end_game(line,"R-0"); break; } } - return EXIT_FAILURE; + return EXIT_SUCCESS; + } else { + lcd_put_line(L_SCROLL, "Game over."); + break; + } + } + // Valid, append to game log + default: { + append_to_gamelog(line, 0); + return EXIT_SUCCESS; + } + } + return EXIT_FAILURE; } @@ -127,53 +127,53 @@ static uint32_t perc; inline void negamax_display_progress(const uint8_t depth, const uint32_t length) { - if (depth == negamax_search_depth) { - lcd_printf_line(L_OVERWRITE, "Computing: %d%%", - (++perc*100)/length); - } + if (depth == negamax_search_depth) { + lcd_printf_line(L_OVERWRITE, "Computing: %d%%", + (++perc*100)/length); + } } static int negamax_turn() { - // Prepare progress bar - perc = 0; - lcd_put_line(L_SCROLL, "Computing: 0%"); - // Run the minimax - float minimax = negamax_generate(); - // Failed to find a move? - if (minimax < -infty) { - lcd_printf_line(L_SCROLL, "%s concedes!", - (ply & 1) ? "Black" : "White"); - return EXIT_FAILURE; - } else { - lcd_printf_line(L_SCROLL, "%s: %s", - (ply & 1) ? "Black" : "White", - negamax_ptn); - return handle_turn(negamax_ptn); - } + // Prepare progress bar + perc = 0; + lcd_put_line(L_SCROLL, "Computing: 0%"); + // Run the minimax + float minimax = negamax_generate(); + // Failed to find a move? + if (minimax < -infty) { + lcd_printf_line(L_SCROLL, "%s concedes!", + (ply & 1) ? "Black" : "White"); + return EXIT_FAILURE; + } else { + lcd_printf_line(L_SCROLL, "%s: %s", + (ply & 1) ? "Black" : "White", + negamax_ptn); + return handle_turn(negamax_ptn); + } } static void do_game_log(void) { - lcd_put_line(L_SCROLL, "TODO!"); + lcd_put_line(L_SCROLL, "TODO!"); } static int input_is_not_turn(const char *line) { - switch (line[0]) { - case 'l': { do_game_log(); break; } - case 'n': { new_game(5); break; } - case 'D': { - negamax_search_depth = line[1] - '0'; - lcd_printf_line(L_SCROLL, "Search depth: %d", - negamax_search_depth); - break; - } - case 'B': { human = 1; new_game(5); break; } - case 'W': { human = 0; new_game(5); break; } - default: return EXIT_FAILURE; - } - return EXIT_SUCCESS; + switch (line[0]) { + case 'l': { do_game_log(); break; } + case 'n': { new_game(5); break; } + case 'D': { + negamax_search_depth = line[1] - '0'; + lcd_printf_line(L_SCROLL, "Search depth: %d", + negamax_search_depth); + break; + } + case 'B': { human = 1; new_game(5); break; } + case 'W': { human = 0; new_game(5); break; } + default: return EXIT_FAILURE; + } + return EXIT_SUCCESS; } const char* license = "ct1986, an interface to the ct library designed to be embedded on a Raspberry Pi Zero\n\ @@ -187,85 +187,85 @@ static char line[LINE_BUFF_LEN+1]; static int poll_input(void) { - char c, *prompt; - int idx = 0, polling = 1; - - if (ply & 1) prompt = "Black: "; - else prompt = "White: "; - - lcd_put_line(L_SCROLL, prompt); - - line[0] = 0; - while (polling) { - lcd_printf_line(L_OVERWRITE, "%s%s", prompt, line); - c = getchar(); - switch (c) { - case 0x7F: { - if (idx>0) idx--; - line[idx] = 0; - break; - } - case 0xFF: // fall-through - case '\r': // fall-through - case '\n': { - polling = 0; - break; - } - default: { - if (idx+1<LINE_BUFF_LEN) { - line[idx] = c; - line[++idx] = 0; - } - break; - } - } + char c, *prompt; + int idx = 0, polling = 1; + + if (ply & 1) prompt = "Black: "; + else prompt = "White: "; + + lcd_put_line(L_SCROLL, prompt); + + line[0] = 0; + while (polling) { + lcd_printf_line(L_OVERWRITE, "%s%s", prompt, line); + c = getchar(); + switch (c) { + case 0x7F: { + if (idx>0) idx--; + line[idx] = 0; + break; + } + case 0xFF: // fall-through + case '\r': // fall-through + case '\n': { + polling = 0; + break; + } + default: { + if (idx+1<LINE_BUFF_LEN) { + line[idx] = c; + line[++idx] = 0; } - return idx; + break; + } + } + } + return idx; } int main(int argc, char **argv) { - (void)(argc); - (void)(argv); - - puts(license); - - if (lcd_begin() != EXIT_SUCCESS) - return EXIT_FAILURE; - - initscr(); - - negamax_search_depth = 3; - new_game(5); - negamax_init(5); - - human = 0; - for (int playing = 1; playing;) { - while (human == 0) { - lcd_set_blink(); - if (poll_input() > 0) { - if (input_is_not_turn(line)) { - int r = handle_turn(line); - if (r == EXIT_SUCCESS && won == 0xFF) { - human = 1; - } - } - } else { - playing = 0; - human = 1; - } - } - lcd_stop_blink(); - if (playing) { - negamax_turn(); - human = 0; - } + (void)(argc); + (void)(argv); + + puts(license); + + if (lcd_begin() != EXIT_SUCCESS) + return EXIT_FAILURE; + + initscr(); + + negamax_search_depth = 3; + new_game(5); + negamax_init(5); + + human = 0; + for (int playing = 1; playing;) { + while (human == 0) { + lcd_set_blink(); + if (poll_input() > 0) { + if (input_is_not_turn(line)) { + int r = handle_turn(line); + if (r == EXIT_SUCCESS && won == 0xFF) { + human = 1; + } } - - free(gamelog); - negamax_free(); - - lcd_end(); - endwin(); - - return EXIT_SUCCESS; + } else { + playing = 0; + human = 1; + } + } + lcd_stop_blink(); + if (playing) { + negamax_turn(); + human = 0; + } + } + + free(gamelog); + negamax_free(); + + lcd_end(); + endwin(); + + return EXIT_SUCCESS; } @@ -1,32 +1,32 @@ /* - ctlm, a line mode interface to the ct library + ctlm, a line mode interface to the ct library - Copyright (C) 2021, tslil clingman + Copyright (C) 2021, tslil clingman - 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 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. + 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 this program. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ -#include <stdlib.h> #include <stdio.h> +#include <stdlib.h> #include <string.h> +#include <negamax.h> #include <tak.h> #include <tps.h> -#include <negamax.h> static const char *blk = "\033[41m", *wht = "\033[44m"; -static const char *und = "\033[4m", *rst = "\033[0m"; +static const char *und = "\033[4m", *rst = "\033[0m"; #define SQUARE_W 5 #define SQUARE_H 3 @@ -35,472 +35,489 @@ static const char *und = "\033[4m", *rst = "\033[0m"; #define CHAR_STN '/' #define CHAR_CAP '*' -static void -put_stone(const enum STONE_VARIANT stone, const enum COLOUR colour, - const uint8_t top, const uint8_t beyond_carry_limit) { - if (beyond_carry_limit) { - fputs(und,stdout); - } else { - if (colour == C_BLACK) fputs(blk, stdout); - else fputs(wht,stdout); - } - if (top) { - switch (stone) { - case STONE_FLAT: putchar(CHAR_FLT); break; - case STONE_STANDING: putchar(CHAR_STN); break; - case STONE_CAPSTONE: putchar(CHAR_CAP); break; - } - } else { - putchar( (colour == C_BLACK) ? 'B' : 'W' ); - } - fputs(rst,stdout); +static void put_stone(const enum STONE_VARIANT stone, const enum COLOUR colour, + const uint8_t top, const uint8_t beyond_carry_limit) { + if (beyond_carry_limit) { + fputs(und, stdout); + } else { + if (colour == C_BLACK) + fputs(blk, stdout); + else + fputs(wht, stdout); + } + if (top) { + switch (stone) { + case STONE_FLAT: + putchar(CHAR_FLT); + break; + case STONE_STANDING: + putchar(CHAR_STN); + break; + case STONE_CAPSTONE: + putchar(CHAR_CAP); + break; + } + } else { + putchar((colour == C_BLACK) ? 'B' : 'W'); + } + fputs(rst, stdout); } -static void -print_cell_line(const uint8_t line, - const uint8_t col, const uint8_t row) { - - const uint8_t location = THE_COORDS(col, row), - stack_size = COUNT_AT(location); - - uint8_t idx; - for (uint8_t k = 0; k < SQUARE_W; k++) { - idx = line + k*SQUARE_H; - // Are we in the last column to be displayed? - if ((k+1)*SQUARE_H > stack_size) { - // If so, then if we can't fill it offset the starting line so - // that it fills from the bottom up instead of the top down - if (line < (k+1)*SQUARE_H - stack_size ) { - // skip these lines - idx = 0xFF; - } else { - // offset back - idx -= (k+1)*SQUARE_H - stack_size; - } - } - if (idx < stack_size) { - put_stone(STONE_AT(location), - (colours[location] & (1 << idx)) ? C_BLACK : C_WHITE, - idx == 0, idx >= board_size); - } else { - putchar(' '); - } - } +static void print_cell_line(const uint8_t line, const uint8_t col, + const uint8_t row) { + + const uint8_t location = THE_COORDS(col, row), + stack_size = COUNT_AT(location); + + uint8_t idx; + for (uint8_t k = 0; k < SQUARE_W; k++) { + idx = line + k * SQUARE_H; + // Are we in the last column to be displayed? + if ((k + 1) * SQUARE_H > stack_size) { + // If so, then if we can't fill it offset the starting line so + // that it fills from the bottom up instead of the top down + if (line < (k + 1) * SQUARE_H - stack_size) { + // skip these lines + idx = 0xFF; + } else { + // offset back + idx -= (k + 1) * SQUARE_H - stack_size; + } + } + if (idx < stack_size) { + put_stone(STONE_AT(location), + (colours[location] & (1 << idx)) ? C_BLACK : C_WHITE, idx == 0, + idx >= board_size); + } else { + putchar(' '); + } + } } // It takes board_size*(SQUARE_H+1)+1 lines to print the board, they // may be requested in any order and at any time -static void -print_board_line(const uint8_t line) { - const uint8_t mod = line % (SQUARE_H + 1), - row = board_size - line/(SQUARE_H + 1) - 1; - - // Print leader, either row number if half-way through square or - // padding spaces otherwise - if (mod == (SQUARE_H + 1)/2 ) printf("%d. ",row + 1); - else fputs(" ",stdout); - - // Top and bottom of squares receive borders - if (mod == 0) { - for (uint8_t x = 0; x < board_size; x++) { - putchar('+'); - for (uint8_t k = 0; k < SQUARE_W; k++) putchar('-'); - } - puts("+"); - } else { - // Interior of board should be filled by borders and pieces - if (line < board_size*(SQUARE_H+1)) { - for (uint8_t x = 0; x < board_size; x++) { - putchar('|'); - print_cell_line(mod - 1 , x, row); - } - puts("|"); - } else { - // Bottom of board has column markers - for (uint8_t x = 0; x < board_size; x++) { - for (uint8_t k = 0; k <= SQUARE_W/2; k++) putchar(' '); - printf("%c.",x+'a'); - for (uint8_t k = 0; k < SQUARE_W-SQUARE_W/2-2; k++) putchar(' '); - } - putchar('\n'); - } - } +static void print_board_line(const uint8_t line) { + const uint8_t mod = line % (SQUARE_H + 1), + row = board_size - line / (SQUARE_H + 1) - 1; + + // Print leader, either row number if half-way through square or + // padding spaces otherwise + if (mod == (SQUARE_H + 1) / 2) + printf("%d. ", row + 1); + else + fputs(" ", stdout); + + // Top and bottom of squares receive borders + if (mod == 0) { + for (uint8_t x = 0; x < board_size; x++) { + putchar('+'); + for (uint8_t k = 0; k < SQUARE_W; k++) + putchar('-'); + } + puts("+"); + } else { + // Interior of board should be filled by borders and pieces + if (line < board_size * (SQUARE_H + 1)) { + for (uint8_t x = 0; x < board_size; x++) { + putchar('|'); + print_cell_line(mod - 1, x, row); + } + puts("|"); + } else { + // Bottom of board has column markers + for (uint8_t x = 0; x < board_size; x++) { + for (uint8_t k = 0; k <= SQUARE_W / 2; k++) + putchar(' '); + printf("%c.", x + 'a'); + for (uint8_t k = 0; k < SQUARE_W - SQUARE_W / 2 - 2; k++) + putchar(' '); + } + putchar('\n'); + } + } } // Simple wrapper to print the whole board in one go -static void -print_board(void) { - for (uint8_t k = 0; k<board_size*(SQUARE_H+1)+2; k++) { - print_board_line(k); - } +static void print_board(void) { + for (uint8_t k = 0; k < board_size * (SQUARE_H + 1) + 2; k++) { + print_board_line(k); + } } // Print the contents of a single square -static void -print_square(const uint8_t col, const uint8_t row) { - if (row < board_size && col < board_size) { - printf("%c%c: ",'a'+col,'1'+row); - const uint8_t stack_size = COUNT_AT(THE_COORDS(col, row)); - if (stack_size > 0) { - uint8_t mask = 1 << (stack_size - 1); - for (uint8_t k = 0; k < stack_size; k++, mask >>= 1) { - put_stone(STONE_AT(THE_COORDS(col, row)), - (colours[THE_COORDS(col, row)] & mask) ? C_BLACK : C_WHITE, - k+1 == stack_size, - stack_size-k-1 >= board_size); - } - puts(" <-- top"); - } else { - puts("(empty)"); - } - } else { - printf("Requested square not on board (%dx%d).\n",board_size,board_size); - } +static void print_square(const uint8_t col, const uint8_t row) { + if (row < board_size && col < board_size) { + printf("%c%c: ", 'a' + col, '1' + row); + const uint8_t stack_size = COUNT_AT(THE_COORDS(col, row)); + if (stack_size > 0) { + uint8_t mask = 1 << (stack_size - 1); + for (uint8_t k = 0; k < stack_size; k++, mask >>= 1) { + put_stone(STONE_AT(THE_COORDS(col, row)), + (colours[THE_COORDS(col, row)] & mask) ? C_BLACK : C_WHITE, + k + 1 == stack_size, stack_size - k - 1 >= board_size); + } + puts(" <-- top"); + } else { + puts("(empty)"); + } + } else { + printf("Requested square not on board (%dx%d).\n", board_size, board_size); + } } -static void -print_info(void) { - printf("Turn: %2d, %s%s%s%s\n", - ply/2 + 1, - (ply & 1) ? blk : wht, - (ply & 1) ? "Black" : "White", - rst, - (ply < 2) ? " (counter-play start)" : ""); - printf("Flats/Caps remaining: %s%02d/%d%s, %s%02d/%d%s\n", - wht, white_count & 127, white_count >> 7, rst, - blk, black_count & 127, black_count >> 7, rst); +static void print_info(void) { + printf("Turn: %2d, %s%s%s%s\n", ply / 2 + 1, (ply & 1) ? blk : wht, + (ply & 1) ? "Black" : "White", rst, + (ply < 2) ? " (counter-play start)" : ""); + printf("Flats/Caps remaining: %s%02d/%d%s, %s%02d/%d%s\n", wht, + white_count & 127, white_count >> 7, rst, blk, black_count & 127, + black_count >> 7, rst); } static int human; static char *gamelog = NULL; static uint8_t auto_board = 0xFF, auto_info = 0xFF; -static int -append_to_gamelog(const char *line, const uint8_t win_line) { - // I _could_ dynamically compute the size but ... don't let - // `perfect' be the enemy of `good' ? - - if (gamelog == NULL) return EXIT_FAILURE; - - char prepend[8]; - - if (win_line) { - prepend[0] = '\n'; - prepend[1] = 0; - } else if (ply & 1) { - snprintf(prepend, 7, "%s%d. ", - (ply == 1) ? "" : "\n", ply/2+1); - } else { - strcpy(prepend, " "); - } - // Make room for this line - gamelog = realloc(gamelog, - strlen(gamelog) - + strlen(prepend) - + strlen(line) + 1); - // TODO: trap errno - strcat(gamelog, prepend); - strcat(gamelog, line); - - return EXIT_SUCCESS; +static int append_to_gamelog(const char *line, const uint8_t win_line) { + // I _could_ dynamically compute the size but ... don't let + // `perfect' be the enemy of `good' ? + + if (gamelog == NULL) + return EXIT_FAILURE; + + char prepend[8]; + + if (win_line) { + prepend[0] = '\n'; + prepend[1] = 0; + } else if (ply & 1) { + snprintf(prepend, 7, "%s%d. ", (ply == 1) ? "" : "\n", ply / 2 + 1); + } else { + strcpy(prepend, " "); + } + // Make room for this line + gamelog = + realloc(gamelog, strlen(gamelog) + strlen(prepend) + strlen(line) + 1); + // TODO: trap errno + strcat(gamelog, prepend); + strcat(gamelog, line); + + return EXIT_SUCCESS; } -static void -end_game(char *line, char *win) { - append_to_gamelog(line, 0); - append_to_gamelog(win, 1); - print_board(); - puts("Game over:"); - puts(gamelog); - putchar('\n'); +static void end_game(char *line, char *win) { + append_to_gamelog(line, 0); + append_to_gamelog(win, 1); + print_board(); + puts("Game over:"); + puts(gamelog); + putchar('\n'); } -static int -handle_turn(char *line) { - // Track win state - uint8_t new_win = (won == 0xFF); - switch (do_ptn(line)) { - // Errors - case ACT_INVALID_PTN: { - puts("Invalid PTN."); - return EXIT_FAILURE; - } - case ACT_ILLEGAL: { - puts("Illegal action."); - return EXIT_FAILURE; - } - case ACT_OVERFLOW: { - puts("Move would cause internal overflow, select another."); - return EXIT_FAILURE; - } - // Game has ended - case GAME_END: { - // Did it end this turn? - if (new_win) { - switch (won) { - case WIN_DRAW: { end_game(line,"1/2-1/2"); break; } - case WIN_FLAT_BLACK: { end_game(line,"0-F"); break; } - case WIN_FLAT_WHITE: { end_game(line,"F-0"); break; } - case WIN_ROAD_BLACK: { end_game(line,"0-R"); break; } - case WIN_ROAD_WHITE: { end_game(line,"R-0"); break; } - } - } - puts("Enter `new' to play again."); - if (! new_win) return EXIT_FAILURE; - break; - } - // Valid, append to game log - case ACT_OK: { - append_to_gamelog(line, 0); - if (auto_board) print_board(); - if (auto_info) print_info(); - break; - } +static int handle_turn(char *line) { + // Track win state + uint8_t new_win = (won == 0xFF); + switch (do_ptn(line)) { + // Errors + case ACT_INVALID_PTN: { + puts("Invalid PTN."); + return EXIT_FAILURE; + } + case ACT_ILLEGAL: { + puts("Illegal action."); + return EXIT_FAILURE; + } + case ACT_OVERFLOW: { + puts("Move would cause internal overflow, select another."); + return EXIT_FAILURE; + } + // Game has ended + case GAME_END: { + // Did it end this turn? + if (new_win) { + switch (won) { + case WIN_DRAW: { + end_game(line, "1/2-1/2"); + break; + } + case WIN_FLAT_BLACK: { + end_game(line, "0-F"); + break; + } + case WIN_FLAT_WHITE: { + end_game(line, "F-0"); + break; + } + case WIN_ROAD_BLACK: { + end_game(line, "0-R"); + break; + } + case WIN_ROAD_WHITE: { + end_game(line, "R-0"); + break; + } } - return EXIT_SUCCESS; + } + puts("Enter `new' to play again."); + if (!new_win) + return EXIT_FAILURE; + break; + } + // Valid, append to game log + case ACT_OK: { + append_to_gamelog(line, 0); + if (auto_board) + print_board(); + if (auto_info) + print_info(); + break; + } + } + return EXIT_SUCCESS; } -static void -new_game(uint8_t size) { - reset_state(size); - printf("New %dx%d game! negamax at search depth %d.\n", - size, size, negamax_search_depth); - if (gamelog) gamelog = realloc(gamelog, sizeof(char)); - else gamelog = malloc(sizeof(char)); - gamelog[0] = 0; +static void new_game(uint8_t size) { + reset_state(size); + printf("New %dx%d game! negamax at search depth %d.\n", size, size, + negamax_search_depth); + if (gamelog) + gamelog = realloc(gamelog, sizeof(char)); + else + gamelog = malloc(sizeof(char)); + gamelog[0] = 0; } -static int -load_ptn(const char* fn) { - FILE *fh = NULL; - - fh = fopen(fn, "r"); - if (fh == NULL) return EXIT_FAILURE; - - int space1, space2; - enum ACT_RESULT r; - - ssize_t read; - size_t alloc_size; - char *line = NULL; - while ((read = getline(&line, &alloc_size, fh)) != -1) { - if (read && line[0] <= '9' && line[0] >= '0') { - // Trim trailing \n - line[read-1] = 0; - // Find first separator - space1 = 0; - while (space1 < read && line[space1++] != ' '); - // If still on line - if (space1 < read) { - // Find next separator or end of line, either way mark the split - space2 = space1; - while (space2 < read && line[space2] != ' ') space2++; - line[space2] = 0; - // Try the first piece we found - r = handle_turn(line+space1); - if (r) { - printf("Error on: %s\n", line+space1); - break; - } - // If there's a second piece, try it - if (space2 + 1 < read) { - r = handle_turn(line+space2+1); - if (r) { - printf("Error on: %s", line+space2+1); - break; - } - } else { - break; - } - } - } - } - - if (line) free(line); - fclose(fh); - - return EXIT_SUCCESS; +static int load_ptn(const char *fn) { + FILE *fh = NULL; + + fh = fopen(fn, "r"); + if (fh == NULL) + return EXIT_FAILURE; + + int space1, space2; + enum ACT_RESULT r; + + ssize_t read; + size_t alloc_size; + char *line = NULL; + while ((read = getline(&line, &alloc_size, fh)) != -1) { + if (read && line[0] <= '9' && line[0] >= '0') { + // Trim trailing \n + line[read - 1] = 0; + // Find first separator + space1 = 0; + while (space1 < read && line[space1++] != ' ') + ; + // If still on line + if (space1 < read) { + // Find next separator or end of line, either way mark the split + space2 = space1; + while (space2 < read && line[space2] != ' ') + space2++; + line[space2] = 0; + // Try the first piece we found + r = handle_turn(line + space1); + if (r) { + printf("Error on: %s\n", line + space1); + break; + } + // If there's a second piece, try it + if (space2 + 1 < read) { + r = handle_turn(line + space2 + 1); + if (r) { + printf("Error on: %s", line + space2 + 1); + break; + } + } else { + break; + } + } + } + } + + if (line) + free(line); + fclose(fh); + + return EXIT_SUCCESS; } static float num_check, progress; static uint8_t old_depth; // Set up output function for negamax -inline void -negamax_display_progress(const uint8_t cur_depth, - const uint8_t init_depth, - const uint32_t length) { - num_check += 1; - if (cur_depth == init_depth) { - if (init_depth != old_depth) { - old_depth = init_depth; - progress = 0; - } - progress++; - printf("\x1B[0G\x1B[KComputing: %.0f/%d @ D%d", - progress, length, init_depth); - fflush(stdout); - } +inline void negamax_display_progress(const uint8_t cur_depth, + const uint8_t init_depth, + const uint32_t length) { + num_check += 1; + if (cur_depth == init_depth) { + if (init_depth != old_depth) { + old_depth = init_depth; + progress = 0; + } + progress++; + printf("\x1B[0G\x1B[KComputing: %.0f/%d @ D%d", progress, length, + init_depth); + fflush(stdout); + } } -static int -negamax_turn(void) { - if (won == 0xFF) { - // Run the minimax - num_check = 0; progress = 0; old_depth = 0; - float minimax = negamax_generate(); - putchar('\n'); - // Failed to find a non-losing move? - if (minimax <= -infty) puts("Opponent concedes!"); - printf("Result: %s (%.2f, checked %.1e)\n", - negamax_ptn, - minimax*100.0, - num_check); - return handle_turn(negamax_ptn); - } else { - return EXIT_FAILURE; - } +static int negamax_turn(void) { + if (won == 0xFF) { + // Run the minimax + num_check = 0; + progress = 0; + old_depth = 0; + float minimax = negamax_generate(); + putchar('\n'); + // Failed to find a non-losing move? + if (minimax <= -infty) + puts("Opponent concedes!"); + printf("Result: %s (%.2f, checked %.1e)\n", negamax_ptn, minimax * 100.0, + num_check); + return handle_turn(negamax_ptn); + } else { + return EXIT_FAILURE; + } } -static int -input_is_not_turn(const char *line) { - if (!strcmp(line,"help")) { - puts("Valid commands: auto (board|info), board, depth [0-9], eval,\ - help, info, load <file.ptn>, log, new, play (b|w), self-play, square\ - <col><row>, tps, <PTN>."); - } else if (!strcmp(line,"board")) { - print_board(); - } else if (!strcmp(line,"info")) { - print_info(); - } else if (!strcmp(line,"eval")) { - float eval = cnn1986_evaluate_black_win()*100; - if (ply & 1) { - printf("Black heuristic chance: %s%.2f%s\n", - blk, eval, rst); - } else { - printf("White heruistic chance: %s%.2f%s\n", - wht, -eval, rst); - } - } else if (!strcmp(line,"log")) { - puts(gamelog); - } else if (!strcmp(line,"new")) { - new_game(5); - } else if (!strcmp(line,"tps")) { - char buf[1000]; - generate_tps(buf); - puts(buf); - } else if (!strcmp(line,"self-play")) { - while (negamax_turn() == 0); - } else if (!strncmp(line,"depth",5)) { - if (strnlen(line,7) == 7 && line[6] >= '0' && line[6] <= '9') { - negamax_search_depth = line[6] - '0'; - printf("New search depth: %d.\n", - negamax_search_depth); - } else { - puts("Usage: depth [0-9]."); - } - } else if (!strncmp(line,"load",4)) { - if (strnlen(line,6) >= 6) { - if (load_ptn(line+5)) { - printf("Errors in file %s\n",line); - } - } else { - puts("Usage: load <file.ptn>."); - } - } else if (!strncmp(line,"auto",4)) { - if (!strcmp(line,"auto board")) { - auto_board = ~auto_board; - printf("Automatic board display %s.\n", - (auto_board) ? "Enabled" : "Disabled"); - } else if (!strcmp(line,"auto info")) { - auto_info = ~auto_info; - printf("Automatic info display %s.\n", - (auto_info) ? "Enabled" : "Disabled"); - } else { - puts("Usage: auto (board|info)."); - } - } else if (!strncmp(line,"square",6)) { - if (strnlen(line, 10) == 9 - && line[7] >= 'a' && line[7] <= '`'+board_size - && line[8] >= '1' && line[8] <= '0'+board_size) { - print_square(line[7]-'a', line[8]-'1'); - } else { - printf("Usage: square [a-%c][1-%c].\n",'`'+board_size,'0'+board_size); - } - } else if (!strncmp(line,"play",4)) { - if (strnlen(line,7) == 6 - && ((line[5] == 'b' || line[5] == 'B') - || (line[5] == 'w' || line[5] == 'W'))) { - // 'b' is even :) - human = 1 - (line[5] & 1); - new_game(5); - } else { - puts("Usage: play (b|w)."); - } - } else { - return EXIT_FAILURE; - } - return EXIT_SUCCESS; +static int input_is_not_turn(const char *line) { + if (!strcmp(line, "help")) { + puts("Valid commands: auto (board|info), board, depth [0-9], eval,\ +help, info, load <file.ptn>, log, new, play (b|w), self-play, square\ +<col><row>, tps, <PTN>."); + } else if (!strcmp(line, "board")) { + print_board(); + } else if (!strcmp(line, "info")) { + print_info(); + } else if (!strcmp(line, "eval")) { + float eval = cnn1986_evaluate_black_win() * 100; + if (ply & 1) { + printf("Black heuristic chance: %s%.2f%s\n", blk, eval, rst); + } else { + printf("White heruistic chance: %s%.2f%s\n", wht, -eval, rst); + } + } else if (!strcmp(line, "log")) { + puts(gamelog); + } else if (!strcmp(line, "new")) { + new_game(5); + } else if (!strcmp(line, "tps")) { + char buf[1000]; + generate_tps(buf); + puts(buf); + } else if (!strcmp(line, "self-play")) { + while (negamax_turn() == 0) + ; + } else if (!strncmp(line, "depth", 5)) { + if (strnlen(line, 7) == 7 && line[6] >= '0' && line[6] <= '9') { + negamax_search_depth = line[6] - '0'; + printf("New search depth: %d.\n", negamax_search_depth); + } else { + puts("Usage: depth [0-9]."); + } + } else if (!strncmp(line, "load", 4)) { + if (strnlen(line, 6) >= 6) { + if (load_ptn(line + 5)) { + printf("Errors in file %s\n", line); + } + } else { + puts("Usage: load <file.ptn>."); + } + } else if (!strncmp(line, "auto", 4)) { + if (!strcmp(line, "auto board")) { + auto_board = ~auto_board; + printf("Automatic board display %s.\n", + (auto_board) ? "Enabled" : "Disabled"); + } else if (!strcmp(line, "auto info")) { + auto_info = ~auto_info; + printf("Automatic info display %s.\n", + (auto_info) ? "Enabled" : "Disabled"); + } else { + puts("Usage: auto (board|info)."); + } + } else if (!strncmp(line, "square", 6)) { + if (strnlen(line, 10) == 9 && line[7] >= 'a' && + line[7] <= '`' + board_size && line[8] >= '1' && + line[8] <= '0' + board_size) { + print_square(line[7] - 'a', line[8] - '1'); + } else { + printf("Usage: square [a-%c][1-%c].\n", '`' + board_size, + '0' + board_size); + } + } else if (!strncmp(line, "play", 4)) { + if (strnlen(line, 7) == 6 && ((line[5] == 'b' || line[5] == 'B') || + (line[5] == 'w' || line[5] == 'W'))) { + // 'b' is even :) + human = 1 - (line[5] & 1); + new_game(5); + } else { + puts("Usage: play (b|w)."); + } + } else { + return EXIT_FAILURE; + } + return EXIT_SUCCESS; } -const char* license = "ctlm, a line mode interface to the ct library\n\ +const char *license = "ctlm, a line mode interface to the ct library\n\ \n\ Copyright (C) 2021, tslil clingman\n\ \n\ This program comes with ABSOLUTELY NO WARRANTY; and is made available under the terms of the GNU GPL v3 license. This is free software, and you are welcome to redistribute it under certain conditions; see COPYING for details.\n"; int main(int argc, char **argv) { - (void)(argc); - (void)(argv); - - puts(license); - - negamax_search_depth = 5; - new_game(5); - negamax_init(5); - - // Test harness - if (argc > 1) { - load_ptn("data/0.ptn"); - negamax_turn(); - return 0; - } - // Test harness - - char *line = NULL; - ssize_t read = -1; - size_t alloc_size; - - human = 0; - for (int playing = 1; playing;) { - while (human == 0) { - fputs("ctlm> ", stdout); - fflush(stdout); - read = getline(&line, &alloc_size, stdin); - if (read > 0) { - line[read - 1] = 0; - if (input_is_not_turn(line)) { - int r = handle_turn(line); - if (r == EXIT_SUCCESS && won == 0xFF) { - human = 1; - } - } - free(line); - line = NULL; - } else { - playing = 0; - human = 1; - } - } - if (playing) { - negamax_turn(); - human = 0; - } - } - - free(line); - free(gamelog); - negamax_free(); - - return EXIT_SUCCESS; + (void)(argc); + (void)(argv); + + puts(license); + + negamax_search_depth = 5; + new_game(5); + negamax_init(5); + + // Test harness + if (argc > 1) { + negamax_search_depth = 7; + load_ptn("data/0.ptn"); + negamax_turn(); + return 0; + } + // Test harness + + char *line = NULL; + ssize_t read = -1; + size_t alloc_size; + + human = 0; + for (int playing = 1; playing;) { + while (human == 0) { + fputs("ctlm> ", stdout); + fflush(stdout); + read = getline(&line, &alloc_size, stdin); + if (read > 0) { + line[read - 1] = 0; + if (input_is_not_turn(line)) { + int r = handle_turn(line); + if (r == EXIT_SUCCESS && won == 0xFF) { + human = 1; + } + } + free(line); + line = NULL; + } else { + playing = 0; + human = 1; + } + } + if (playing) { + negamax_turn(); + human = 0; + } + } + + free(line); + free(gamelog); + negamax_free(); + + return EXIT_SUCCESS; } diff --git a/src/cttei.c b/src/cttei.c index a663359..aae1045 100644 --- a/src/cttei.c +++ b/src/cttei.c @@ -1,20 +1,20 @@ /* - cttei, a TEI interface to the ct library & its computer opponent + cttei, a TEI interface to the ct library & its computer opponent - Copyright (C) 2021, tslil clingman + Copyright (C) 2021, tslil clingman - 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 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. + 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 this program. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ #include <stdlib.h> @@ -28,11 +28,11 @@ // Set up output function for negamax inline void negamax_display_progress(const uint8_t cur_depth, - const uint8_t init_depth, - const uint32_t length) { - (void)(cur_depth); - (void)(init_depth); - (void)(length); + const uint8_t init_depth, + const uint32_t length) { + (void)(cur_depth); + (void)(init_depth); + (void)(length); } enum TEI_RETURN { TEI_QUIT, TEI_OK, TEI_FAILURE }; @@ -40,63 +40,63 @@ enum TEI_RETURN { TEI_QUIT, TEI_OK, TEI_FAILURE }; // expects ``(startpos|tps <tps>) moves <ptn>'' static enum TEI_RETURN parse_position_string(char *line) { - // Find the word ``moves'' - char *beg = strstr(line, "moves"); - - if (!strncasecmp(line, "tps", 3)) { - // Split the string on the space before moves - if (beg) *(beg-1) = 0; - // so that we can load it as a TPS description - load_tps(line + 4); - } else if (!strncasecmp(line, "startpos", 8)) { - reset_state(board_size); - } else { - return TEI_FAILURE; - } - - if (beg == NULL) return TEI_OK; - - // parse the PTN sequence - strtok(beg, " "); - char *ptn = strtok(NULL, " "); - while (ptn != NULL) { - if (do_ptn(ptn) != ACT_OK) return TEI_FAILURE; - ptn = strtok(NULL, " "); - } - - return TEI_OK; + // Find the word ``moves'' + char *beg = strstr(line, "moves"); + + if (!strncasecmp(line, "tps", 3)) { + // Split the string on the space before moves + if (beg) *(beg-1) = 0; + // so that we can load it as a TPS description + load_tps(line + 4); + } else if (!strncasecmp(line, "startpos", 8)) { + reset_state(board_size); + } else { + return TEI_FAILURE; + } + + if (beg == NULL) return TEI_OK; + + // parse the PTN sequence + strtok(beg, " "); + char *ptn = strtok(NULL, " "); + while (ptn != NULL) { + if (do_ptn(ptn) != ACT_OK) return TEI_FAILURE; + ptn = strtok(NULL, " "); + } + + return TEI_OK; } static enum TEI_RETURN handle_tei(char *line) { - if (!strcmp(line, "quit")) { - return TEI_QUIT; - } if (!strcmp(line, "isready")) { - puts("readyok"); - } else if (!strncmp(line, "setoption Depth value ", 22)) { - negamax_search_depth = atoi(line + 23); - } else if (!strncmp(line, "go", 2)) { - // TODO: for now we ignore all of the parameters - float minimax = negamax_generate(); - enum ACT_RESULT r = do_ptn(negamax_ptn); - if (r != ACT_OK && r != GAME_END) return TEI_FAILURE; - printf("info score cp %f pv %s\nbestmove %s\n", - minimax, negamax_ptn, negamax_ptn); - } else if (!strncmp(line, "position", 8)) { - return parse_position_string(line + 9); - } else if (!strncmp(line, "teinewgame", 10)) { - if (line[11] != '5') return TEI_FAILURE; - const uint8_t size = atoi(line + 11); - if (size != board_size) { - negamax_free(); - reset_state(size); - negamax_init(size); - } else { - reset_state(size); - } - } - fflush(stdout); - return TEI_OK; + if (!strcmp(line, "quit")) { + return TEI_QUIT; + } if (!strcmp(line, "isready")) { + puts("readyok"); + } else if (!strncmp(line, "setoption Depth value ", 22)) { + negamax_search_depth = atoi(line + 23); + } else if (!strncmp(line, "go", 2)) { + // TODO: for now we ignore all of the parameters + float minimax = negamax_generate(); + enum ACT_RESULT r = do_ptn(negamax_ptn); + if (r != ACT_OK && r != GAME_END) return TEI_FAILURE; + printf("info score cp %f pv %s\nbestmove %s\n", + minimax, negamax_ptn, negamax_ptn); + } else if (!strncmp(line, "position", 8)) { + return parse_position_string(line + 9); + } else if (!strncmp(line, "teinewgame", 10)) { + if (line[11] != '5') return TEI_FAILURE; + const uint8_t size = atoi(line + 11); + if (size != board_size) { + negamax_free(); + reset_state(size); + negamax_init(size); + } else { + reset_state(size); + } + } + fflush(stdout); + return TEI_OK; } const char* license = "cttei, a TEI interface to the ct library & its computer opponent\n\ @@ -106,58 +106,58 @@ Copyright (C) 2021, tslil clingman\n\ This program comes with ABSOLUTELY NO WARRANTY; and is made available under the terms of the GNU GPL v3 license. This is free software, and you are welcome to redistribute it under certain conditions; see COPYING for details.\n"; int main(int argc, char **argv) { - (void)(argc); - (void)(argv); - - puts(license); - - char *line = NULL; - ssize_t read = -1; - size_t alloc_size; - - // Wait for tei - while ((read = getline(&line, &alloc_size, stdin))) { - if (read > 0 && !strncmp("tei", line, 3)) { - break; - } else return EXIT_FAILURE; - } - - if (line) free(line); - line = NULL; - - // Identify ourselves, and send the options - puts("id name cttei"); - puts("id author tslil clingman"); - puts("option name Depth type spin default 4 min 2 max 6"); - puts("teiok"); - fflush(stdout); - - // Set default option - negamax_search_depth = 4; - negamax_init(5); - reset_state(5); - - for (int playing = 1; playing;) { - if ((read = getline(&line, &alloc_size, stdin)) > 0) { - line[read-1] = 0; - switch (handle_tei(line)) { - case TEI_FAILURE: return EXIT_FAILURE; - case TEI_QUIT: playing = 0; // fall-through - case TEI_OK: { - if (line) { - free(line); - line = NULL; - } - break; - } - } - } else { - break; - } + (void)(argc); + (void)(argv); + + puts(license); + + char *line = NULL; + ssize_t read = -1; + size_t alloc_size; + + // Wait for tei + while ((read = getline(&line, &alloc_size, stdin))) { + if (read > 0 && !strncmp("tei", line, 3)) { + break; + } else return EXIT_FAILURE; + } + + if (line) free(line); + line = NULL; + + // Identify ourselves, and send the options + puts("id name cttei"); + puts("id author tslil clingman"); + puts("option name Depth type spin default 4 min 2 max 6"); + puts("teiok"); + fflush(stdout); + + // Set default option + negamax_search_depth = 4; + negamax_init(5); + reset_state(5); + + for (int playing = 1; playing;) { + if ((read = getline(&line, &alloc_size, stdin)) > 0) { + line[read-1] = 0; + switch (handle_tei(line)) { + case TEI_FAILURE: return EXIT_FAILURE; + case TEI_QUIT: playing = 0; // fall-through + case TEI_OK: { + if (line) { + free(line); + line = NULL; + } + break; } + } + } else { + break; + } + } - if (line) free(line); - negamax_free(); + if (line) free(line); + negamax_free(); - return EXIT_SUCCESS; + return EXIT_SUCCESS; } diff --git a/src/geminict.c b/src/geminict.c new file mode 100644 index 0000000..2ac2eab --- /dev/null +++ b/src/geminict.c @@ -0,0 +1,346 @@ +/* + geminict, a Gemini CGI interface to the ct library + + Copyright (C) 2021, tslil clingman + + 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 this program. If not, see <https://www.gnu.org/licenses/>. +*/ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include <negamax.h> +#include <tak.h> +#include <tps.h> + +#define SQUARE_W 5 +#define SQUARE_H 3 + +#define STR_FLT_BLK "⛀" +#define STR_FLT_WHT "⛂" +#define STR_STN_BLK "⫾" +#define STR_STN_WHT "❚" +#define STR_CAP_BLK "♕" +#define STR_CAP_WHT "♛" +#define STR_HFL_BLK "▭" +#define STR_HFL_WHT "▬" +#define STR_CHF_BLK "▿" +#define STR_CHF_WHT "▾" + +static void put_stone(const enum STONE_VARIANT stone, const enum COLOUR colour, + const uint8_t top, const uint8_t beyond_carry_limit) { + if (beyond_carry_limit) { + fputs((colour == C_BLACK) ? STR_CHF_BLK : STR_CHF_WHT, stdout); + } else { + if (top) { + switch (stone) { + case STONE_FLAT: { + fputs((colour == C_BLACK) ? STR_FLT_BLK : STR_FLT_WHT, stdout); + break; + } + case STONE_STANDING: { + fputs((colour == C_BLACK) ? STR_STN_BLK : STR_STN_WHT, stdout); + break; + } + case STONE_CAPSTONE: { + fputs((colour == C_BLACK) ? STR_CAP_BLK : STR_CAP_WHT, stdout); + break; + } + } + } else { + fputs((colour == C_BLACK) ? STR_HFL_BLK : STR_HFL_WHT, stdout); + } + } +} + +static void print_cell_line(const uint8_t line, const uint8_t col, + const uint8_t row) { + + const uint8_t location = THE_COORDS(col, row), + stack_size = COUNT_AT(location); + + uint8_t idx; + for (uint8_t k = 0; k < SQUARE_W; k++) { + idx = line + k * SQUARE_H; + // Are we in the last column to be displayed? + if ((k + 1) * SQUARE_H > stack_size) { + // If so, then if we can't fill it offset the starting line so + // that it fills from the bottom up instead of the top down + if (line < (k + 1) * SQUARE_H - stack_size) { + // skip these lines + idx = 0xFF; + } else { + // offset back + idx -= (k + 1) * SQUARE_H - stack_size; + } + } + if (idx < stack_size) { + put_stone(STONE_AT(location), + (colours[location] & (1 << idx)) ? C_BLACK : C_WHITE, idx == 0, + idx >= board_size); + } else { + putchar(' '); + } + } +} + +// It takes board_size*(SQUARE_H+1)+1 lines to print the board, they +// may be requested in any order and at any time +static void print_board_line(const uint8_t line) { + const uint8_t mod = line % (SQUARE_H + 1), + row = board_size - line / (SQUARE_H + 1) - 1; + + // Print leader, either row number if half-way through square or + // padding spaces otherwise + if (mod == (SQUARE_H + 1) / 2) + printf("%d. ", row + 1); + else + fputs(" ", stdout); + + // Top and bottom of squares receive borders + if (mod == 0) { + for (uint8_t x = 0; x < board_size; x++) { + putchar('+'); + for (uint8_t k = 0; k < SQUARE_W; k++) + putchar('-'); + } + puts("+"); + } else { + // Interior of board should be filled by borders and pieces + if (line < board_size * (SQUARE_H + 1)) { + for (uint8_t x = 0; x < board_size; x++) { + putchar('|'); + print_cell_line(mod - 1, x, row); + } + puts("|"); + } else { + // Bottom of board has column markers + for (uint8_t x = 0; x < board_size; x++) { + for (uint8_t k = 0; k <= SQUARE_W / 2; k++) + putchar(' '); + printf("%c.", x + 'a'); + for (uint8_t k = 0; k < SQUARE_W - SQUARE_W / 2 - 2; k++) + putchar(' '); + } + putchar('\n'); + } + } +} + +// Simple wrapper to print the whole board in one go +static void print_board(void) { + for (uint8_t k = 0; k < board_size * (SQUARE_H + 1) + 2; k++) { + print_board_line(k); + } + putchar('\n'); +} + +static void print_info(void) { + printf("Turn: %2d, %s%s\n", ply / 2 + 1, + (ply & 1) ? "Black" : "White", + (ply < 2) ? " (counter-play start)" : ""); + printf("Flats/Caps remaining: %02d/%d, %02d/%d\n", + white_count & 127, white_count >> 7, black_count & 127, + black_count >> 7); +} + +static char *gamelog = NULL; + +static void print_everything(void) { + print_board(); + print_info(); + puts(gamelog); +} + +static int append_to_gamelog(const char *line, const uint8_t win_line) { + // I _could_ dynamically compute the size but ... don't let + // `perfect' be the enemy of `good' ? + + if (gamelog == NULL) + return EXIT_FAILURE; + + char prepend[8]; + + if (win_line) { + prepend[0] = '\n'; + prepend[1] = 0; + } else if (ply & 1) { + snprintf(prepend, 7, "%s%d. ", (ply == 1) ? "" : "\n", ply / 2 + 1); + } else { + strcpy(prepend, " "); + } + // Make room for this line + gamelog = + realloc(gamelog, strlen(gamelog) + strlen(prepend) + strlen(line) + 1); + // TODO: trap errno + strcat(gamelog, prepend); + strcat(gamelog, line); + + return EXIT_SUCCESS; +} + +static void end_game(char *line, char *win) { + append_to_gamelog(line, 0); + append_to_gamelog(win, 1); + print_board(); + puts("Game over:"); + puts(gamelog); + putchar('\n'); +} + +enum TURN_RESULT { T_ERR, T_OK, T_WIN }; +static enum TURN_RESULT handle_turn(char *line) { + // Track win state + uint8_t new_win = (won == 0xFF); + switch (do_ptn(line)) { + // Errors + case ACT_INVALID_PTN: { + puts("Invalid PTN."); + return T_ERR; + } + case ACT_ILLEGAL: { + puts("Illegal action."); + return T_ERR; + } + case ACT_OVERFLOW: { + puts("Move would cause internal overflow, select another."); + return T_ERR; + } + // Game has ended + case GAME_END: { + // Did it end this turn? + if (new_win) { + switch (won) { + case WIN_DRAW: { + end_game(line, "1/2-1/2"); + break; + } + case WIN_FLAT_BLACK: { + end_game(line, "0-F"); + break; + } + case WIN_FLAT_WHITE: { + end_game(line, "F-0"); + break; + } + case WIN_ROAD_BLACK: { + end_game(line, "0-R"); + break; + } + case WIN_ROAD_WHITE: { + end_game(line, "R-0"); + break; + } + } + return T_WIN; + } + if (!new_win) + return T_ERR; + break; + } + // Valid, append to game log + case ACT_OK: { + append_to_gamelog(line, 0); + break; + } + } + return T_OK; +} + +static void new_game(uint8_t size) { + reset_state(size); + if (gamelog) + gamelog = realloc(gamelog, sizeof(char)); + else + gamelog = malloc(sizeof(char)); + gamelog[0] = 0; +} + +static float num_check; + +// Set up output function for negamax +inline void negamax_display_progress(const uint8_t cur_depth, + const uint8_t init_depth, + const uint32_t length) { + (void)(cur_depth); + (void)(init_depth); + (void)(length); + num_check += 1; +} + +static int negamax_turn(void) { + if (won == 0xFF) { + // Run the minimax + num_check = 0; + float minimax = negamax_generate(); + putchar('\n'); + // Failed to find a non-losing move? + if (minimax <= -infty) + puts("Opponent concedes!"); + printf("ct1986 says: %s (minmax %.2f, checked %.1e)\n\n", negamax_ptn, minimax * 100.0, + num_check); + return handle_turn(negamax_ptn); + } else { + return EXIT_FAILURE; + } +} + +int main(int argc, char **argv) { + if (argc != 2) { + puts("Usage: PTN1.[PTN2.][PTN3.] etc"); + return EXIT_FAILURE; + }; + + negamax_search_depth = 5; + new_game(5); + negamax_init(5); + + enum TURN_RESULT tr; + + char* line = argv[1]; + // Some maximum length we're willing to parse + const uint32_t len = strnlen(line, 65535); + if (!line || len == 0 || len == 65535) return EXIT_FAILURE; + uint32_t start = 0, end = 0; + while (start < len) { + // Find first separator + while (end < len && line[end] != '.') end++; + // If still on line + if (end < len) { + // Mark the split + line[end] = 0; + // Try the first piece we found + tr = handle_turn(line + start); + if (tr == T_ERR) { + printf("Error on: %s\n", line + start); + print_everything(); + return EXIT_FAILURE; + } else if (tr == T_WIN) return EXIT_SUCCESS; + start = ++end; + } else { + puts("Malformed input."); + return EXIT_FAILURE; + } + } + + negamax_turn(); + + print_everything(); + + free(gamelog); + negamax_free(); + + return EXIT_SUCCESS; +} diff --git a/src/pptdb.c b/src/pptdb.c index 79f60c5..eeebf2a 100644 --- a/src/pptdb.c +++ b/src/pptdb.c @@ -1,21 +1,21 @@ /* - pptdb, generate neural network training data from a playtak.com - database dump + pptdb, generate neural network training data from a playtak.com + database dump - Copyright (C) 2021, tslil clingman + Copyright (C) 2021, tslil clingman - 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 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. + 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 this program. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ #include <stdio.h> @@ -31,121 +31,121 @@ float max_flats, outcome_black; static void write_input(const int dx, const int dy, const uint8_t swap) { - // Two numbers for flats remaining - fprintf(training_fh,"%.8f,%.8f,", - (float)(white_count & 127)/max_flats, - (float)(black_count & 127)/max_flats); - - // Write the board layers - float val; - int col, row; - for (uint8_t depth = 0; depth < board_size + 1; depth++) { - row = (dy>0)?-1:board_size; - for (int i = 0; i < board_size; i++) { - row += dy; - col = (dx>0)?-1:board_size; - for (int j = 0; j < board_size; j++) { - col += dx; - const uint8_t k = - (swap) ? THE_COORDS(row, col) : THE_COORDS(col, row); - val = 0; - if (COUNT_AT(k)>depth) { - if (depth == 0) { - // Top layer of stacks is handled differently to indicate - // stone type - if (STONE_AT(k) == STONE_STANDING) { - val = (colours[k] & 1) ? +0.25 : -0.25; - } else if (STONE_AT(k) == STONE_CAPSTONE) { - val = (colours[k] & 1) ? +1.00 : -1.00; - } else { - val = (colours[k] & 1) ? +0.75 : -0.75; - } - } else { - // Layers underneath - val = (colours[k] & (1<<depth)) ? +0.75 : -0.75; - } - } - fprintf(training_fh,"%.2f,", val); - } - } + // Two numbers for flats remaining + fprintf(training_fh,"%.8f,%.8f,", + (float)(white_count & 127)/max_flats, + (float)(black_count & 127)/max_flats); + + // Write the board layers + float val; + int col, row; + for (uint8_t depth = 0; depth < board_size + 1; depth++) { + row = (dy>0)?-1:board_size; + for (int i = 0; i < board_size; i++) { + row += dy; + col = (dx>0)?-1:board_size; + for (int j = 0; j < board_size; j++) { + col += dx; + const uint8_t k = + (swap) ? THE_COORDS(row, col) : THE_COORDS(col, row); + val = 0; + if (COUNT_AT(k)>depth) { + if (depth == 0) { + // Top layer of stacks is handled differently to indicate + // stone type + if (STONE_AT(k) == STONE_STANDING) { + val = (colours[k] & 1) ? +0.25 : -0.25; + } else if (STONE_AT(k) == STONE_CAPSTONE) { + val = (colours[k] & 1) ? +1.00 : -1.00; + } else { + val = (colours[k] & 1) ? +0.75 : -0.75; + } + } else { + // Layers underneath + val = (colours[k] & (1<<depth)) ? +0.75 : -0.75; + } } - fprintf(training_fh,"%.1f\n", outcome_black); + fprintf(training_fh,"%.2f,", val); + } + } + } + fprintf(training_fh,"%.1f\n", outcome_black); } // Warning: performs _no_ checks on input whatsoever static enum ACT_RESULT parse_line(const char *pt, const ssize_t read) { - ssize_t idx; - enum ACT_RESULT r; - int total_plies = 0; - - for (idx=0;idx<read;idx++) { - if (pt[idx]==',') total_plies++; + ssize_t idx; + enum ACT_RESULT r; + int total_plies = 0; + + for (idx=0;idx<read;idx++) { + if (pt[idx]==',') total_plies++; + } + for(idx=0;;) { + if (pt[idx] == 'P') { + // P [A-F][1-6] [CF]?, + idx+=2; + enum STONE_VARIANT stone; + const uint8_t col = pt[idx]-'A', row = pt[idx+1]-'1'; + + if (idx + 3 < read) { + switch (pt[idx+3]) { + case 'W': { stone = STONE_STANDING; break; } + case 'C': { stone = STONE_CAPSTONE; break; } + default: { stone = STONE_FLAT; break; } } - for(idx=0;;) { - if (pt[idx] == 'P') { - // P [A-F][1-6] [CF]?, - idx+=2; - enum STONE_VARIANT stone; - const uint8_t col = pt[idx]-'A', row = pt[idx+1]-'1'; - - if (idx + 3 < read) { - switch (pt[idx+3]) { - case 'W': { stone = STONE_STANDING; break; } - case 'C': { stone = STONE_CAPSTONE; break; } - default: { stone = STONE_FLAT; break; } - } - } else { - stone = STONE_FLAT; - } - - r = try_place(THE_COORDS(col,row), current_colour, stone); - if (r != ACT_OK) return r; - } else if (pt[idx] == 'M') { - // M [A-F][1-6] [A-F][1-6]( [1-6])+, - idx+=2; - uint8_t drops[board_size]; - const uint8_t s_col =pt[idx]-'A', s_row=pt[idx+1]-'1', - d_col=pt[idx+3]-'A', d_row=pt[idx+4]-'1'; - idx+=4; - - enum MOVE_DIRECTION dir = M_RIGHT; - if (s_col < d_col) dir=M_RIGHT; - else if (s_col > d_col) dir=M_LEFT; - else if (s_row < d_row) dir=M_UP; - else if (s_row > d_row) dir=M_DOWN; - - uint8_t steps = 0; - do { - idx+=2; - drops[steps++] = pt[idx] - '0'; - } while (idx+2<read && pt[idx+1] != ','); - - r = try_move(THE_COORDS(s_col, s_row), dir, steps, drops); - - if (r != ACT_OK) return r; - - if (generate == 0) { - // Measure height of stacks exceeding 1 - for (int k = 0; k < board_size * board_size; k++) { - if (COUNT_AT(k)>1) heights[COUNT_AT(k)]+=1; - } - } - } - // Generate training data, not too early in the game and not at - // the end, under all eight symmetries of the board - if (generate && ply < total_plies && ply + 2 >= total_plies) { - write_input(+1, +1, 1); write_input(+1, +1, 0); - write_input(+1, -1, 1); write_input(+1, -1, 0); - write_input(-1, +1, 1); write_input(-1, +1, 0); - write_input(-1, -1, 1); write_input(-1, -1, 0); - } - // Parse next action - while (idx<read && pt[idx++]!=','); - if (idx>=read) return ACT_OK; - next_ply(); + } else { + stone = STONE_FLAT; + } + + r = try_place(THE_COORDS(col,row), current_colour, stone); + if (r != ACT_OK) return r; + } else if (pt[idx] == 'M') { + // M [A-F][1-6] [A-F][1-6]( [1-6])+, + idx+=2; + uint8_t drops[board_size]; + const uint8_t s_col =pt[idx]-'A', s_row=pt[idx+1]-'1', + d_col=pt[idx+3]-'A', d_row=pt[idx+4]-'1'; + idx+=4; + + enum MOVE_DIRECTION dir = M_RIGHT; + if (s_col < d_col) dir=M_RIGHT; + else if (s_col > d_col) dir=M_LEFT; + else if (s_row < d_row) dir=M_UP; + else if (s_row > d_row) dir=M_DOWN; + + uint8_t steps = 0; + do { + idx+=2; + drops[steps++] = pt[idx] - '0'; + } while (idx+2<read && pt[idx+1] != ','); + + r = try_move(THE_COORDS(s_col, s_row), dir, steps, drops); + + if (r != ACT_OK) return r; + + if (generate == 0) { + // Measure height of stacks exceeding 1 + for (int k = 0; k < board_size * board_size; k++) { + if (COUNT_AT(k)>1) heights[COUNT_AT(k)]+=1; } - return ACT_OK; + } + } + // Generate training data, not too early in the game and not at + // the end, under all eight symmetries of the board + if (generate && ply < total_plies && ply + 2 >= total_plies) { + write_input(+1, +1, 1); write_input(+1, +1, 0); + write_input(+1, -1, 1); write_input(+1, -1, 0); + write_input(-1, +1, 1); write_input(-1, +1, 0); + write_input(-1, -1, 1); write_input(-1, -1, 0); + } + // Parse next action + while (idx<read && pt[idx++]!=','); + if (idx>=read) return ACT_OK; + next_ply(); + } + return ACT_OK; } const char* license = "pptdb, generate neural network training data from a playtak.com database dump\n\ @@ -155,92 +155,92 @@ Copyright (C) 2021, tslil clingman\n\ This program comes with ABSOLUTELY NO WARRANTY; and is made available under the terms of the GNU GPL v3 license. This is free software, and you are welcome to redistribute it under certain conditions; see COPYING for details.\n"; int main(int argc, char **argv) { - (void)(argc); - - enum ACT_RESULT r; - enum WIN_TYPE win; - uint32_t games = 0, overflow=0, illegal = 0; - uint32_t road_wins=0, flat_wins=0, road_turns=0, flat_turns=0, - white_wins = 0, black_wins = 0; - - for (int k = 0; k < 16; k++) heights[k] = 0; - - size_t len = 0; - ssize_t read = 0; - FILE *playtak_fh = NULL; - char *line = NULL, td_fn[65]; - - const uint8_t size = argv[1][0]-'0'; - - playtak_fh = fopen(argv[2], "r"); - if (playtak_fh == NULL) exit(EXIT_FAILURE); - - if (argc > 3 && (!strncmp("generate", argv[3], 8))) { - generate=1; - max_flats = (size == 5) ? 21.0 : 30.0; - snprintf(td_fn, 64, "data/training-%d.csv",size); - training_fh = fopen(td_fn, "w"); - if (training_fh == NULL) exit(EXIT_FAILURE); - } else generate=0; - - while ((read = getline(&line, &len, playtak_fh)) != -1) { - // Reset everything - reset_state(size); - // Store the outcome of this game. Black win = 1 - if (line[read-4] == '0') outcome_black = 0.9; - else outcome_black = -0.9; - // Parse the line - r = parse_line(line,read-4); - // Adjust counts if we're not generating training data - if (generate == 0) { - if (r == ACT_ILLEGAL) { - illegal++; - printf("Illegal:\n%s",line); - } else if (r == ACT_OVERFLOW) { - printf("Overflow:\n%s",line); - overflow++; - } else { - win = check_win(); - if (win == WIN_FLAT_BLACK - || win == WIN_FLAT_WHITE - || win == WIN_DRAW) { - flat_wins++; - flat_turns += ply/2+1; - } else { - road_wins++; - road_turns += ply/2+1; - } - if (win == WIN_FLAT_BLACK || win == WIN_ROAD_BLACK) - black_wins++; - else if (win == WIN_FLAT_WHITE || win == WIN_ROAD_WHITE) - white_wins++; - } - } - games++; + (void)(argc); + + enum ACT_RESULT r; + enum WIN_TYPE win; + uint32_t games = 0, overflow=0, illegal = 0; + uint32_t road_wins=0, flat_wins=0, road_turns=0, flat_turns=0, + white_wins = 0, black_wins = 0; + + for (int k = 0; k < 16; k++) heights[k] = 0; + + size_t len = 0; + ssize_t read = 0; + FILE *playtak_fh = NULL; + char *line = NULL, td_fn[65]; + + const uint8_t size = argv[1][0]-'0'; + + playtak_fh = fopen(argv[2], "r"); + if (playtak_fh == NULL) exit(EXIT_FAILURE); + + if (argc > 3 && (!strncmp("generate", argv[3], 8))) { + generate=1; + max_flats = (size == 5) ? 21.0 : 30.0; + snprintf(td_fn, 64, "data/training-%d.csv",size); + training_fh = fopen(td_fn, "w"); + if (training_fh == NULL) exit(EXIT_FAILURE); + } else generate=0; + + while ((read = getline(&line, &len, playtak_fh)) != -1) { + // Reset everything + reset_state(size); + // Store the outcome of this game. Black win = 1 + if (line[read-4] == '0') outcome_black = 0.9; + else outcome_black = -0.9; + // Parse the line + r = parse_line(line,read-4); + // Adjust counts if we're not generating training data + if (generate == 0) { + if (r == ACT_ILLEGAL) { + illegal++; + printf("Illegal:\n%s",line); + } else if (r == ACT_OVERFLOW) { + printf("Overflow:\n%s",line); + overflow++; + } else { + win = check_win(); + if (win == WIN_FLAT_BLACK + || win == WIN_FLAT_WHITE + || win == WIN_DRAW) { + flat_wins++; + flat_turns += ply/2+1; + } else { + road_wins++; + road_turns += ply/2+1; } - - fclose(playtak_fh); - if (generate) fclose(training_fh); - if (line) free(line); - - if (illegal || overflow) putchar('\n'); - printf("Read %d games\n",games); - - if (generate==0) { - printf("Illegals: %d\nOverflows: %d\n\ + if (win == WIN_FLAT_BLACK || win == WIN_ROAD_BLACK) + black_wins++; + else if (win == WIN_FLAT_WHITE || win == WIN_ROAD_WHITE) + white_wins++; + } + } + games++; + } + + fclose(playtak_fh); + if (generate) fclose(training_fh); + if (line) free(line); + + if (illegal || overflow) putchar('\n'); + printf("Read %d games\n",games); + + if (generate==0) { + printf("Illegals: %d\nOverflows: %d\n\ Black wins: %.3f%%\n\ Road wins: %d\nFlat wins: %d\n\ Average turns to road win: %.3f\n\ Average turns to flat win: %.3f\n", - illegal, overflow, - (double)black_wins / (double)(black_wins+white_wins) * 100, - road_wins, flat_wins, - (double)(road_turns)/(double)(road_wins), - (double)(flat_turns)/(double)(flat_wins)); - for (int k = 2; k < 16; k++) { - printf("Height %2d: %7ld\n",k,heights[k]); - } - } - - exit(EXIT_SUCCESS); + illegal, overflow, + (double)black_wins / (double)(black_wins+white_wins) * 100, + road_wins, flat_wins, + (double)(road_turns)/(double)(road_wins), + (double)(flat_turns)/(double)(flat_wins)); + for (int k = 2; k < 16; k++) { + printf("Height %2d: %7ld\n",k,heights[k]); + } + } + + exit(EXIT_SUCCESS); } |