mjtb49 · March 26, 2025 09:08 · Aug 2, 2024 · Jul 31, 2024
diff --git a/infinite_tablebase.py b/infinite_tablebase.py
@@ -1,4 +1,3 @@
-import math
 import random
 import itertools as iter
 
@@ -47,13 +46,14 @@ def move_on_board(board, index, v):
 
 
 class PieceType:
-    def __init__(self, symbol, riders=(), jumpers=(), rider_bound=None, is_royal=False):
+    def __init__(self, symbol, riders=(), jumpers=(), rider_bound=None, is_royal=False, is_pawn=False):
         assert len(riders) == len(set(riders))
         assert len(jumpers) == len(set(jumpers))
         assert len(set(jumpers).intersection(set(riders))) == 0
         self.riders = set(riders)
         self.jumpers = set(jumpers)
         self.is_royal = is_royal
+        self.is_pawn = is_pawn
         self.symbol = symbol
         self.rider_bound = rider_bound if rider_bound is not None else 2 ** 64
 
@@ -64,6 +64,10 @@ def threatens_from(self, board, my_index, target_square):
             return False
         if piece_square == target_square:
             return False
+        if self.is_pawn:
+            if move(piece_square, (-1, 1)) == target_square or move(piece_square, (-1, -1)) == target_square:
+                return True
+            return False
 
         if (target_square[0] - piece_square[0], target_square[1] - piece_square[1]) in self.jumpers:
             return True
@@ -107,6 +111,7 @@ def get_resulting_board_states(self, board, index, move_bound):
 GUARD = PieceType("G", jumpers=[(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (-1, -1), (1, -1)])
 HAWK = PieceType("H", jumpers=[(2, 0), (-2, 0), (0, 2), (0, -2), (2, 2), (-2, 2), (-2, -2), (2, -2),
                                (3, 0), (-3, 0), (0, 3), (0, -3), (3, 3), (-3, 3), (-3, -3), (3, -3)])
+PAWN = PieceType("P", jumpers=[(-1, 0)], is_pawn=True)
 
 
 def get_white_moves(board, move_bound):
@@ -117,8 +122,18 @@ def get_white_moves(board, move_bound):
 
 
 def get_white_preimages(board, move_bound):
-    # TODO with pawns or other black pieces this won't be the case.
-    return [w for w in get_white_moves(board, move_bound) if KING_SQUARE not in w and not is_threatened(KING_SQUARE, w)]
+    result = []
+    for i in range(len(PIECES)):
+        if PIECES[i].is_pawn:
+            if board[i] is not None:
+                for v in PIECES[i].jumpers:
+                    new_board = move_on_board(board, i, (-v[0], -v[1]))
+                    if not new_board[i] in board:
+                        result.append(new_board)
+        else:
+            result += PIECES[i].get_resulting_board_states(board, i, move_bound)
+
+    return [w for w in result if KING_SQUARE not in w and not is_threatened(KING_SQUARE, w)]
 
 
 def get_black_moves(board):
@@ -297,8 +312,8 @@ def get_wins(winning_positions, move_bound, pos_score=None, should_print_variati
     black_wins = winning_positions
     white_wins = {}
     unexplored = winning_positions
-    # for p in winning_positions:
-    #     print_position(p)
+    for p in winning_positions:
+        print_position(p)
     i = 1
     while len(unexplored) > 0:
         # forceable_position = ((0, -1), (3, -1), (-4, -2))
@@ -322,6 +337,11 @@ def get_wins(winning_positions, move_bound, pos_score=None, should_print_variati
             black_wins.update(new_wins)
             print(f"{i} {len(new_wins)}")
 
+            if len(new_wins) < 10:
+                print("-" * 80)
+                for p in new_wins:
+                    print_position(p)
+                print("-"*80)
             pos_to_print = get_best_position(new_wins, pos_score) if pos_score is not None else random.choice(list(new_wins.keys()))
             if should_print_variations:
                 print_variations(pos_to_print, white_wins, black_wins, move_bound, black_to_move=True)
@@ -343,9 +363,9 @@ def get_wins(winning_positions, move_bound, pos_score=None, should_print_variati
         i += 1
 
 
-PIECES = [HAWK, HAWK, HAWK, HAWK]
+PIECES = [QUEEN, PAWN, KING]
 if __name__ == "__main__":
     def score(position):
-        return min(p[1] for p in position if p is not None)
-    get_wins(get_mates_faster(5), 20, pos_score=score, should_print_variations=True)
+        return min(p[1] for p in position[2:] if p is not None)
+    get_wins(get_mates_faster(5), 20, pos_score=score, should_print_variations=False)
     # get_wins(rotations_and_reflections({((-1, -1), (2, -1), (-1, 3)), ((-1, -1), (2, -1), (-1, -3)), ((0, -1), (3, -1), (-4, -2))}), 20, pos_score=score, should_print_variations=False)
diff --git a/infinite_tablebase.py b/infinite_tablebase.py
@@ -0,0 +1,351 @@
+import math
+import random
+import itertools as iter
+
+KING_SQUARE = (0, 0)
+KING_THREATENS = {(-1, -1), (-1, 0), (-1, 1),
+                   (0, 1),           (0, -1),
+                   (1, -1), (1, 0), (1, 1)}
+MATING_SQUARES = {(-1, -1), (-1, 0), (-1, 1),
+                  (0, 1), (0, 0), (0, -1),
+                  (1, -1), (1, 0), (1, 1)}
+
+assert len(MATING_SQUARES) == 9
+assert len(KING_THREATENS) == 8
+WINNING_POSITIONS = set()
+
+
+def move(piece, v):
+    return piece[0] + v[0], piece[1] + v[1]
+
+
+# return if v is a natural number multiple of u. Assumes u != (0,0)
+def is_natural_multiple(v, direction):
+    if direction[0] != 0:
+        scalar = v[0] // direction[0]
+    else:
+        scalar = v[1] // direction[1]
+    return (scalar > 0 and (scalar * direction[0], scalar * direction[1]) == v), scalar
+
+
+def rider_threatens(direction, piece_square, target_square, board):
+    works, distance = is_natural_multiple((target_square[0] - piece_square[0], target_square[1] - piece_square[1]), direction)
+    if works:
+        for piece in board:
+            if piece is not None:
+                a, b = is_natural_multiple((piece[0] - piece_square[0], piece[1] - piece_square[1]), direction)
+                if a and b < distance:
+                    return False
+        return True
+    return False
+
+
+def move_on_board(board, index, v):
+    ls = list(board)
+    ls[index] = move(board[index], v)
+    return tuple(ls)
+
+
+class PieceType:
+    def __init__(self, symbol, riders=(), jumpers=(), rider_bound=None, is_royal=False):
+        assert len(riders) == len(set(riders))
+        assert len(jumpers) == len(set(jumpers))
+        assert len(set(jumpers).intersection(set(riders))) == 0
+        self.riders = set(riders)
+        self.jumpers = set(jumpers)
+        self.is_royal = is_royal
+        self.symbol = symbol
+        self.rider_bound = rider_bound if rider_bound is not None else 2 ** 64
+
+    # We don't need to check if the Black king is in the way.
+    def threatens_from(self, board, my_index, target_square):
+        piece_square = board[my_index]
+        if piece_square is None:
+            return False
+        if piece_square == target_square:
+            return False
+
+        if (target_square[0] - piece_square[0], target_square[1] - piece_square[1]) in self.jumpers:
+            return True
+        for v in self.riders:
+            if rider_threatens(v, piece_square, target_square, board):
+                return True
+        return False
+
+    def get_resulting_board_states(self, board, index, move_bound):
+        if board[index] is None:
+            return []
+        moves = []
+        for v in self.jumpers:
+            new_board = move_on_board(board, index, v)
+            # TODO with black pieces we need to check check and captures.
+            if not new_board[index] in board:
+                if (not self.is_royal) or (new_board[index] not in KING_THREATENS):
+                    moves.append(new_board)
+        for v in self.riders:
+            k = 1
+            new_pieces = move_on_board(board, index, v)
+            while new_pieces[index] not in board and k < min(self.rider_bound, move_bound):
+                k += 1
+                if (not self.is_royal) or (new_pieces[index] not in KING_THREATENS):
+                    moves.append(new_pieces)
+                new_pieces = move_on_board(new_pieces, index, v)
+        return moves
+
+
+CHANCELLOR = PieceType("C", riders=[(1, 0), (-1, 0), (0, 1), (0, -1)],
+                       jumpers=[(1, 2), (-1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, 1), (-2, -1)])
+ARCHBISHOP = PieceType("A", riders=[(1, 1), (-1, 1), (1, -1), (-1, -1)],
+                       jumpers=[(1, 2), (-1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, 1), (-2, -1)])
+ROOK = PieceType("R", riders=[(1, 0), (-1, 0), (0, 1), (0, -1)])
+QUEEN = PieceType("Q", riders=[(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (-1, -1), (1, -1)])
+KNIGHT = PieceType("N", jumpers=[(1, 2), (-1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, 1), (-2, -1)])
+KNIGHTRIDER = PieceType("R", riders=[(1, 2), (-1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, 1), (-2, -1)])
+BISHOP = PieceType("B", riders=[(1, 1), (-1, 1), (-1, -1), (1, -1)])
+
+KING = PieceType("K", jumpers=[(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (-1, -1), (1, -1)], is_royal=True)
+GUARD = PieceType("G", jumpers=[(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (-1, -1), (1, -1)])
+HAWK = PieceType("H", jumpers=[(2, 0), (-2, 0), (0, 2), (0, -2), (2, 2), (-2, 2), (-2, -2), (2, -2),
+                               (3, 0), (-3, 0), (0, 3), (0, -3), (3, 3), (-3, 3), (-3, -3), (3, -3)])
+
+
+def get_white_moves(board, move_bound):
+    result = []
+    for i in range(len(PIECES)):
+        result += PIECES[i].get_resulting_board_states(board, i, move_bound)
+    return result
+
+
+def get_white_preimages(board, move_bound):
+    # TODO with pawns or other black pieces this won't be the case.
+    return [w for w in get_white_moves(board, move_bound) if KING_SQUARE not in w and not is_threatened(KING_SQUARE, w)]
+
+
+def get_black_moves(board):
+    result = []
+    for v in KING_THREATENS:
+        new_board = []
+        for p in board:
+            if p is not None:
+                p = move(p, v)  # technically this moves the king along -v
+                new_board.append(p if p != KING_SQUARE else None)
+            else:
+                new_board.append(None)
+        if not is_threatened(KING_SQUARE, tuple(new_board)):
+            result.append(tuple(new_board))
+    return result
+
+
+def get_black_preimages(board):
+    if is_threatened(KING_SQUARE, board):
+        return []
+    result = []
+    for v in KING_THREATENS:
+        new_board = []
+        for p in board:
+            if p is not None:
+                new_board.append(move(p, v))
+            else:
+                new_board.append(None)
+        if KING_SQUARE not in new_board and all(piece is None or (not piece.is_royal) or (new_board[i] not in MATING_SQUARES) for i, piece in enumerate(PIECES)):
+            result.append(tuple(new_board))
+    return result
+
+
+def is_threatened(square, board):
+    return any(PIECES[i].threatens_from(board, i, square) for i in range(len(board)))
+
+
+def is_mate(piece_positions):
+    return all(is_threatened(v, piece_positions) for v in MATING_SQUARES)
+
+
+def is_stalemate(piece_positions):
+    return all(is_threatened(v, piece_positions) for v in KING_THREATENS) and not is_threatened(KING_SQUARE,
+                                                                                                piece_positions)
+
+
+def branch_value(x):
+    return len(get_black_moves(x))
+
+
+def pieces_same_color(s1, s2):
+    if s1 is None or s2 is None:
+        return True
+    return (s1[0] + s1[1] + s2[0] + s2[1]) % 2 == 0
+
+
+def pieces_different_color(s1, s2):
+    return not pieces_same_color(s1, s2)
+
+
+def get_mates(n, parity_condition=lambda x: True):
+    coordinates = [(a, b) for a in range(-n, n + 1) for b in range(-n, n + 1)] + [None]
+    coordinates.remove(KING_SQUARE)
+    royalty = [i for i in range(len(PIECES)) if PIECES[i].is_royal]
+    positions = {}
+
+    for p in iter.permutations(coordinates, len(PIECES)):
+        if is_mate(p):
+            if parity_condition(p):
+                if all(p[i] not in MATING_SQUARES for i in royalty):
+                    positions[p] = 0
+
+    return positions
+
+
+def get_mates_faster(bound, parity_condition=lambda x: True):
+    coordinates = [(a, b) for a in range(-bound, bound + 1) for b in range(-bound, bound + 1)] + [None]
+    coordinates.remove(KING_SQUARE)
+    ms = list(MATING_SQUARES)
+    royalty = [i for i in range(len(PIECES)) if PIECES[i].is_royal]
+    patterns = [dict() for _ in PIECES]
+    keys = [set() for _ in PIECES]
+
+    for piece_index, piece in enumerate(PIECES):
+        for c in coordinates:
+            pattern = 0
+            for i, p in enumerate(ms):
+                if piece.threatens_from((c,), 0, target_square=p):
+                    pattern |= 2**i
+            if pattern not in patterns[piece_index]:
+                patterns[piece_index][pattern] = []
+                keys[piece_index].add(pattern)
+            patterns[piece_index][pattern].append(c)
+
+    positions = dict()
+    for p in iter.product(*keys):
+        s = 0
+        for k in p:
+            s |= k
+        if s == 2**9 - 1:
+            for r in iter.product(*[patterns[i][key] for i, key in enumerate(p)]):
+                # print(r)
+                if all(pos is None or r.count(pos) == 1 for pos in r):
+                    if is_mate(r):
+                        if parity_condition(r):
+                            if all(r[i] not in MATING_SQUARES for i in royalty):
+                                positions[r] = 0
+    # print(positions)
+    return positions
+
+
+def print_position(board, indent=0):
+    min_x = min([b[0] for b in board if b is not None] + [0]) - 2
+    min_y = min([b[1] for b in board if b is not None] + [0]) - 2
+    gap_x = max([b[0] for b in board if b is not None] + [0]) - min_x + 2 + 1
+    gap_y = max([b[1] for b in board if b is not None] + [0]) - min_y + 2 + 1
+    arr = [['_' for _ in range(gap_y)] for _ in range(gap_x)]
+
+    for i, b in enumerate(board):
+        if b is not None:
+            arr[b[0]-min_x][b[1]-min_y] = PIECES[i].symbol
+    arr[KING_SQUARE[0]-min_x][KING_SQUARE[1]-min_y] = 'k'
+
+    print("|  " * indent + str(board))
+    # if indent < 4:
+    for l in arr:
+        print("|  " * indent + (" ".join(l)))
+
+
+def print_variations(position, white_wins, black_wins, move_bound, indent=0, black_to_move=True):
+    print_position(position, indent)
+    if black_to_move:
+        if black_wins[position] <= 0:
+            return
+        for p in sorted(get_black_moves(position), key=lambda x: -white_wins[x]):
+            assert p in white_wins
+            print_variations(p, white_wins, black_wins, move_bound, indent+1, black_to_move=False)
+    else:
+        if white_wins[position] <= 0:
+            return
+        found_position = False
+        for p in get_white_moves(position, move_bound):
+            if p in black_wins and black_wins[p] < white_wins[position]:
+                assert black_wins[p] + 1 == white_wins[position]
+                print_variations(p, white_wins, black_wins, move_bound, indent+1, black_to_move=True)
+                found_position = True
+                break
+        assert found_position
+
+
+def get_best_position(positions, position_score):
+    best = -2**64
+    best_pos = None
+    for board in positions:
+        if position_score(board) > best:
+            best = position_score(board)
+            best_pos = board
+    return best_pos
+
+
+def rotations_and_reflections(positions):
+    new_positions = dict()
+    for p in positions:
+        for i in range(4):
+            new_positions[p] = 0
+            p = tuple((-b, a) for (a, b) in p)
+        p = tuple((-a, b) for (a, b) in p)
+        for i in range(4):
+            new_positions[p] = 0
+            p = tuple((-b, a) for (a, b) in p)
+    return new_positions
+
+
+def get_wins(winning_positions, move_bound, pos_score=None, should_print_variations=False):
+    print(f"Starting the search {len(winning_positions)}")
+    black_wins = winning_positions
+    white_wins = {}
+    unexplored = winning_positions
+    # for p in winning_positions:
+    #     print_position(p)
+    i = 1
+    while len(unexplored) > 0:
+        # forceable_position = ((0, -1), (3, -1), (-4, -2))
+        # if forceable_position in white_wins:
+        #     print("White to move is a win!")
+        #     print_variations(forceable_position, white_wins, black_wins, move_bound, black_to_move=False)
+        #     print(i)
+        # if forceable_position in black_wins:
+        #     print("Black to move is a win!")
+        #     print_variations(forceable_position, white_wins, black_wins, move_bound, black_to_move=True)
+    #     print(i)
+        new_wins = {}
+        if i % 2 == 0:  # Black just moved
+            for p in unexplored:
+                for q in get_black_preimages(p):
+                    if q not in black_wins:
+                        if all(r in white_wins or is_mate(r) for r in get_black_moves(q)):
+                            # print("HI")
+                            new_wins[q] = i
+            unexplored = new_wins
+            black_wins.update(new_wins)
+            print(f"{i} {len(new_wins)}")
+
+            pos_to_print = get_best_position(new_wins, pos_score) if pos_score is not None else random.choice(list(new_wins.keys()))
+            if should_print_variations:
+                print_variations(pos_to_print, white_wins, black_wins, move_bound, black_to_move=True)
+            else:
+                print_position(pos_to_print)
+        else:  # White just moved
+            for p in unexplored:
+                for q in get_white_preimages(p, move_bound):
+                    if q not in white_wins:
+                        new_wins[q] = i
+            unexplored = new_wins
+            white_wins.update(new_wins)
+            print(f"{i} {len(new_wins)}")
+            pos_to_print = get_best_position(new_wins, pos_score) if (pos_score is not None) else random.choice(list(new_wins.keys()))
+            if should_print_variations:
+                print_variations(pos_to_print, white_wins, black_wins, move_bound, black_to_move=False)
+            else:
+                print_position(pos_to_print)
+        i += 1
+
+
+PIECES = [HAWK, HAWK, HAWK, HAWK]
+if __name__ == "__main__":
+    def score(position):
+        return min(p[1] for p in position if p is not None)
+    get_wins(get_mates_faster(5), 20, pos_score=score, should_print_variations=True)
+    # get_wins(rotations_and_reflections({((-1, -1), (2, -1), (-1, 3)), ((-1, -1), (2, -1), (-1, -3)), ((0, -1), (3, -1), (-4, -2))}), 20, pos_score=score, should_print_variations=False)
No results found