minimax, search and memoization
Intuition\nThe problem describes a turn-based game on a chessboard with a knight and pawns. The key insight is that this can be modeled as a minimax problem, wh
# Intuition\nThe problem describes a turn-based game on a chessboard with a knight and pawns. The key insight is that this can be modeled as a minimax problem, where one player (Alice) tries to maximize the total number of moves, while the other (Bob) tries to minimize it.\n\nThe challenge lies in efficiently calculating all possible move sequences and determining the optimal play for both players. My first thought was to use a recursive approach with memoization to explore all possible game states.\n\n# Approach\nTo solve this problem, I implemented a minimax algorithm with the following key components:\n\n1. **State Representation**: \n   - Knight\'s position (row, col)\n   - Bitmask to represent captured pawns\n\n2. **Move Generation**:\n   - Implemented a function to generate all valid knight moves\n   - Used Breadth-First Search (BFS) to find the shortest path between positions\n\n3. **Minimax Algorithm**:\n   - `find_max_moves`: Represents Alice\'s turns (maximizing player)\n   - `find_min_moves`: Represents Bob\'s turns (minimizing player)\n   - These functions alternate to simulate the turn-based nature of the game\n\n4. **Optimization**:\n   - Used `@functools.cache` for memoization to avoid recomputing subproblems\n   - Employed bit manipulation for efficient pawn state tracking\n\n5. **Move Selection**:\n   - For each turn, consider all remaining pawns\n   - Calculate moves needed to capture each pawn\n   - Recursively evaluate the game state after capturing each pawn\n\nThe algorithm explores all possible move sequences, alternating between maximizing and minimizing players, to determine the optimal play and the maximum total number of moves Alice can achieve.\n\n# Code\n```python3 []\nclass Solution:\n    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:\n        import functools\n\n        num_rows = 50\n        num_cols = 50\n\n        def get_next_coords(src_row, src_col):\n            for row in [src_row - 2, src_row + 2]:\n                if row < 0 or row >= num_rows:\n                    continue\n                for col in [src_col - 1, src_col + 1]:\n                    if col < 0 or col >= num_cols:\n                        continue\n                    yield row, col\n            for col in [src_col - 2, src_col + 2]:\n                if col < 0 or col >= num_cols:\n                    continue\n                for row in [src_row - 1, src_row + 1]:\n                    if row < 0 or row >= num_rows:\n                        continue\n                    yield row, col\n\n        @functools.cache\n        def get_num_moves(src_row, src_col, tgt_row, tgt_col):\n            if src_row == tgt_row and src_col == tgt_col:\n                return 0\n            enqueued = [\n                [False for _ in range(num_cols)] for _ in range(num_rows)\n            ]\n            enqueued[src_row][src_col] = True\n            nodes_curr = [(src_row, src_col)]\n            dist = 0\n            while nodes_curr:\n                dist += 1\n                nodes_next = []\n                for src in nodes_curr:\n                    for row, col in get_next_coords(*src):\n                        if enqueued[row][col]:\n                            continue\n                        enqueued[row][col] = True\n                        if row == tgt_row and col == tgt_col:\n                            return dist\n                        nodes_next.append((row, col))\n                nodes_curr = nodes_next           \n            return dist\n\n        full_pos_mask = (1 << len(positions)) - 1\n        def get_pos(pos_mask):\n            for i, pos in enumerate(positions):\n                if (1 << i) & pos_mask:\n                    continue\n                yield i, pos\n\n        @functools.cache\n        def find_min_moves(src_row, src_col, pos_mask):\n            if full_pos_mask == pos_mask:                \n                return 0            \n            min_moves = None\n            def _update_min_moves(curr_moves):\n                nonlocal min_moves\n                if min_moves is None:\n                    min_moves = curr_moves\n                else:\n                    min_moves = min(curr_moves, min_moves)\n\n            for i, (tgt_row, tgt_col) in get_pos(pos_mask):\n                sub = get_num_moves(src_row, src_col, tgt_row, tgt_col) \n                if sub is None:\n                    continue\n                _update_min_moves(sub + find_max_moves(tgt_row, tgt_col, pos_mask | (1 << i)))\n            \n            return min_moves\n\n        @functools.cache\n        def find_max_moves(src_row, src_col, pos_mask):\n            if full_pos_mask == pos_mask:                \n                return 0            \n            max_moves = None\n            def _update_max_moves(curr_moves):\n                nonlocal max_moves\n                if max_moves is None:\n                    max_moves = curr_moves\n                else:\n                    max_moves = max(curr_moves, max_moves)                \n\n            for i, (tgt_row, tgt_col) in get_pos(pos_mask):\n                sub = get_num_moves(src_row, src_col, tgt_row, tgt_col) \n                if sub is None:\n                    continue\n                _update_max_moves(sub + find_min_moves(tgt_row, tgt_col, pos_mask | (1 << i)))\n            \n            return max_moves\n\n\n        return find_max_moves(kx, ky, 0)\n\n\n                \n                \n```
['Python3']