Do what the game says
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nOne DP function for eac
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nOne DP function for each player. Alice tries to maximize, Bob tries to minimize. Note in Alice DP we use Bobs DP and vice verca.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:\n        @cache\n        def alice(i,j,pawns):\n            res = 0\n            for ii in range(1,len(positions)+1):\n                if (1<<ii) & pawns == 0:\n                    x,y = positions[ii-1]\n                    d = knight_dist((i,j),(x,y))\n                    res = max(res, d+bob(x,y,pawns|(1<<ii)))\n            return res\n        \n        @cache\n        def bob(i,j,pawns):\n            res = float(\'inf\')\n            for ii in range(1,len(positions)+1):\n                if (1<<ii) & pawns == 0:\n                    x,y = positions[ii-1]\n                    d = knight_dist((i,j),(x,y))\n                    res = min(res, d+alice(x,y,pawns|(1<<ii)))\n            return res if res < float(\'inf\') else 0\n        \n        @cache\n        def knight_dist(s,t):\n            level,d,visited = [s],0,set([s])\n            while level:\n                newlevel = []            \n                for i,j in level:\n                    if (i,j) == t: return d\n                    for (ii,jj) in [(i+2,j+1),(i+2,j-1),(i-2,j+1),(i-2,j-1),(i+1,j+2),(i+1,j-2),(i-1,j+2),(i-1,j-2)]:\n                        if 0<=ii<=49 and 0<=jj<=49 and (ii,jj) not in visited:\n                            visited.add((ii,jj))\n                            newlevel.append((ii,jj))\n                level = newlevel\n                d += 1\n            return d\n        return alice(kx,ky,0)\n```
['Python3']