iChomp

Combinatorial Games: two-person games with perfect information and win or lose outcome and no chance moves.

Impartial Games: combinatorial games in which the allowable moves depend only on the position and not on which one of the two players is currently moving. Also, the payoffs are symmetric. In other words, the only difference between player 1 and player 2 is that player 1 goes first. Example: Chomp.

Partisan Games: games that are not impartial. Example: Chess.

Normal Play: The player to make the last move WINS, i.e. the player who cannot make a move, i.e. who has nothing to take away, loses.

Misère Play: The player to make the last move LOSES.

Chomp: the game introduced on our game site which uses one quadrant and Misère Play.

Does the Nim game as it is played on our game page use normal or misère play?
- Our Nim game uses misère play, because the player who takes the last match loses the game.
Does the Chomp game as it is played on our Chomp game page use normal or misère play?
- The Chomp game as it's played on our game page uses misère play, since the player who takes the last candy loses.
Why does it not make sense to use normal play for Chomp?
- Using normal play would mean that whoever takes the last tile wins. Therefore, the player that moves first could instantly win by taking the tile in the upper left corner.
Does the iChomp game as it is played on this webpage use Normal or Misère Play?
- In iChomp, the player who takes the last tile wins, so this game uses Normal Play.
Do you have a suggestion for how one could change the Chomp board to use Normal Play and still play the same game?
- One could start with a position where the (poisoned) candy in the upper left corner is already missing from the start. Taking the last candy from such a board means that one would win in Normal Play. In Misère Play and with this tile then the other player would have to take it and lose which is the same outcome.
  
  Thus, having a left upper corner tile and using Misère Play or not having this tile right from the start of the game and using Normal Play are both exactly the same game.

The iChomp game is designed to be the union of four Chomp games played at the same time, all under the Normal Play rule. This makes the game more beautiful in two aspects, which will be explained below. Also, iChomp is not that more difficult to play than Chomp if one applies the Sprague-Grundy theory, which is also described below.

The class of games that it applies to are impartial combinatorial games. This theory does two things for us:
1. It gives us an algorithm which determines for each game (i.e. each position) a number (we will call it the SG-value) such that the number is 0 if and only if it is a losing position (called 'P-position' in the literature on combinatorial game theory with 'P' indicating that the 'p'revious player played a winning move). That means if this SG-value is 1, 2, 3, ... then this is a winning position (called 'N'-position in the literature). In that case, whoever moves 'n'ext can enforce a win if playing optimally.
2. The second purpose of the SG-theory is to describe how to win a game that consists of several positions played at the same time. A move in such a combined game is made by making one move in any one of the positions that are combined.
  
  What one needs to know is the SG-value of each one of the combined positions. To get them one needs to know the SG-value after each move in any one of these combined positions. These are needed as well to play optimally.
  
  For example: In the Nim game one has one or two or more piles of matches. If we know the SG-value for playing each individual pile alone, then the SG-theory tells us how to play optimally with all of these piles by taking away the appropriate number of matches from any one of these piles.
What is amazing about the SG-theory is that the positions that can be combined to one game are not only piles of the Nim game but any positions of any impartial combinatorial games. For example, one could combine several chomp positions into one "super-chomp" game, or one could play a game optimally that starts with 5 different chomp positions and 3 piles of matches and any one of the 8 places can be played at any time.

iChomp is a new version of Chomp introduced by Caribou Contests which is played on this webpage. The 'i' in iChomp stands for 'isotropic' i.e. all directions are treated equally.

In normal Chomp the removal of one tile also removes all tiles to the East and South of it. So, the directions East and South play a special role.

In iChomp all tiles in other directions may be removed as well depending on where the removed tile is that is closest to the center. If this tile is, for example, in the North-West direction of the center then all tiles in the North or West are removed as well.

Removing artificial rules, for example, the rule that East and South are special is usually considered to make a game mathematically more beautiful.

There is another beautification that iChomp has in comparison with Chomp.

In Chomp the tile in the left upper corner plays a special role compared to other tiles. If that is the only tile on the board the game is over. If another tile is removed the game continues. One could start Chomp without that corner tile so all tiles are treated the same, but this itself would then be an artificial rule as to why to start the game without that tile and not without other tiles as well.

In iChomp all tiles are present at the start and all are treated the same. Any tile can be removed without automatically ending the game.

Some questions arise:

Is iChomp a trivial game because it is the combination or 4 trivial Chomp games in 'Normal Play'?
- The answer is no. For example, the Nim game with a single pile of matches is trivial. Under 'Normal Play', one can remove the whole pile in one move and win. In Nim under 'Misère Play', one can remove all but one match and win. Nevertheless, the combination of such 1-pile Nim games to a multiple-pile Nim game as on our Nim games page is not trivial.
  
  Similarly here: A single chomp game using the corner tile and 'Normal Play' is trivial because one could remove all tiles in one move and win. But the combination of 4 such games is not trivial.
Summary of Comparison
- IChomp is mathematically more beautiful than Chomp because it does not artificially single out the South-East directions and does not give one tile a special role. The price seems to be that iChomp is much more difficult to play than Chomp but SG-theory helps out. It is enough to know the SG-value of Chomp positions up to some size to easily calculate the SG-value of iChomp positions up to 4 times that size and thus to know how to play iChomp optimally up to that 4 times bigger size.

Exclusive Or, or XOR for short, is a logical operation that is performed on binary data. Using binary data, we could have one of two values, true (=1) or false (=0). The XOR operation on two binary values is defined through the following table.

a b a XOR b
1 1 0
1 0 1
0 1 1
0 0 0

While it is easy to use this operation on values of 1 (true) or 0 (false), for our computations we need to be able to perform XOR on two numbers. This can also be done, however a new step is required before we can perform the XOR.

What first has to happen is the numbers will need to be converted into binary, i.e. to convert it from base 10 to base 2.

How can one convert a number from base 10 into base 2?
- The following algorithm can be used to convert a number n in base 10 into base 2 format. (Be reminded that 2⁰ = 1):
  1. Find the highest exponent p of 2, so that 2^p ≤ n.
  2. Record a 1 and subtract 2^p from n.
  3. If p = 0 then stop else subtract 1 from p and continue.
  4. If 2^p > n then record a 0 else subtract 2^p from n and record a 1.
  5. Go back to step 3.
  The sequence of 1's and 0's you recorded following this algorithm will be the binary representation of the number n. Example:
  
  Let us convert the number 13 into base 2 format. We start by finding the highest power of 2 less than or equal 13, which is 2³, or 8. We then record a 1 and subtract 8 from 13, which gives us 5. Next we check 2⁽³⁻¹⁾ = 2² = 4. Since 4 ≤ 5, we record a 1, and subtract 4 from 5, which gives us 1. The next lower power of 2 is 2¹ = 2. 2 > 1, so we record a 0. The next power of 2 is 2⁰ = 1, which is equal to our n of 1, so we record a 1 and subtract 1 from 1, giving us 0. Since p = 0 we stop the algorithm. Therefore 13 (base 10) = 1101 (base 2).
  
  After we convert two numbers into binary representation, we can now perform the XOR operation on the corresponding digits of the two binary numbers. The result is a binary number that can then be converted back into base 10 if that is more convenient for future use of that XOR value. Example:
  
  Let us compute the XOR of the numbers 6 and 13. The binary representation for these two numbers are 6 = 110, and 13 = 1101. At first we add 0's on the left of the smaller number so that both have the same number of digits, so 6 = 0110. We can then perform the XOR by lining them up and performing the operation on each of the individual digits:
  
  0110
  XOR 1101
  ------
  1011
  
  Thus 6 XOR 13 = 1011 (base 2) = 1×2³+0×2²+1×2¹+1×2⁰ = 8+2+1 = 11 (base 10).
Let us check our understanding of XOR with a few questions.

What is m XOR m for any number m?
- For any number m we have m XOR m = 0 because 0 XOR 0 = 0 and also 1 XOR 1 = 0.
Is n XOR m = m XOR n for any numbers n, m?
- Yes, because 1 XOR 0 = 0 XOR 1 (=1).
What is 0 XOR m for any number m?
- 0 XOR m = m because 0 XOR 0 = 0 and 0 XOR 1 = 1.
If a number m is XOR'ed with a number n through m XOR n then which digits of m get flipped?
- If a digit in m is XOR'ed with 0 then the digit is unchanged (because 0 XOR 0 = 0 and 1 XOR 0 = 1). If a digit in m is XOR'ed with 1 then the digit is flipped (because 0 XOR 1 = 1 and 1 XOR 1 = 0). Thus XOR n flips all digits for which the corresponding digit in n is a 1.

a	b	a XOR b
1	1	0
1	0	1
0	1	1
0	0	0

The following algorithm computes the SG-value of any position P in any impartial combinatorial game. We explain it using the Chomp game.
- Every game position that is a losing position gets the SG-value 0. In Chomp, a single tile (in the North-West corner) is the only position without a follow-up move and therefore is a losing position with SG-value 0.
- We need the SG-values of all positions that can be reached from position P in one move. So if position P has n tiles then there are n-1 possible moves: except the tile in the North-West corner, all other tiles can be removed together with all the tiles to the South/East of that tile.
- The SG-value of a position P is the smallest non-negative number that is not in this list of n-1 reachable SG-values.
This algorithm is recursive because for computing the SG-value of position P we need the SG-values of all positions reachable from P in one move. It still works because the SG-values that are needed concern smaller positions of fewer tiles and the SG-value of the smallest possible position (one tile in the North-West corner) is known.

Try to verify the 3rd property in the game above by selecting a larger board width and height and clicking 'Randomize Board'.
- When you move the mouse over a tile, then this tile and the other tiles that would be removed are highlighted. The number in that tile is the SG-value of the quadrant under 'Normal Play' (not 'Misère Play') that would result if this tile is clicked. You can check that the number shown in the text 'SG value Base Ten:' next to the quadrant is the smallest number not shown in the quadrant. You can also check that if you click a tile then the number that was in it now shows as 'SG value Base Ten:' of the new position.
How to speed up the determination of SG-values:

Because the same position can be reached from different positions in one move, and can come up repeatedly when computing the SG-value of a larger position, it would be a waste of an effort to compute it again and again. Therefore, once the SG-value of a position P is calculated, it should be stored for later use.

If one wants to compute the SG-value of all positions up to some size, then the following approach is useful. We start by assigning the only position with one tile (in the North-West corner) the SG-value zero. Then, we use the above algorithm to compute the SG values of all positions with 2 tiles, then with 3 tiles and so on.

An iChomp position consists of 4 Chomp positions, one in each quadrant of the board.
- At first we determine the SG-value of each one of the 4 Chomp positions using the Chomp 'Misère Play' rule. The empty quadrant is not a Chomp position, so we give it the value −1.
- We then add 1 to each value.
- For each one of the 4 resulting numbers we compute the binary representation.
- We compute the XOR value of the 4 binary values and obtain the SG-value of that position (in binary form). If this value is zero, it is a losing position, otherwise it is a winning position.

Why did we add a '1'?

We add a 1 in order to obtain the SG-value of a Chomp position under 'Normal Play' from the SG-value under 'Misère Play'. The following theorem explains it.

Theorem:
--------
To get the SG-value of a Chomp position under 'Normal Play' (i.e. taking the last tile wins the game which is not the common way to play Chomp) one needs to add 1 to the SG-value of the same position under 'Misère Play' (i.e. taking the last tile loses which is the common way to play Chomp).

Can you try proving the theorem by induction?
- Proof (by induction (and in much detail)):
  
  Base Case (1 tile):
  -------------------
  Under 'Normal Play' an empty board without tile is a losing position and has therefore SG-value zero. Furthermore, under 'Normal Play' for a board with one tile (in the upper left corner) the only possible move is to remove this tile yielding a position with SG-value 0. So, under 'Normal Play' the smallest non-negative SG-value that cannot be achieved by a move is 1, so that is the SG-value of a position with one tile under 'Normal Play'.
  
  Under 'Misère Play' having one tile is a losing position with SG-value 0.
  
  Thus, for 1 tile the 'Normal Play' SG-value is 1 bigger than the 'Misère Play' value.
  
  Inductive Step
  ---------------
  
  Induction Hypothesis (n tiles):
  ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
  We assume that there exists a number n so that for all positions with ≥1 and ≤n tiles the SG-value under 'Normal Play' is one bigger than under 'Misère Play'. Induction Claim (n+1 tiles):
  ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
  We will show that this is then also the case for all positions with n+1 tiles.
  
  Induction Step ( n tiles → n+1 tiles):
  ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
  For any position 'Misère Play' and 'Normal Play' allow the same moves except that 'Normal Play' also allows to take all tiles through the upper left corner tile.
  
  If the position has n+1 tiles, then making a move generates a position with at most n tiles to which we can apply the induction hypothesis:
  
  The list of obtainable SG-values under 'Normal Play' is therefore obtained from the list of obtainable SG-values under 'Misère Play' each increased by 1 and by adding the value 0 through taking all tiles.
  
  Therefore the smallest non-negative number NOT obtainable under 'Normal Play' is 1 higher than the smallest non-negative number NOT obtainable under 'Misère Play'. In other words, for the original position with n+1 tiles the SG-value under 'Normal Play' is one higher than the SG-value under 'Misère Play'. ∎ (This completes the proof.)

The aim is to make a move such that the SG-value of the resulting position is zero. Whatever move one makes, it has to be in one of the 4 quadrants. That means that the SG-value of the position where the move has been made and the SG-values of the other 3 unchanged quadrants all XOR'ed must give zero. This is the case if and only if the other 3 SG-values XOR'ed give exactly the SG-value of the new quadrant after making the move (see further below for a proof of this statement). The procedure is therefore as follows:
- (simple) Case: Two of the 4 quadrants have the same SG-value. Then XOR of these two equal values will give zero so both quadrants are to be ignored.
- (general) Case:
Why is that a winning move?
- Please remind yourself about properties of XOR as shown earlier to answer the following questions.
  
  If u = w XOR x XOR y XOR z, then what is y XOR u ?
  - By using XOR rules learned earlier we get
       y XOR u
    = y XOR w XOR x XOR y XOR z
    = y XOR y XOR w XOR x XOR z
    =        0     XOR w XOR x XOR z
    =            w XOR x XOR z.
  If y is replaced by y XOR u then what is the new XOR of all 4 SG-values?
  - The new XOR would be
    (y XOR u) XOR w XOR x XOR z
    = (w XOR x XOR z) XOR (w XOR x XOR z)
    = 0
    because of m XOR m = 0 for any number m.
    
    That means the new SG-value of the whole board would be zero, so that would be a losing position as intended.
  Why should a move exist which changes an SG-value y into a lower value?
  - According to the definition: A position has an SG-value of y if and only if there exist moves that generate positions with SG-values 0,1,..,(y-1). So, if y > (y XOR u), then there must exist a move generating an SG-value (y XOR u) < y.
  What remains to be answered is:
  
  Why should there exist a quadrant with an SG-value y that satisfies y > (y XOR u)?
  - A reminder:
    Earlier, when we learned about properties of XOR, we saw: XOR u flips all digits for which the corresponding digit in u is a 1.
    
    If u ≠ 0, then u contains a highest power of 2, say 2^p. This power of 2 must occur in an odd number of the 4 SG-values, so in at least one, say y.
    
    This means, when computing y XOR u, this 1 in y gets flipped to a 0 by the corresponding 1 in u. There may be other binary digits flipped in y located to the right of this 1. The largest possible value of y − (y XOR u) occurs if the digits in y to the right of this 1 are zeros and the digits in u to the right of that 1 are ones. In that case u = 111..111 changes y = *100..00 (where * stands for any number of digits) to y XOR u = *011..11. Their difference is:
    
    y − (y XOR u)
    = 2^p − (2^p−1 + 2^p−2+ ... +2⁰)
    = 2^p − (2^p−1 + 2^p−2+ ... +2⁰)× (2-1)/(2-1)
    = 2^p − (2^p−1)/(2-1)
    = 1.
    That means y is at least one bigger than (y XOR u). ∎
Try this algorithm out by playing and winning against 'Difficulty: Hard'.
- To start, select 'Difficulty: Hard' which guarantees optimal computer play. If you still win then you played each move optimally.
  
  The SG-value of each quadrant is shown in base 10 and base 2. Check that this number is the smallest value that is not shown in the quadrant.
  
  Underneath, the XOR of all 4 SG-values called u is shown. Verify the value of u by simply changing any pair of two 1's in the 4 SG-values to 0 if the two 1's are in the same position. Then place the remaining 1's into one binary number and convert that to base 10.
  
  To make a move proceed as described above:
  - Find one of the 4 SG-values, say y, which has a 1 in the same position as the left most 1 in u.
  - Compute y XOR u in binary form and then convert it to base 10.
  - In the y-quadrant click the tile with the computed y XOR u.
  - Play your moves in this way until you won.
  - Play again but this time start with a random move. Unless you were lucky and played by accident a winning move, you will not be able to win this game even if you then try to play optimally.

In order to compute the SG-value of a position, one needs to know the SG-values of all positions that can be reached from it in one move. This is a recursive process. Therefore we need to start with positions with the fewest number of tiles and work our way up.

Can you find the SG-values of 1,2,3,... tiles in one row?
- Having only 1 tile (in the upper left corner) is a losing position with therefore SG-value 0.
  
  Having 2 tiles (in the top row or left column), the only possible move is to take one tile obtaining the mentioned position with SG-value 0. So the smallest non-negative SG-value that can not be achieved by a move is 1, so that is the SG-value of a position with 2 tiles is 1.
  
  Having 3 tiles all in the top row, one can take either 1 or 2 tiles and obtain SG-values 1 and 0, so the SG-value is therefore 2.
  
  Similarly, the SG-value of n tiles in the top row is n-1.
  
  Let us consider 3 tiles, 2 in the top row and 2 in the left column. We can remove only 1 tile and reach an SG-value of 1 but not 0, so the smallest SG-value that can not be obtained is 0 which therefore is the SG value of this position. This is a losing position.
Can you find the SG-value of a position with m+n−1 tiles of which n are in the top row and m tiles are in the left column?
- One can only remove tiles from the top row or from the left column. The SG-value is therefore the same as having two quadrants, one with n tiles in the top row and one with m tiles in the left column. Thus, the SG-value is (m-1) XOR (n-1). This is the same as playing NIM with two piles and 'Normal Play' rule where matches can be removed from only one pile in one move.
Can you find the SG-value of a position with tiles only in the top two rows?
- The formulas for these positions are more complicated. As far as we know, they had not been published before. You could try to verify them for a small number of tiles.
  
  Let n and m be the number of tiles in the top and second row.
  
  If n is even then
    k = (n-2)/2
    if m is even then
      a = m/2
      SG-value = 2*k+a+1
    else (m is odd)
      a = (m-1)/2
      if a ≤ (k/2) then SG-value = 2*k-a
      else SG-value = 3*(k-a)
  else (n is odd)
    k = (n-1)/2
    if m is even then
      a = m/2
      if a ≤ (k/2) then SG-value = 2*k-a
      else SG-value = 3*(k-a)
    else (m is odd)
      a = (m-1)/2
      SG-value = 2*k+a+1
  
  Check whether the formulas are correct using the game board above.
  - Select the minimal board height so that there are quadrants with only two rows of tiles. After applying the above formulas you should obtain an SG-value that is one lower than the value shown under 'SG Value Base Ten:' because the formulas are for 'Misère Play' whereas iChomp uses 'Normal Play'.

We start with an observation: The rules of Chomp make no difference between the East and South direction.

What is the consequence for SG-values of two positions that are mirror symmetric to each other under mirroring on the diagonal that starts from the top left corner?
- Because East and South directions are mirrored into each other this means that both must have the same SG-value.
What does that mean for iChomp when 2 quadrants have positions that are symmetric under rotation of the quadrants and/or diagonal mirroring?
- Both quadrants can be ignored. Why? Both quadrants have the same SG-value under misère play and after adding 1 also the same SG-value under normal play. XOR of these two equal values gives zero. Therefore, both quadrants have no contribution to the SG-value of the whole board position.
Which playing strategy should therefore work?
- One should make a move which creates two pairs of quadrants so that the quadrants in each pair have symmetric positions with equal SG-values, say A and A, and B and B. Then, the SG-value of the combination of all 4 quadrants is A XOR A XOR B XOR B = 0 XOR 0 = 0 or (A XOR B) XOR (A XOR B) = 0 so always 0. One created a losing position.
  
  Equally one should NOT make a move which leaves two symmetric quadrants and two others of which one can be changed into the other one in one move by the opponent. This would allow the opponent to create a losing position.

Here come some questions where you can test your understanding of Chomp, iChomp and the SG-theory.

Is the knowledge of SG-values enough to play Chomp perfectly?
- Yes. If the SG-value of a position is zero, then it is a losing position (because no move exists to make it zero, so no winning move exists, so it is a losing position). If the SG-value is bigger than zero, then this means that there is a move to make the SG-value of the resulting position zero, so there is a winning move.
Does one need to know SG-values of Chomp positions to play Chomp perfectly?
- No. To play Chomp we need to find a move that generates a losing position. If no such move exists then it is a losing position and any move can be played. But, if such a move is found, one can stop searching. The SG-value is not needed.
What are SG-values good for then?
- They are only needed to play several Chomp games in parallel as a new game, like in iChomp.
How much more difficult is it in Chomp to compute the SG-value of a position than a winning move?
- To play Chomp we need to find a move that generates a losing position. If no such move exists then it is a losing position and any move can be played. But, if such a move is found, one can stop searching.
  
  The effort to find the SG-value of a position is usually higher. For finding the SG-value one always has to search ALL moves in order to find all SG-values of resulting positions and find the smallest non-negative value that can not be reached in a move. This value is the SG-value of the position.
  
  For example, in our (Caribou) computations we were able to determine all losing positions (and thus winning positions) with up to 93 tiles. With a comparable computational effort we were able to compute the SG-value of all Chomp positions with up to 82 tiles.
  
  In this sense determining SG-values is computationally more expensive than determining a winning move.
If Nim with 4 piles is harder to play than NIM with 1 pile, is then iChomp with 4 quadrants much harder to play than Chomp with 1 quadrant?
- In Nim, the SG-value of one pile is simply the number of matches in that pile. (Please confirm this by applying the above comments how to compute SG-values to a single stack in Nim.) The only complication of playing several piles in Nim is to XOR the different SG-values of these piles to get the SG-value of all piles combined.
  
  In Chomp it is computationally expensive to get the SG-value of a position (which is in one quadrant). In iChomp, once the SG-values of the 4 quadrants are known, these values need to be XOR'ed as well, but that is much easier than finding the SG-value of one quadrant.
  
  To play Chomp optimally one does not need to know the SG-value of the position, knowing a winning move is good enough, but as shown above the difference is not that big.
  
  So the answer is NO, it is not much harder to play iChomp optimally than Chomp.
In Chomp, can a move create a position that has a higher SG-value?
- Yes. The SG-value of a position is the smallest value that cannot be generated by a move.
In Chomp, can there be different moves that create position with the same SG-value?
- Yes. You can see examples by increasing the board size and click the button 'Show SG values of Moves'. For example, the position
  
  ###
  ##
  #
  
  has 3 winning moves, all creating a position with SG-value of 0. We even found a position with 7 winning moves:
```
 + 10  6 15  2 20 21 14 22 11  0 23  7 26
13  7 11  9 14  0 19  5
17 11 14 18  0 24 23  8
 3 19  2  0 20
11  4  0  5  1
 8  0
 0
 4
23
25
24
```

iChomp^©

How To Play:

How To Win:

Player 1's Turn

	0110
XOR	1101
	------
	1011

iChomp©

How To Play:

How To Win:

Player 1's Turn

iChomp^©