Game Development Stack Exchange is a question and answer site for professional and independent game developers. It only takes a minute to sign up.
Sign up to join this community
Players take turns in taking a rectangular bite out of the bottom right corner of the bar, by shading a square, tighter with all the squares below and/ or to the right it. The top left-hand square is poisoned, and the player forced to eat the square loses.
How do I determine who is currently winning while the game is being played? (Creating the game in Unity using c#)
For a square grid, there is a strategy which allows the player who is taking the next turn to always win. (it is actually mathematically proven that there is a winning strategy for the first player for any width and height except 1x1. But so far nobody found out what that strategy is, except for the special cases of a square board or a 2xn board).
A losing position in this game is any position where the board looks like this:
xxxxx
x
x
x
x
The player who finds themselves in this situation has lost, because whatever the player does, the opponent can return to a game-state like this until there is only the poisoned tile remaining. The player in this situation has only 3 options:
To which the opponent can respond by shortening the other arm so both have the same length again. Now the opponent is back in the same situation. This goes on until both arms are lost and only the poisoned tile remains.
Knowing the strategy for this situation, we can also derive a winning state for the game: "If the board is currently a square larger than 1x1, then the player whose turn it is is winning, because they can pull off the above strategy by taking the tile to the lower right of the poisoned tile."
OK, but how do we determine who is winning if the current player does not have one of the two positions outlined above? Much smarter mathematicians than us have tried to find a strategy and failed. So what can we mathematically challenged game programmers do?
We simply throw our computational power at the problem and brute-force it!
We map each possible move they can make right now and check if it's a winning move or a losing move. And if any moves are inconclusive, we can check all possible moves from there. And if those are also inconclusive, we again check all possible moves. And so on and so on until all branches of the game tree either end in a win or in a lose. That way we can figure out if there is a route through the tree through which the current player can force a win (which means they are winning) or if the other player can do that (they are losing). The number of possible moves in this game is small enough that this is feasible (at least as long as the board doesn't get much larger).
