2
$\begingroup$

The game of nim is played with two players againts each other ,by removing 1 or many stones from only one pile in each turn from n piles each pile with $n_1,...,n_k$ and a player cannot skip a turn. The game is determined to be winning or losing for a first player and otherway around for another player from the starting to the end of the game given the both plays optimally.

XOR the number of stones in the pile

  • Not equal to zero then the first player win
  • Equal to zero the the first player will lose

But I don't see the intuation behind the XOR being used here.

For example in a simple game with one pile of N stone and we can only take 1,2,3 stones in one move,the player to take the last stone(s) wins. The winning and the losing states kinda seems intuative, $$0 - Lose, 1 - win, 2 - lose, 3 - win, 4 - lose, 5 - win, 6 - win, 7 - win, 8 - lose ..$$ Althought the states in the nim game are clearly defined with the XOR operation but the ldea of using it here seems not that intuative.

$\endgroup$
5
  • 1
    $\begingroup$ Check this: math.stackexchange.com/q/416042/42969, or this: math.stackexchange.com/q/1870129/42969 $\endgroup$ Commented Nov 30 at 17:53
  • $\begingroup$ Btw, it's “intuition” and “intuitive.” $\endgroup$ Commented Nov 30 at 17:55
  • 3
    $\begingroup$ You may also want to check out WIkipedia on Sprague-Grundy. One of the key ideas is that the S-G number of a position is recursively defined to be the minimum natural number (MEX for Minimum EXcluded) not included in the values of the position we can arrive at a single move. And it turns out that the operation governing the sum of two games, $$ a\oplus b=\operatorname{mex}\left(\{a'\oplus b\mid a'<a\}\cup \{a\oplus b'\mid b'<b\}\right). $$ turns out to be $a\oplus b=a \mathop{XOR} b$. $\endgroup$ Commented Nov 30 at 18:07
  • 2
    $\begingroup$ Why these downvotes ? $\endgroup$ Commented Nov 30 at 19:15
  • $\begingroup$ @JeanMarie All two of those downvotes. Beats me. +1. $\endgroup$ Commented Dec 1 at 0:07

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.