Commits

Anonymous committed 1b9c4aa

try again!

Comments (0)

Files changed (1)

checkers/checkers2.c

+/*
+ * Board representation:
+ * 32 positions
+ * 3 32bit integers
+ *  - active player's pieces
+ *  - opponent's pieces
+ *  - kings
+ *
+ * position numbers
+ * ..01..02..03..04
+ * 05..06..07..08..
+ * ..09..10..11..12
+ * 13..14..15..16..
+ * ..17..18..19..20
+ * 21..22..23..24..
+ * ..25..26..27..28
+ * 29..30..31..32..
+ *
+ * bit numbers
+ * ..11..05..31..25
+ * 10..04..30..24..
+ * ..03..29..23..17
+ * 02..28..22..16..
+ * ..27..21..15..09
+ * 26..20..14..08..
+ * ..19..13..07..01
+ * 18..12..06..00..
+ *
+ * to move a piece NE <<  1
+ * to move a piece NW <<< 7
+ * to move a piece SE >>> 7
+ * to move a piece SW >>  1
+ * invalid for certain pieces around edges so
+ *
+ * to find pieces that can move in a certain direction rotate empty spaces
+ * in opposite direction then & with pieces: rotate(~(active | opponent))
+ * & active; apply mask after rotating so we only get valid empty positions
+ * to which we can move in a known direction
+ *
+ *
+ * input is board position, output is board position
+ * add (board,board)->move so we can output move later
+ *
+ *
+ * in the program a move is the new board state
+ */
+#include <ctype.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <strings.h>
+
+enum {
+    WIN  =   13,
+    LOSE = -WIN,
+    INF  =  WIN + 1,
+};
+
+typedef enum {
+    BLACK = -1,
+    WHITE =  1,
+} Color;
+
+typedef enum {
+    // just to be explicity about Color <-> Direction
+    SE = BLACK + 1,
+    SW,
+    NE = WHITE + 1,
+    NW,
+} Direction;
+
+/*
+ * gcc x86_64 struct up to 4 32bit ints passed in 2 64bit registers
+ * does that matter? it'll be shoved on the stack when we recurse...
+ * yes it matters, use them all before recursing and they can be thrown away
+ * tail recursion, is it possible?
+ */
+typedef struct {
+    uint32_t active;   // active player (this player's turn)
+    uint32_t opponent; // opponent      (other player)
+    uint32_t kings;
+    int      score;    // needed often enough was added here
+} Board;
+
+// bit set means that piece can move in the given direction
+const uint32_t valid_mask[] = {
+    [SE] = ~0x02061243,
+    [SW] = ~0x04041445,
+    [NE] = ~0x82020a22,
+    [NW] = ~0x86040c24,
+};
+
+// last row in given direction. a piece that lands here is crowned
+const uint32_t crown_mask[] = {
+    [SE] = 0x00041041,
+    [SW] = 0x00041041,
+    [NE] = 0x82000820,
+    [NW] = 0x82000820,
+};
+
+// board_to_bit[board_position - 1] == bit_number
+const int board_to_bit[] = {
+    11,  5, 31, 25,
+    10,  4, 30, 24,
+     3, 29, 23, 17,
+     2, 28, 22, 16,
+    27, 21, 15,  9,
+    26, 20, 14,  8,
+    19, 13,  7,  1,
+    18, 12,  6,  0,
+};
+
+// bit_to_board[bit number] == board_position
+const int bit_to_board[] = {
+    32, 28, 13,  9,
+     6,  2, 31, 27,
+    24, 20,  5,  1,
+    30, 26, 23, 19,
+    16, 12, 29, 25,
+    22, 18, 15, 11,
+     8,  4, 21, 17,
+    14, 10,  7,  3,
+};
+
+// TODO: bits.S for rotates and hamming weight?
+// rot is never 0 so we will never shift by 32
+// (which is undefined for a 32bit word)
+uint32_t rotate_left(uint32_t board, unsigned rot)
+{
+    return (board << rot) | (board >> (32 - rot));
+}
+
+uint32_t rotate_right(uint32_t board, unsigned rot)
+{
+    return (board >> rot) | (board << (32 - rot));
+}
+
+// https://en.wikipedia.org/wiki/Hamming_weight
+// TODO: lookup table? asm call? do tests
+unsigned bits_set(uint32_t i)
+{
+    i = i - (i >> 1 & 0x55555555);
+    i = (i & 0x33333333) + (i >> 2 & 0x33333333);
+    return ((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101 >> 24;
+}
+
+// rotate the entire bitset as if a piece were moving in Direction dir
+uint32_t rotate_board(uint32_t board, Direction dir)
+{
+    switch (dir) {
+        default: fprintf(stderr, "bad direction\n"); return 0;
+        case SE: return rotate_left (board, 7) & valid_mask[SE];
+        case SW: return rotate_left (board, 1) & valid_mask[SW];
+        case NE: return rotate_right(board, 1) & valid_mask[NE];
+        case NW: return rotate_right(board, 7) & valid_mask[NW];
+    }
+}
+
+// rotate a piece to a new spot on the board in Direction dir
+// no need to mask, we won't do an invalid piece move becuase
+// we already found valid moves with rotate_board()
+uint32_t rotate_piece(uint32_t piece, Direction dir)
+{
+    switch (dir) {
+        default: fprintf(stderr, "bad direction\n"); return 0;
+        case SE: return rotate_right(piece, 7);
+        case SW: return rotate_right(piece, 1);
+        case NE: return rotate_left (piece, 1);
+        case NW: return rotate_left (piece, 7);
+    }
+}
+
+int max(int a, int b)
+{
+    return a > b ? a : b;
+}
+
+// read a comma separated list of board positions and set bits in *pieces
+char *read_pieces(char *p, uint32_t *pieces, uint32_t *kings)
+{
+    int npieces = 0;
+    do {
+        if (++npieces > 12) return NULL;
+        int pos;
+        uint32_t king = (*p == 'K');
+        if (king) ++p;
+        pos = strtol(p, &p, 10) - 1;
+        if (pos < 0 || pos > 31) return NULL;
+        *pieces |=   1U << board_to_bit[pos];
+        *kings  |= king << board_to_bit[pos];
+    } while (*(p++) == ',');
+    return p - 1;
+}
+
+// read FEN notation and set up game
+// e.g. "B:W18,24,27,28,K10,K15:B12,16,20,K22,K25,K29"
+int read_board(Color *turn, Board *board)
+{
+    char      buf[128], *p = buf;
+    uint32_t *pieces, *black, *white;
+
+    board->active = board->opponent = board->kings = 0;
+
+    if (!fgets(buf, sizeof(buf), stdin)) return -1;
+    switch (*(p++)) {
+        case 'B': *turn = BLACK; black = &board->active; white = &board->opponent; break;
+        case 'W': *turn = WHITE; white = &board->active; black = &board->opponent; break;
+        default : return -1;
+    }
+    if (*(p++) != ':') return -1;
+    switch (*(p++)) {
+        case 'B': pieces = black; break;
+        case 'W': pieces = white; break;
+        default : return -1;
+    }
+    p = read_pieces(p, pieces, &board->kings);
+    if (!p || (*p++) != ':') return -1;
+    switch (*(p++)) {
+        case 'B': if (pieces == black) return -1; pieces = black; break;
+        case 'W': if (pieces == white) return -1; pieces = white; break;
+        default : return -1;
+    }
+    p = read_pieces(p, pieces, &board->kings);
+    if (!p || *p != '\n') return -1;
+    return 0;
+}
+
+// for a move from board position a to b print "a-b" if no capture, "axb" if capture
+void print_move(Board board, Board move)
+{
+    uint32_t piece = board.active ^ move.active;
+    printf("%d%c%d\n", bit_to_board[ffs(board.active & piece) - 1],
+                       board.opponent ^ move.opponent ? 'x' : '-',
+                       bit_to_board[ffs(move.active  & piece) - 1]);
+}
+
+// for debugging
+void print_board(uint32_t white, uint32_t black, uint32_t kings)
+{
+    for (int i = 0; i < 32; i++) {
+        int  pre   = !((i / 4) % 2); // preceding empty on even rows
+        int  pos   = 1 << board_to_bit[i];
+        char piece = white & pos ? 'w' :
+                     black & pos ? 'b' : ' ';
+        if (kings & pos)
+            piece = toupper(piece);
+
+        if (!(i % 4))
+            printf("\n");
+
+        printf("%s %c %s", pre ? " . " : "", piece, pre ? "" : " . ");
+    }
+    printf("\n");
+}
+
+int do_jumps_single_dir(Color turn, Board board, uint32_t jumper, uint32_t dead, uint32_t mask, int *alpha, int beta, int depth, Board *move, Direction dir);
+void do_jumps_single(Color turn, Board board, uint32_t piece, uint32_t dead, uint32_t king, int *alpha, int beta, int depth, Board *move);
+void do_jumps_dir(Color turn, Board board, uint32_t mask, int *alpha, int beta, int depth, Board *move, Direction dir);
+void do_jumps(Color turn, Board board, int *alpha, int beta, int depth, Board *move);
+void do_moves_dir(Color turn, Board board, uint32_t mask, int *alpha, int beta, int depth, Board *move, Direction dir);
+void do_moves(Color turn, Board board, int *alpha, int beta, int depth, Board *move);
+int negamax(Color turn, Board board, int alpha, int beta, int depth, Board *move);
+// jumps are mandatory. jumps can chain. after a jump, if another jump is available it must be taken
+// once we start jumping, the *move holds...hmm, move so far?
+
+// given a single piece and a direction, check if the piece can jump there
+// if it can then start the jump search for that piece over again to continue jumping
+// unless it became crowned then its turn is over becuse it can't jump anymore (??? i shouldn't manually deal with that...)
+// extra parameter jumper which contains our one piece that we are using
+// extra parameter dead which contains the opponent's pieces that we have captured so far this turn
+int do_jumps_single_dir(Color turn, Board board, uint32_t jumper, uint32_t dead, uint32_t mask, int *alpha, int beta, int depth, Board *move, Direction dir)
+{
+    // find empty spaces dir of live opponents
+    uint32_t piece = rotate_board(~(board.active | board.opponent), dir) & (board.opponent ^ dead);
+    // see if one of those is dir of our piece
+    piece = rotate_board(piece, dir) & jumper & mask;
+
+    if (piece) {
+        uint32_t new_dead  = rotate_piece(piece   , dir); // opponent's piece we are capturing
+        uint32_t new_piece = rotate_piece(new_dead, dir); // where our piece ends up
+        uint32_t king      = board.kings & piece;         // position of our king if it was one
+        uint32_t new_king  = rotate_piece(rotate_piece(king, dir), dir); // new position of our king (if king) exclude new crowns as turn isn't over
+        board.active ^= (piece | new_piece); // move our piece
+        dead         ^= new_dead;            // add new captured piece but leave opponent's pieces in place until end of turn
+        board.kings  ^= (king  | new_king ); // move our king (if king)
+        do_jumps_single(turn, board, new_piece, dead, new_piece & crown_mask[dir], alpha, beta, depth, move);
+        return 1;
+    }
+    return 0;
+}
+
+// given a single piece try to jump in all directions
+// if it can't jump, then the turn is over, recurse (negamax)
+// passed in one more extra parameter king which contains our newly crowned king if we have one
+void do_jumps_single(Color turn, Board board, uint32_t piece, uint32_t dead, uint32_t king, int *alpha, int beta, int depth, Board *move)
+{
+    Direction dir = turn + 1;
+    int jumped = 0;
+    jumped += do_jumps_single_dir(turn, board, piece, dead,         -1U, alpha, beta, depth, move,   dir                );
+    jumped += do_jumps_single_dir(turn, board, piece, dead,         -1U, alpha, beta, depth, move, ++dir                );
+    jumped += do_jumps_single_dir(turn, board, piece, dead, board.kings, alpha, beta, depth, move,   dir = (dir + 1) % 4);
+    jumped += do_jumps_single_dir(turn, board, piece, dead, board.kings, alpha, beta, depth, move, ++dir                );
+
+    if (!jumped) {
+        Board tmp_move = {
+            board.active         , // we didn't have a jump, so we didn't move
+            board.opponent ^ dead, // get rid of the pieces we captured
+            board.kings    | king, // add our new king if we have one
+            -INF
+        };
+        tmp_move.score = -negamax(-turn, tmp_move, -beta, -*alpha, depth - 1, NULL);
+        if (tmp_move.score > move->score)
+            *move = tmp_move;
+        *alpha = max(*alpha, tmp_move.score);
+    }
+}
+
+// try all pieces that can jump in dir, and make sure to continue jumping
+void do_jumps_dir(Color turn, Board board, uint32_t mask, int *alpha, int beta, int depth, Board *move, Direction dir)
+{
+    if (*alpha >= beta) return;
+    uint32_t jumpers = rotate_board(~(board.active | board.opponent), dir) & board.opponent;
+    jumpers = rotate_board(jumpers, dir) & board.active & mask;
+    for (uint32_t piece; jumpers && (piece = 1U << (ffs(jumpers) - 1)); jumpers &= ~piece) {
+        Board tmp_move = { 0, 0, 0, -INF };
+        do_jumps_single_dir(turn, board, piece, 0, mask, alpha, beta, depth, &tmp_move, dir);
+        if (tmp_move.score > move->score)
+            *move = tmp_move;
+        if (*alpha >= beta) // updated inside do_jumps_single()
+            return;
+    }
+}
+
+// try all pieces to see if any can jump in dir
+void do_jumps(Color turn, Board board, int *alpha, int beta, int depth, Board *move)
+{
+    Direction dir = turn + 1;
+    do_jumps_dir(turn, board,         -1U, alpha, beta, depth, move,   dir                );
+    do_jumps_dir(turn, board,         -1U, alpha, beta, depth, move, ++dir                );
+    do_jumps_dir(turn, board, board.kings, alpha, beta, depth, move,   dir = (dir + 1) % 4);
+    do_jumps_dir(turn, board, board.kings, alpha, beta, depth, move, ++dir                );
+}
+
+// try all pieces that can move in dir (non jump), and recurse (negamax)
+// update alpha and move
+// if only kings can move in dir mask is board.kings otherwise mask is -1U
+void do_moves_dir(Color turn, Board board, uint32_t mask, int *alpha, int beta, int depth, Board *move, Direction dir)
+{
+    if (*alpha >= beta) return; // should probably do this check _before_ recursion
+    for (uint32_t piece, movers = rotate_board(~(board.active | board.opponent), dir) & board.active & mask;
+         movers && (piece = 1U << (ffs(movers) - 1));
+         movers &= ~piece) {
+        uint32_t new_piece = rotate_piece(piece, dir);      // new position of piece
+        uint32_t king      = board.kings & piece;           // bit set if piece was king
+        uint32_t new_king  = rotate_piece(king, dir) |      // new position of old king or
+                             (new_piece & crown_mask[dir]); // position of newly created king
+        Board tmp_move = {
+            board.active ^ (piece | new_piece), // move our piece
+            board.opponent                    , // don't affect opponent's pieces
+            board.kings  ^ (king  | new_king ), // move/add/noop our king
+            -INF                                // is this correct or should I use alpha/beta here?
+        };
+        tmp_move.score = -negamax(-turn, tmp_move, -beta, -*alpha, depth - 1, NULL);
+        if (tmp_move.score > move->score)
+            *move = tmp_move;
+        if ((*alpha = max(*alpha, tmp_move.score)) >= beta)
+            return;
+    }
+}
+
+// try all non jump moves storing the outcome and score of best in move
+void do_moves(Color turn, Board board, int *alpha, int beta, int depth, Board *move)
+{
+    Direction dir = turn + 1;
+    do_moves_dir(turn, board,         -1U, alpha, beta, depth, move,   dir                );
+    do_moves_dir(turn, board,         -1U, alpha, beta, depth, move, ++dir                );
+    do_moves_dir(turn, board, board.kings, alpha, beta, depth, move,   dir = (dir + 1) % 4);
+    do_moves_dir(turn, board, board.kings, alpha, beta, depth, move, ++dir                );
+}
+
+int negamax(Color turn, Board board, int alpha, int beta, int depth, Board *move)
+{
+    int nactive_pieces   = bits_set(board.active  ); if (!nactive_pieces  ) return LOSE;
+    int nopponent_pieces = bits_set(board.opponent); if (!nopponent_pieces) return WIN;
+    if (!depth) return nactive_pieces - nopponent_pieces;
+
+    // is it worth only doing the tmp_move thing when move != NULL
+    // and have do_jumps and do_moves return scores?
+    Board tmp_move = { 0, 0, 0, -INF };
+    do_jumps(turn, board, &alpha, beta, depth, &tmp_move);
+    if (tmp_move.score == -INF) // no jumps available
+        do_moves(turn, board, &alpha, beta, depth, &tmp_move);
+    if (move)
+        *move = tmp_move;
+    return tmp_move.score;
+}
+
+int main(void)
+{
+    for (;;) {
+        Color turn;
+        Board move = { 0, 0, 0, -INF };
+        Board board;
+        if (read_board(&turn, &board)) return 1;
+        if (turn == WHITE) print_board(board.active, board.opponent, board.kings);
+        else               print_board(board.opponent, board.active, board.kings);
+        negamax(turn, board, -INF, INF, 0, &move);
+        printf("%d ", move.score); print_move(board, move);
+        if (turn == WHITE) print_board(move.active, move.opponent, move.kings);
+        else               print_board(move.opponent, move.active, move.kings);
+        printf("\n\n");
+
+    }
+    return 0;
+}