BFS + bitmask
Intuition\nThe question itself is quite straightforward: BFS for knight to pawn and bitmask dp for best solution.\n\n\n# Approach\n1. For each step, we need to 
# Intuition\nThe question itself is quite straightforward: BFS for knight to pawn and bitmask dp for best solution.\n\n\n# Approach\n1. For each step, we need to do BFS to get the minimum steps from knight to each pawn. Since the path to the target pawn will not be affected by the existing pawns, it would be more efficient to get the minimum steps for each squares and reuse the result if possible.\n2. Alice and Bob have similar strategy, the only difference is max or min of all possible cases\n3. Use bit operation to mark if the pawn is still on the board.\n\n# Complexity\n- Time complexity (n=number of pawns, m = size of board (50)):\n    possible cases of pawn ($2^n$) * possible cases of knight (n+1) * complexity of BFS ($m^2$) = O($n*2^n*m^2$)\n\n- Space complexity:\n    possible cases of knight (n+1) * space for BFS and its result ($m^2$) + binary dp ($(n+1)*2^n$) = O($n*m^2+n*2^n$)\n\n# Code\n```python3 []\nfrom collections import deque\nclass Solution:\n    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:\n        n = len(positions)\n        position = [(p[0],p[1]) for p in positions]\n        pawn = (1<<n)-1\n\n        chessSize = 50\n\n        @cache\n        def _chess_bfs(kxy):\n            kx,ky = kxy\n            steps = [[-1]*chessSize for _ in range(chessSize)]\n            queue = deque([(kx,ky,0)])\n            steps[kx][ky] = 0\n            while queue:\n                x,y,step = queue.popleft()\n                if x-2 >= 0:\n                    if y-1>=0 and steps[x-2][y-1] == -1:\n                        queue.append((x-2,y-1,step+1))\n                        steps[x-2][y-1] = step+1\n                    if y+1<chessSize and steps[x-2][y+1] == -1:\n                        queue.append((x-2,y+1,step+1))\n                        steps[x-2][y+1] = step+1\n                if x-1 >= 0:\n                    if y-2>=0 and steps[x-1][y-2] == -1:\n                        queue.append((x-1,y-2,step+1))\n                        steps[x-1][y-2] = step+1\n                    if y+2<chessSize and steps[x-1][y+2] == -1:\n                        queue.append((x-1,y+2,step+1))\n                        steps[x-1][y+2] = step+1\n                if x+2 < chessSize:\n                    if y-1>=0 and steps[x+2][y-1] == -1:\n                        queue.append((x+2,y-1,step+1))\n                        steps[x+2][y-1] = step+1\n                    if y+1<chessSize and steps[x+2][y+1] == -1:\n                        queue.append((x+2,y+1,step+1))\n                        steps[x+2][y+1] = step+1\n                if x+1 < chessSize:\n                    if y-2>=0 and steps[x+1][y-2] == -1:\n                        queue.append((x+1,y-2,step+1))\n                        steps[x+1][y-2] = step+1\n                    if y+2<chessSize and steps[x+1][y+2] == -1:\n                        queue.append((x+1,y+2,step+1))\n                        steps[x+1][y+2] = step+1\n            return steps\n\n        @cache\n        def _maxminMoves(kxy,pawn,whosTurn):\n            if pawn == 0:\n                return 0\n            steps = _chess_bfs(kxy)\n\n            if whosTurn == \'alice\':\n                ans = max([steps[position[i][0]][position[i][1]]+\n                           _maxminMoves(position[i],pawn-(1<<i),\'bob\')\n                            for i in range(n) if ((1<<i) & (pawn))])\n            else:\n                ans = min([steps[position[i][0]][position[i][1]]+\n                           _maxminMoves(position[i],pawn-(1<<i),\'alice\')\n                            for i in range(n) if ((1<<i) & (pawn))])\n            return ans\n        \n        \n        kxy = (kx,ky)\n        return _maxminMoves(kxy,pawn,\'alice\')\n\n\n\n        \n```
['Breadth-First Search', 'Bitmask', 'Python3']