300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | РусскийiChomp©
Nombre total de parties: 775601
Nombre de victoires: 486693
Nombre de victoires: 486693
Comment Jouer :
- À tour de rôle, les joueurs prennent des bonbons du plateau ci-dessous.
- Les bonbons enlevés dépendent du quadrant où se trouve le bonbon sélectionné.
- Le quadrant supérieur gauche enlève tous les bonbons au-dessus de et à la gauche du bonbon sélectionné, le quadrant supérieur droite enlève tout au-dessus et à gauche, le quadrant inférieur gauche enlève tout en dessous et à gauche, et le quadrant inférieur droit enlève tout en dessous et à la droite du bonbon sélectionné.
Comment Gagner :
- Celui qui prend le dernier bonbon gagne la partie.
C’est à votre tour, Joueur 1
Largeur:
Longueur :
Access to 'Some food for thought' (SFFT) for the iChomp game can be purchased in the online shop
The algorithm that you will learn in this tutorial is able to play a large class of games optimally, so it will pay off spending some time learning it. The key will be the famous Sprague-Grundy theory. If you want to know hints for playing iChomp without learning Sprague-Grundy theory, then scroll down to the corresponding section. Before going into detail we need to clarify a few terms.
Notation
-
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.
About iChomp
- 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.
About the Sprague-Grundy theory
-
The class of games that it applies to are impartial combinatorial games. This theory does two things for us:
- 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.
- 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.
Why iChomp?
-
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.
-
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.
In SG-theory a mathematical operation called XOR is needed. In case you are not familiar with it, the following section will be useful.
What is XOR?
-
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 20 = 1):
- Find the highest exponent p of 2, so that 2p ≤ n.
- Record a 1 and subtract 2p from n.
- If p = 0 then stop else subtract 1 from p and continue.
- If 2p > n then record a 0 else subtract 2p from n and record a 1.
- 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 23, or 8. We then record a 1 and subtract 8 from 13, which gives us 5. Next we check 2(3−1) = 22 = 4. Since 4 ≤ 5, we record a 1, and subtract 4 from 5, which gives us 1. The next lower power of 2 is 21 = 2. 2 > 1, so we record a 0. The next power of 2 is 20 = 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×23+0×22+1×21+1×20 = 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.
-
The following algorithm can be used to convert a number n in base 10 into base 2 format. (Be reminded that 20 = 1):
The algorithm to compute the SG value of a Chomp position.
-
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.
The algorithm to compute the SG-value of an iChomp position
-
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.
-
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.)
-
Proof (by induction (and in much detail)):
Why did we add a '1'?
How to play iChomp
-
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.
- If the other two quadrants have also equal SG-values then the SG-value of the whole position is zero and the position is a losing position. Then remove just one tile from any quadrant to delay the defeat and have more chances for the opponent not to play optimally.
- If the other two quadrants have unequal SG-values then pick the quadrant with a larger SG-value. Make a move in there by clicking a tile with a number inscribed which is equal to the SG-value of the other quadrant. The result are 2 pairs of quadrants with pairwise equal SG-value and total XOR value of zero - a losing position.
- (general) Case:
- Compute the 4 iChomp-SG-values, say w,x,y,z of the 4 quadrants (each being the Chomp-SG-values of that quadrant plus 1) and convert them to Base Two.
- Then find the most left position such that an odd number of these 4 numbers have a 1 in this position. For example, if the 4 numbers are
w=11011
then the most left position with a 1 is the 5th position (we start counting positions from the right). w and y have a 1 there, i.e. two numbers (w and y) have a 1 there. Two is an even number, we therefore need to ignore this position. The next position is the 4th position, again counted from the right. Here too, evenly many numbers have a 1 there (w and x). We need to ignore this position as well. The 3rd position has 3 numbers with a 1 there (x, y, z). 3 is an odd number, so we pick any one of these 3 numbers, for example, y=10100.
x= 1101
y=10100
z= 100- If in all positions there is an even number of 1s then the XOR value of all 4 numbers is zero and this is a losing position. For example
w'=11011
have an even number of 1's in each position. The XOR of these 4 numbers is zero, this is a losing position. In this case one removes just one tile from any quadrant to delay the defeat and have more chances for the opponent not to play optimally.
x'= 1011
y'=10110
z'= 110 - If at least one position has odd many 1's then we found a number, like y above (not y').
- We XOR the other 3 numbers, in our case w XOR x XOR z = 11011 XOR 1101 XOR 100 = 10011. This value is always less than the number we picked, here y = 10100 (see proofs further below).
- In the quadrant with the picked value, here y, we make a move that results in a position with SG-value equal the XOR of the other 3 values, in our example 10011.
- To know which tile to click we either convert 10011 to Base Ten (= 1×1 + 1×2 + 0×4 + 0×8 + 1×16 = 19) and click the tile with the number 19, or we compute in binary form 10100 − 10011 = 1 and convert this to Base Ten (= 1) and know that the tile to click should have the value 1 less than y (=20), i.e. to click the tile with the number 19 inscribed.
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 2p. 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)
= 2p − (2p−1 + 2p−2+ ... +20)
= 2p − (2p−1 + 2p−2+ ... +20)× (2-1)/(2-1)
= 2p − (2p−1)/(2-1)
= 1.
That means y is at least one bigger than (y XOR u). ∎
-
By using XOR rules learned earlier we get
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.
All the instructions above assume that one knows the SG-value of the 4 quadrants which means one knows the SG-value of each quadrant after each possible move.
Can you find SG-values of some Chomp positions (in 'Misère Play')?
-
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'.
-
Having only 1 tile (in the upper left corner) is a losing position with therefore SG-value 0.
How can one play iChomp reasonably well without knowing SG-values?
-
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.
Some test questions
-
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
Suivez ou abonnez-vous à l'Infolettre