We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Game Theory
  4. Chessboard Game, Again!
  5. Discussions

Chessboard Game, Again!

  • nayeemjoy59
     + 1 comment

    A good one . If You understand grandy theorem of game theory , then it is very easy for you to solve recursively .When our possible moves from a co-ordinate of chess-board has been given .We can compute grandy-value recursively using the help of memoization .

    My full solution here https://github.com/joy-mollick/Game-Theory-Problems/blob/master/HackerRank-Chessboard%20Game%2C%20Again!.cpp

    Here is the part of my code to compute grandy value of every co-ordinate by given input .

    int sg(int x,int y)
{
    if((x==1&&y==1))
    {
        return 0;
/// (1,1) it is base case ,because from here there is no move,so grandy value of this state is zero
    }
    if(grandy_value[x][y]!=-1) /// if grandy value is already computed just return it , no need to calculate it
    {
        return grandy_value[x][y];
    }
    set<int>s;
    for(int i=0;i<4;i++)
    {
        int newx=x+dx[i];
        int newy=y+dy[i];
        if(newx>=1&&newy>=1&&newx<=15&&newy<=15)///if newx and newy is beyond (1,1) then this recursion will be recursively run ,there is no end .So (1,1) should be the terminal point
        {
            s.insert(sg(newx,newy));
        }
    }
    int mex=0;
    while(s.find(mex)!=s.end()) mex++;
    grandy_value[x][y]=mex;///assigning mex [not included minimum element in the set of grandy value of possible co-ordinates]
    return grandy_value[x][y];/// return grandy_value
}