Bitmask DP
\nPrecompute number of steps required to go from postion of each pawn and starting position to all other pawns. \n\nStore the number of steps in distance matrix
\nPrecompute number of steps required to go from postion of each pawn and starting position to all other pawns. \n\nStore the number of steps in distance matrix of size (n+1) * (n+1).\n\n\n---------------\n\nNow do a recursive dp with the following parameters\n\npos - position we are currently at( 16 possibilities, 0th will be starting position and 15 positions of pawns)\n\nmask - represents which positions are already visited.\n\nstat - (0-Alices turn, 1 - bobs turn).\n\nTake maximum when its alices turn. \nTake minimum when its bobs turn.\n\n(please upvote if it helped)\n\n# Code\n```cpp []\n\n#define ll long long\n\nint xf;\n\nvector<ll> xm{-2, -2, +2, +2, -1, +1, -1, +1};\nvector<ll> ym{-1, +1, -1, +1, -2, -2, +2, +2};\n\nint dp[70000][16][2];\n\nvoid find(int pos, vector<vector<ll>> &arr, map< pair<int, int>, int> &m, vector< vector<ll> > &g)\n{\n    int x = arr[pos][0];\n    int y = arr[pos][1];\n \n    vector<ll> t(51, 0);\n    vector< vector<ll> > vis(51, t); // visited array of size 51*51. \n    \n    ll n = arr.size();\n\n    queue< tuple<int, int, int> > q;\n    q.push({0, x, y}); // push initial postion inside the queue to start bfs search.\n    \n    tuple<int, int, int> tp;\n    int dec = 0;\n\n    while(q.size() > 0 && dec < n) // when dec = n, all positions are visited. \n    {\n        tp = q.front(); \n        q.pop();\n            \n        int step = get<0>(tp);\n        x = get<1>(tp);\n        y = get<2>(tp);\n        \n        if(vis[x][y] == 1)\n            continue;\n        \n        vis[x][y] = 1;\n        \n        if(m.find({x ,y}) != m.end()) // check if (x, y) is a required position. \n        {\n            ++dec;\n            \n            ll p1 = pos;\n            ll p2 = m[{x, y}]; // get the index of (x,y) from map.\n            \n            g[p1][p2] = step; // distance matrix updation (p1 to p2).\n        }\n        \n        for(int i=0; i<8; ++i) // checking all 8 moves. \n        {\n            ll nx = x + xm[i];\n            ll ny = y + ym[i];\n            \n            if(nx >= 0 && nx < 50 && ny >= 0 && ny < 50 && vis[nx][ny] == 0) // make sure the new position is not out of the board and its not visited previously. \n            {\n                q.push({step+1, nx, ny});\n            }\n        }\n    }\n}\n\n\nint find(int pos, int mask, int stat, vector<vector<ll>> &arr, vector< vector<ll> > &g)\n{\n    if(mask == xf) // xf = value of mask when all position is visited \n        return 0;\n    \n    if(dp[mask][pos][stat] != -1)\n        return dp[mask][pos][stat];\n    \n    ll ans;\n    \n    if(stat == 0)\n    {\n        ans = 0;\n    \n        for(int i=1; i<arr.size(); ++i)\n        {\n            ll rp = i-1;       \n            int bit = (mask >> rp) & 1;\n            \n            if(!bit)\n            {\n                mask = mask | (1<<rp);\n                ans = max(ans, g[pos][i] + find(i, mask, 1, arr, g)); // g[pos][i] = steps required to go from pos to i.\n                mask = mask ^ (1<<rp);\n            }\n        }\n    }\n\n    else if(stat == 1)\n    {\n        ans = 1e9;\n        \n        for(int i=1; i<arr.size(); ++i)\n        {\n            ll rp = i-1;       \n            int bit = (mask >> rp) & 1;\n            \n            if(!bit)\n            {\n                mask = mask | (1<<rp);\n                ans = min(ans, g[pos][i] + find(i, mask, 0, arr, g));\n                mask = mask ^ (1<<rp);\n            }\n        }\n    }\n\n    return dp[mask][pos][stat] = ans;\n}\n\n\n\nclass Solution {\npublic:\n    int maxMoves(int kx, int ky, vector<vector<int>>& pos) {\n        \n        memset(dp, -1, sizeof(dp));\n        \n        vector<vector<ll>> arr; // creating new array with starting position included. \n        arr.push_back({kx, ky});\n        \n        map< pair<int, int>, int> m; // map to keep track of index of each position. \n        m[{kx, ky}] = 0; // index of starting position = 0.\n        \n        for(int i=0; i<pos.size(); ++i)\n        {\n            arr.push_back({pos[i][0], pos[i][1]}); \n            m[{pos[i][0], pos[i][1]}] = i+1; \n        }\n        \n        ll n = arr.size();\n            \n        vector< ll > v(n+1, 0);\n        vector< vector<ll> > g(n+1, v); // distance matrix.\n        \n        for(int i=0; i<arr.size(); ++i)\n        {\n            find(i, arr, m, g); // pre-computing from each position.\n        }\n        \n        n = n-1;\n        xf = pow(2, n)-1; // xf = value of mask when all positions are visited.\n        \n        ll ans = find(0, 0, 0, arr, g);\n        \n        return ans;\n    }\n};\n\n\n\n```
['C++']