# Mathematical equation for CHOMP AI?

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#)

• Your game rules are not super clear. Could you please, using words, how you would determine who is winning? What are the winning conditions at mid-game? Then once the words will be chosen, it'll be easier for us to provide a coding solution. May 6, 2020 at 7:38
• Remember that there is never just one way to solve a problem in Unity. We do not know how exactly you implemented this game, so we do not know how you would need to extend your implementation to detect the win-condition. May 6, 2020 at 9:06
• I have to create a game using AI, and the game I chose is Chomp a game you usually play on pen and paper. I am new to this type of code and I'm really unsure about a lot of things. Before I can code my project I need to determine a winning condition which I did, the player that is forced to eat the last square loses. But while playing I need to determine which player is winning so far even when the winning condition hasn't been met. The map grid is 11 x 11. May 6, 2020 at 9:32

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 tile to the lower right of the poisoned tile is missing
• The two "arms" reaching horizontally or vertically from the poisoned tile have the same length.

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:

• lose
• shorten the vertical arm
• shorten the horizontal arm

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).