akulsareen game of amazons code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int MAX_DEP;
const int BOARD_SZ = 10;
const int INF = 1000000000;
struct MOVE
{
    pair <int,int> sp,fp,ap;
    int val;
};
bool sorter(const MOVE &x, const MOVE &y)
{
    return x.val > y.val;
}
int P1, tot_iter, pruned, early_break, deepest, heu_break;
int dr[] = {-1,-1,-1,0,0,1,1,1}, dc[] = {-1,0,1,-1,1,-1,0,1};
bool alternate_limits;
double alt_ratio;
bool is_ok(int r, int c, int board[][BOARD_SZ])
{
    if(r < 0 || r >= 10 || c < 0 || c >= 10)
        return false;
    if(board[r][c] != 0)
        return false;
    return true;
}
bool is_almost_ok(int r, int c, int board[][BOARD_SZ])
{
    if(r < 0 || r >= 10 || c < 0 || c >= 10)
        return false;
    if(board[r][c] == -1)
        return false;
    return true;
}
void print_board(int board[][BOARD_SZ])
{
    for (int i = 0; i < 10; ++i)
    {
        for (int j = 0; j < 10; ++j)
        {
            cout<<board[i][j]<<"\t";
        }
        cout<<"\n";
    }
    cout<<"\n\n";
}
inline void apply_MOVE(int board[][BOARD_SZ], const MOVE &mv)
{
    swap(board[mv.sp.first][mv.sp.second],board[mv.fp.first][mv.fp.second]);
    board[mv.ap.first][mv.ap.second] = -1;
}
inline void withdraw_MOVE(int board[][BOARD_SZ], const MOVE &mv)
{
    board[mv.ap.first][mv.ap.second] = 0;
    swap(board[mv.sp.first][mv.sp.second],board[mv.fp.first][mv.fp.second]);
}
int board_eval(int board[][BOARD_SZ])
{
    vector < vector <int> > d1(10,vector <int> (10,INF));
    vector < vector <int> > d2 = d1;
    queue <pii> bfs;
    for (int i = 0; i < 10; ++i)
    {
        for (int j = 0; j < 10; ++j)
        {
            if(board[i][j] == P1)
            {
                d1[i][j] = 0;
                bfs.push(pii(i,j));
            }
        }
    }
    while(!bfs.empty())
    {
        pii top = bfs.front();
        bfs.pop();
        for (int i = 0; i < 8; ++i)
        {
            int r = top.first, c = top.second;
            while(is_ok(r+dr[i],c+dc[i],board) && d1[r+dr[i]][c+dc[i]] == INF)
            {
                r+=dr[i];
                c+=dc[i];
                d1[r][c] = d1[top.first][top.second]+1;
                bfs.push(pii(r,c));
            }
        }
    }
    for (int i = 0; i < 10; ++i)
    {
        for (int j = 0; j < 10; ++j)
        {
            if(board[i][j] == 3-P1)
            {
                d2[i][j] = 0;
                bfs.push(pii(i,j));
            }
        }
    }
    while(!bfs.empty())
    {
        pii top = bfs.front();
        bfs.pop();
        for (int i = 0; i < 8; ++i)
        {
            int r = top.first, c = top.second;
            while(is_ok(r+dr[i],c+dc[i],board) && d2[r+dr[i]][c+dc[i]] == INF)
            {
                r+=dr[i];
                c+=dc[i];
                d2[r][c] = d2[top.first][top.second]+1;
                bfs.push(pii(r,c));
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < 10; ++i)
    {
        for (int j = 0; j < 10; ++j)
        {
            if(d1[i][j] < d2[i][j])
                ans++;
            if(d1[i][j] > d2[i][j])
                ans--;
        }
    }
    return ans;
}
bool is_finished(int board[][BOARD_SZ])
{
    vector < vector <int> > d1(10,vector <int> (10,INF));
    vector < vector <int> > d2 = d1;
    queue <pii> bfs;
    for (int i = 0; i < 10; ++i)
    {
        for (int j = 0; j < 10; ++j)
        {
            if(board[i][j] == P1)
            {
                d1[i][j] = 0;
                bfs.push(pii(i,j));
            }
        }
    }
    while(!bfs.empty())
    {
        pii top = bfs.front();
        bfs.pop();
        for (int i = 0; i < 8; ++i)
        {
            int r = top.first, c = top.second;
            while(is_almost_ok(r+dr[i],c+dc[i],board) && d1[r+dr[i]][c+dc[i]] == INF)
            {
                r+=dr[i];
                c+=dc[i];
                d1[r][c] = d1[top.first][top.second]+1;
                bfs.push(pii(r,c));
            }
        }
    }
    for (int i = 0; i < 10; ++i)
    {
        for (int j = 0; j < 10; ++j)
        {
            if(board[i][j] == 3-P1)
            {
                d2[i][j] = 0;
                bfs.push(pii(i,j));
            }
        }
    }
    while(!bfs.empty())
    {
        pii top = bfs.front();
        bfs.pop();
        for (int i = 0; i < 8; ++i)
        {
            int r = top.first, c = top.second;
            while(is_almost_ok(r+dr[i],c+dc[i],board) && d2[r+dr[i]][c+dc[i]] == INF)
            {
                r+=dr[i];
                c+=dc[i];
                d2[r][c] = d2[top.first][top.second]+1;
                bfs.push(pii(r,c));
            }
        }
    }
    for (int i = 0; i < 10; ++i)
    {
        for (int j = 0; j < 10; ++j)
        {
            if(d1[i][j]+d2[i][j] < INF)
                return false;
        }
    }
    return true;
}
void get_MOVEs(int board[][BOARD_SZ], int pl, vector <MOVE> &all_MOVEs, int BRANCHES = 1000)
{
    int p1,p2;
    if(pl == 1)
    {
        p1 = P1;
        p2 = 3-p1;
    }
    else
    {
        p1 = 3-P1;
        p2 = P1;
    }
    vector < vector <int> > neigh_ctr(10, vector <int> (10,0));
    vector < vector <int> > path_ctr = neigh_ctr;
    //
    for (int i = 0; i < 10; ++i)
    {
        for (int j = 0; j < 10; ++j)
        {
            //
            for (int k = 0; k < 8; ++k)
            {
                if(!is_ok(i+dr[k],j+dc[k],board))
                    neigh_ctr[i][j]++;
            }
            //
            if(board[i][j] == p2)
            {
                for (int k = 0; k < 8; ++k)
                {
                    int r = i, c = j, cd = 1;
                    while(is_ok(r+dr[k],c+dc[k],board))
                    {
                        r+=dr[k];
                        c+=dc[k];
                        cd++;
                        path_ctr[r][c]+=15-cd;
                    }
                }
            }
        }
    }
    // now check all of your own MOVEs
    MOVE temp;
    for (int i = 0; i < 10; ++i)
    {
        for (int j = 0; j < 10; ++j)
        {
            if(board[i][j] == p1)
            {
                temp.sp.first = i;
                temp.sp.second = j;
                for (int k = 0; k < 8; ++k)
                {
                    int r = i, c = j;
                    while(is_ok(r+dr[k],c+dc[k],board))
                    {
                        r+=dr[k];
                        c+=dc[k];
                        temp.fp.first = r;
                        temp.fp.second = c;
                        swap(board[i][j],board[r][c]);
                        for (int l = 0; l < 8; ++l)
                        {
                            int tr = r, tc = c;
                            while(is_ok(tr+dr[l],tc+dc[l],board))
                            {
                                tr+=dr[l];
                                tc+=dc[l];
                                temp.ap.first = tr;
                                temp.ap.second = tc;
                                temp.val = neigh_ctr[i][j]*neigh_ctr[i][j] - neigh_ctr[r][c] + path_ctr[r][c] + 2*(path_ctr[tr][tc] + neigh_ctr[tr][tc]);
                                all_MOVEs.push_back(temp);
                            }
                        }
                        swap(board[i][j],board[r][c]);
                    }
                }
            }
        }
    }
    sort(all_MOVEs.begin(), all_MOVEs.end(), sorter);
    if(all_MOVEs.size() <= BRANCHES)
        return;
    all_MOVEs.resize(min(3*BRANCHES/2,(int)all_MOVEs.size()));
    random_shuffle(all_MOVEs.begin(), all_MOVEs.end());
    all_MOVEs.resize(min(BRANCHES,(int)all_MOVEs.size()));
    sort(all_MOVEs.begin(), all_MOVEs.end(), sorter);
}
MOVE alpha_beta(int board[][BOARD_SZ], int depth, int alpha, int beta)
{
    // int lala;
    // cin>>lala;
    // cout<<"entering: "<<alpha<<" "<<beta<<" "<<" at depth = "<<depth<<"\n";
    MOVE ret;
    tot_iter++;
    if(depth == MAX_DEP || (clock() >= alt_ratio*CLOCKS_PER_SEC && depth >= 3))
    {
        if(depth < 3)
            early_break++;
        if(depth == MAX_DEP)
            deepest++;
        ret.val = board_eval(board);
        // cout<<"early ret = "<<ret.val<<"\n";
        return ret;
    }
    // print_board(board);
    if(depth%2)
        ret.val = -INF;
    else
        ret.val = INF;
    if(clock() >= 0.98*CLOCKS_PER_SEC)
    {
        if(depth < 3)
            early_break++;
        ret.val*=-1;
        return ret;
    }
    // odd depth = P1 = max. node
    // even depth = P2 = min.node
    if(depth >= 2 && is_finished(board))
    {
        ret.val = board_eval(board);
        heu_break++;
        return ret;
    }
    vector <MOVE> all_MOVEs;
    if(depth <= 2)
        get_MOVEs(board,depth%2,all_MOVEs);
    else if(depth <= 4)
        get_MOVEs(board,depth%2,all_MOVEs,500);
    else
        get_MOVEs(board,depth%2,all_MOVEs,100);
    if(all_MOVEs.empty())
    {
        ret.val = board_eval(board);
        return ret;
    }
    for (int i = 0; i < all_MOVEs.size() && alpha < beta; ++i)
    {
        apply_MOVE(board,all_MOVEs[i]);
        MOVE temp = alpha_beta(board,depth+1,alpha,beta);
        withdraw_MOVE(board,all_MOVEs[i]);
        if(depth%2)
        {
            if(temp.val > alpha)
                alpha = temp.val;
            if(temp.val > ret.val)
            {
                ret = all_MOVEs[i];
                ret.val = temp.val;
            }
        }
        else
        {
            if(temp.val < beta)
                beta = temp.val;
            if(temp.val < ret.val)
            {
                ret = all_MOVEs[i];
                ret.val = temp.val;
            }
        }
        if(alpha >= beta)
            pruned++;
    }
    return ret;
}
int main()
{
    // freopen("input.txt", "r", stdin);
    srand(92812038);
    int board[BOARD_SZ][BOARD_SZ];
    //
    for (int i = 0; i < 10; ++i)
    {
        for (int j = 0; j < 10; ++j)
        {
            cin>>board[i][j];
        }
    }
    cin>>P1;
    // for some reason bit doesnt play well when it is player 2
    // making sure it is not some stupid fault somewhere in the code
    // by changing code to always run on player 1
    if(P1 == 2)
    {
        for (int i = 0; i < 10; ++i)
        {
            for (int j = 0; j < 10; ++j)
            {
                if(board[i][j] == 2)
                    board[i][j] = 1;
                else if(board[i][j] == 1)
                    board[i][j] = 2;
                else
                {
                    //
                }
            }
        }
        P1 = 1;
    }
    //
    vector <MOVE> lala;
    get_MOVEs(board,1,lala);
    alt_ratio = 0.95;
    MAX_DEP = 45;
    for (int i = 50; i <= 1050; i+=50, alt_ratio-=0.02, MAX_DEP--)
    {
        if(lala.size() <= i)
            break;
    }
    MOVE ans = alpha_beta(board,1,-INF,INF);
    cout<<ans.sp.first<<" "<<ans.sp.second<<"\n";
    cout<<ans.fp.first<<" "<<ans.fp.second<<"\n";
    cout<<ans.ap.first<<" "<<ans.ap.second<<"\n";
    cout<<"stats: "<<ans.val<<" "<<MAX_DEP<<" : ("<<early_break<<","<<deepest<<","<<tot_iter<<") "<<heu_break<<"\n";
    return 0;
}