I was trying to solve the spoj problem MATGAME. I have read topcoder tutorial on game theory and this discussion on topcoder forums and this discussion. All i understand is that each row can be treated as a subgame. I cannot figure out how to assign grundy numbers to sub games. Can someone help me? Thanks in advance.
P.S. I am a novice in game theory problems.
Its a nice modification of Sprague-Grundy Theory. For this problem you need to find the Grundy number of each and every row the given matrix.
To calculate the Grundy number of each row you need to know the Grundy number of each and every cell of the row.
Now if you are on a cell of a row you have 2 possible moves -> either finish the current cell and move to next or move to a lower number in the current cell. An edge case comes when the number in the cell is equal to 1. Here you have just one move that is to move to next cell.
Now you may calculate Grundy numbers in this manner ->
grundy[i][j] = grundy[i][j+1] >= grundy[i][j] ? grundy[i][j] - 1 : grundy[i][j];
Now just find the NIM sum of 1st elements in each row.
1 Like
Can you please explain how the following formula is derived:
grundy[i][j] = grundy[i][j+1] >= grundy[i][j] ? grundy[i][j] - 1 : grundy[i][j];
thanks in advance,
1 Like