Monday, August 15, 2016

Games@Dal 2016: Carlos talks about 3-player Nim

Games@Dal 2016 talk: "3-player Nim with podium rule" - Carlos Santos w/Richard J. Nowakowski and Alexandre M. Silva

Carlos's talk entered the somewhat-forbidden world of three-player games.  He spoke of different ways of considering these games, but continued using Lee's Podium Rule from 1978: If you can't come in first, you should instead try to come in second.  (Try to get as high up the podium as you can.)

In impartial games, this leads to a third outcome class: O ("Other") which has no P options, but at least one N option.  Playing on Nim heaps, to find P positions, we now have to perform the nim sum, but mod 3 instead of mod 2.  Thus, *7 + *17 + *22 + *23 is a P position.  Zeroness in the sum only actually tells us about P positions; non-zero values might be O or N, so we need further criteria.

Carlos described these further criteria, then continued by describing how to define canonical forms for Nim.

5 comments:

  1. This comment has been removed by a blog administrator.

    ReplyDelete
  2. This comment has been removed by a blog administrator.

    ReplyDelete
  3. Don't know if you'll read this, but unless I'm reading it totally wrong, taking the nim-sum mod 3 doesn't reveal whether a position is a P-position (assuming that you prefer the player that goes after you loses; if you prefer they win, the game is somewhat different but as every 1-heap game is a P-position the nim-sum mod 3 obviously does not say anything about P-positions). P-positions in 2 heap 3-nim include (0,0), (1,2), (3,4), and (5,6), which have nim-sums mod 3 of 0,0,1,2 respectively. O positions would be (2n+1,2n+1) for all n.

    I am actually interested in 3-player impartial games (and can't find any patterns in 3 heap 3-nim), so if you have any other info or references to papers that'd be great!

    ReplyDelete
  4. It's more likely that I made a mistake in my report of Carlos's talk. :)

    It seems like every handful of years there's another take on 3-player games. I don't know how far this one has got. I'm not sure whether Carlos, Richard, and Alexandre have published this stuff yet.

    I don't have any of these links at the tip of my fingers. If you can't find them via Google, you might want to try contacting one of the three of them. :)

    ReplyDelete