17
$\begingroup$

Is there a game-theoretic interpretation of nimber multiplication? There is such for addition (a single move in a+b is either a move in a or a move in b).

$\endgroup$
2

5 Answers 5

13
$\begingroup$

As Alex says, there's no good one. One way to see the problem is to compare nimbers with (surreal) numbers. Addition in both is just game addition, so you can consider nimbers and numbers together and add them consistently. But there is no consistent multiplication. (What would the unit be?) A good game theoretic multiplication would explain how to multiply arbitrary games.

Instead, we have nimber multiplication, which is constructed ad hoc and based on the algebraic structure of the nimbers: nimbers include all additive groups of characteristic 2, and the multiplication makes them into the universal field of characteristic 2 (in the sense that any field of characteristic 2 embeds in the nimbers); any totally ordered field embeds in the surreal numbers.

$\endgroup$
3
  • 4
    $\begingroup$ If I understand correctly, there is a single definition for multiplcation of games which specializes to that of both numbers and nimbers. It's just that * is only a multiplicative unit with respect to other nimbers. (And the combinatorial interpretation of multiplication of games isn't very nice.) $\endgroup$ Nov 23, 2009 at 4:59
  • $\begingroup$ Oh, ok. Then I don't know what it is. (And I vaguely remember asking Conway essentially this question years ago, and this being essentially his answer, but I could be misremembering something.) $\endgroup$ Nov 23, 2009 at 16:36
  • 2
    $\begingroup$ It is not true that "any field of characteristic 2 embeds in the nimbers". For example, $GF(8)$ does not. The fields which embed are $GF(2^{2^n})$. $\endgroup$ Aug 27, 2022 at 7:51
10
$\begingroup$

Not a pleasingly natural one, I think. Somewhere or other I've seen a discussion of a game played with rectangular cards in which the move is to replace an a*b card by three cards of sizes a'*b, a*b', and a'*b' for some 0≤a'<a and 0≤b'<b, but it was clear that this game had been concocted to match nim-multiplication.

$\endgroup$
5
$\begingroup$

In part 2 of Game Theory by Thomas Ferguson, example 2 'Turning Corners' on page 33, Thomas Ferguson mentions a so-called 'flipping-coin' game, where the Sprague-Grundy functions g(x, y) equals nim multiplication of x and y.

A move consists of turning over four distinct coins at the corners of a rectangle, i.e. (a, b), (a, y), (x, b) and (x, y), where 0 ≤ a < x and 0 ≤ b < y, the coin at (x, y) going from heads to tails.

This is under the (in part 2 of this book) usual assumptions that the game is for 2 players, and the last player that makes a move wins (i.e., you lose when you can't make a valid move according to the rules of the game). This might be the game that Alex Fink referred to, but I didn't find it to be such a contrived example, so it might be worth looking at (to be honest, at this point I don't understand the game completely and I don't have time for it now: this might be the same game that Lenstra mentions in the article linked to by Kevin O'Bryant: both are 'coin-turning' games).

Edit: In fact, the Sprague-Grundy value of a move in any 'product' of two coin-turning games G1 and G2 is given by the nimber product of the SG-value of the corresponding move in G1 and the corresponding move in G2. What this means exactly is explained more clearly in the document I linked to.

$\endgroup$
1
4
$\begingroup$

There is a recursive definition of the product of two games here:

http://en.wikipedia.org/wiki/Nimber

Surreal numbers have a multiplicative identity see the section on multiplication here:

http://en.wikipedia.org/wiki/Surreal_number

In terms of ease of computation there are the following rules which may make computing the product of finite nimbers. There are two rules any number of the form 2^(2^i) multiplies normally with any number of the form 2^(2^j) j and i different. However 2^(2^i) times itself is equal to 3/2(2^(2^i). Using these rules we can break up two integers into the sums of powers of two and multiply then for each of the powers of two we break up the exponent into powers of two then we can use the two rules to evaluate the products of the exponents and that should make the computation easier.

$\endgroup$
1
  • $\begingroup$ Is there an interpretation of that identity which defines game a*b in terms of a and b? What I'm looking for is something easier to comprehend than a game in which the number of subgames increases every move. $\endgroup$
    – Robert
    Nov 22, 2009 at 20:09
4
$\begingroup$

check out this comment. this is also mentioned towards the end of chapter 6 in conway, but i don't have that on hand at the moment.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.