View source for Talk:Nim

{{WikiProject banner shell|class=C|1=
{{WikiProject Mathematics|importance = mid }}
{{WikiProject Games |importance=Low}}
{{WikiProject Computer science|importance=}}
}}

==Old posts==
Nim is now used as a simple illustration of the Sprague-Grundy theorem. 

A version of this game is played in Alain Resnais' movie L'année dernière à Marienbad. 

A typical normal game starts with heaps of 3, 4 and 5: 

 A B C           (Heaps A, B, and C)
 3 4 5           I take 2 from A
 1 4 5           You take 3 from C
 1 4 2           I take 1 from B
 1 3 2           You take 1 from B
 1 2 2           I take entire C heap
 2 2 0           You take 1 from A
 1 2 0           I take 1 from B (In the misere game I would take the entire 2 heap)
 1 1 0           You take 1 from B
 1 0 0           I take the last 1 and win.


Error in heap A. why is there a 2? Should be 1.

quote:
"
Now here, C was the one we artificially subtracted from, so we have to pick another one. You can think of it as that we pretend you took one from another stack, say A.

 1 2 0   011   I take one from B
 1 1 0   000   You take one from B
 1 0 0   001   I take one from A, and I win.

But you see, since A was our artificial stack, it still looks like 1,0,0, and they have to make the last move
"

But, if in the 1 1 0 situation, which is actually a 2 1 0 situation, You can take the two from A, and leaving a -1 1 0 situation, which is a 0 1 0, and I loose.

== Cleanup ==

I have rewritten the mathematical part of the article, and deleted most of the material on strategy, because it was (IMO, anyway) disorganized, confusing, didn't contain any information (all the painfully constructed "winning patterns" there are simply special cases of the general Bouton's characterization), and sometimes  incorrect (why the hell was [[User:Ling Kah Jai|Ling Kah Jai]] credited for a well-known 100 years old result?). Nevertheless, in case somebody decides to reintroduced bits of the text, here it is. -- [[User:EJ|EJ]] 9 July 2005 17:12 (UTC)

----

I've put the text from the old version of the article that was once here on the subpage [[/Deleted text]].  [[User:4pq1injbok|4pq1injbok]] 19:33, 30 July 2005 (UTC)

I've rewritten much of the explanatory material to be more explanatory and correct, especially the relation to combinatorial game theory.  The mathematical part got minor edits, mostly to make the stuff consistent.--[[User:Dan Hoey|Dan Hoey]] 19:33, 26 October 2005 (UTC)

Dan, while most of your edits here are certainly valuable, [[please]] [[don't]] [[attempt]] [[to]] [[link]] [[every]] [[word]] [[in]] [[the]] [[article]]. It clutters the text, distracts the readers, and serves no useful purpose. As a [[Wikipedia:Manual of Style (links)|general rule]], it usually suffices to link to a particular page only once. Thanks. -- [[User:EJ|EJ]] 03:49, 18 December 2005 (UTC)

==Last move game==

Does the name ''last move game'' for normal Nim actually have any currency?  [[User:4pq1injbok|4pq1injbok]] 06:30, 24 July 2005 (UTC)

I don't know if ''last move game'' or ''last stone game'' is really used, so I deleted it.  Anyone who wants it back should say something more specific than asserting that it is used in some regions.--[[User:Dan Hoey|Dan Hoey]] 19:28, 26 October 2005 (UTC)
==Linking blindly to a binary==
It is extremely unsafe to link toa binary from an untrusted source the way you are doing it.  The program isn't that great, so I don't see why we are linking to it in the first place.

== Yet another variation... ==

For those who have the latest version of [[Enigma (computer game)|Enigma]], take a look in Enigma level pack 2, level 16 (Enignimm). The thing is, you'll have to play and win two games to access the Oxyd stones locked away but there is only '''one heap'''! The first heap has 13 blocks and the second has 16. I don't think I can calculate the Nim-sum because it now has four binary digits. The only way I ever won this game is nearly by chance. In the first heap, the computer starts first, but in the second, you get to start first. <s>What's the process of calculation?</s>

[Later after examining code of level...]

I just found the solution. Basically, you have to use the correct subtractand so that you can get 13, 9 and 5 blocks remaining(These numbers are what makes the computer take away (random number between 1 to 3) blocks). By using the correct subtractand to get the numbers I explained, you can win both games and unlock the door to the Oxyd stones and complete the level. Again I ask, what's the process of "calculating" this?  --[[User:Bruin_rrss23|Bruin_rrss23]] [[User talk:Bruin_rrss23|(talk)]] 11:29, 18 January 2007 (UTC)

== Appearance in popular culture ==

Uh, I'm not sure what the "standard" title for a section about cultural references to stuff is, so I'm not going to add it to the article, but I thought it might be of interest that this game appears in the GBA version (and possibly the PSX version, though probably not the Super Nintendo version) of Tales of Phantasia.  It is the "subtraction game" variant.  If you need a reference, you could probably use one of the entries at Gamefaqs.

== which player will win  ==

"there is an easily-calculated way to determine which player will win " -- assuming this player doesn't screw up. [[User:Jnestorius|jnestorius]]<sup>([[User talk:Jnestorius|talk]])</sup> 22:05, 10 April 2007 (UTC)


== Rules ==

Talking about this version: [http://en.wikipedia.org/enwiki/w/index.php?title=Nim&oldid=155929823]. Someone should insert a "rules" section before the "illustration" section.

Also, this sentence in the illustration section makes no sense: "In order to win always leave an even number of 1's, 2's, and 4's." It doesn't make sense as a win condition, because the player who did that didn't win. It also doesn't work as a winning strategy, because the player who did it lost. --[[User:68.161.152.145|68.161.152.145]] 04:36, 20 September 2007 (UTC)

== New external link: nim developed in AJAX ==

After i read http://en.wikipedia.org/wiki/Wikipedia:External_links i don't know if i can add
the following external link [[http://www.isidoroghezzi.net/very_simple_game.html very_simple_game]]
where, using AJAX techniques, I developed a program to free play at "nim"
in the variant "who is getting the last element loses". There are 8 schemas, at growing difficult level.
The solver server-side algorithm, was developed in PHP and it is of kind recursive reduction with sorted cached.
Sorry for my bad english, my natural language is Italian.
Thanks, MacApp.--[[User:MacApp|MacApp]] ([[User talk:MacApp|talk]]) 12:09, 17 March 2008 (UTC)

== Computer version ==

In 1979-80, I acquired a number of games playable on the TRS-80 Model I microcomputer.  One was "Android Nim".  In this version, 18 androids are displayed on the screen, eight in the top row, six in the middle, four in the bottom.  The left-most android of each row has a "ray gun", and on instruction of the player (computer user versus the computer), one of the armed androids inspects its line to see if there are enough androids to take out as per the quantity indicated by the player. After confirming this, the android nods at the screen and raises its ray gun. The androids all turn their heads to look at the android with the ray gun raised. The ray gun fires, "dissolving" the number of androids required. The next player then selects which row and how many.

If the computer user wins, the computer sometimes tries in vain to ask an android to destroy androids it does not have, and the armed android shakes its head. When the user's winning move is completed, the computer selects a half-dozen adjectives from a program list that generally describes the incredulity of the computer that the user has won.

The computer then asks if another game is desired.

I can only play it if I fire up my old Model IV computer (vintage 1984) in Model III mode, but I'm not certain if I still have readable floppy discs to do it. A version of this game true to this version, but usable on modern IBM compatibles with Windows, would be welcome! [[User:Gcapp1959|GBC]] ([[User talk:Gcapp1959|talk]]) 06:26, 3 August 2008 (UTC)

== "nimm!"? ==

: ''The name is probably derived from [[German language|German]] ''nimm!'' meaning "take!"''
Why the exclamation marks?  Does the word "nimm" mean something different without it? -- [[User:Smjg|Smjg]] ([[User talk:Smjg|talk]]) 08:43, 15 October 2009 (UTC)
The exclamation mark is to underline that it is an imperative. ''Take!'' is different from ''Take'' (at least in English)  <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/194.39.218.10|194.39.218.10]] ([[User talk:194.39.218.10|talk]]) 13:26, 21 February 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

==I added the 100 game ==
Hello, I added this "100 game" which I once saw in a TV show and which kept me mumbling for a whole day...[[Special:Contributions/194.39.218.10|194.39.218.10]] ([[User talk:194.39.218.10|talk]]) 14:00, 21 February 2012 (UTC)

== PAwn Duel/Northcott's Nim ==

There was an article called "Pawn duel".  There was no reference to that name being used, except a website that plays the game.  I renamed it [[Northcott's Nim]], but that isn't quite accurate either (no first move restriction).  What do you think about that article being merged into this one?  [[User:Bubba73|Bubba73]] <sup>[[User talk:Bubba73|You talkin' to me?]]</sup> 15:58, 21 August 2012 (UTC)

: On second thought, I think I'll prod that article because of a lack of references and notability.  [[User:Bubba73|Bubba73]] <sup>[[User talk:Bubba73|You talkin' to me?]]</sup> 20:41, 21 August 2012 (UTC)

== Is it just me? ==
Sorry, but the Strategy does not make sense (at least to me). If there are only 1 in each of 3 heaps then the strategy elucidated here would lead one to remove one item (which is also the only legal move) and would leave a Nim sum of 0. This of course results in the current player loosing, when the other player removes one, despite the fact that this strategy is supposed to guarantee a win. So either I have misunderstood something, or the strategy needs further explanation.  <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/76.167.251.4|76.167.251.4]] ([[User talk:76.167.251.4|talk]]) 01:32, 4 January 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
<br />
If you are playing "normal" game (the last player who takes wins) then you're guaranteed to win because you take the last item.
If you are playing "misère" game (the last player who takes loses) then you obviously have to invert your strategy. But starting from your example, you can only lose.--[[Special:Contributions/194.39.218.10|194.39.218.10]] ([[User talk:194.39.218.10|talk]]) 15:47, 17 July 2013 (UTC)

You have misunderstood something: The consequences of the sentence "When played as a misère game, Nim strategy is different only when the normal play move would leave only heaps of size one. In that case, the correct move is to leave an odd number of heaps of size one (in normal play, the correct move would be to leave an even number of such heaps)." 

This guarantees that you never face "only 1 in each of 3 heaps", or in any odd number of heaps.  Instead, you force your opponent to face that situation.  At the start of the game, at least one heap has 2 or more objects.  Eventually, all of the heaps will get down to 0 or 1.  The first player who doesn't leave any heaps of 2 or more (in other words, who leaves only heaps of 0 or 1) has to be careful to leave an odd number of heaps in a misère game (but an even number in normal play), and will win the game.

The strategy is the same in normal or misère play until you get to the point where one, and only one, heap has 2 or more objects.  After that, the strategy to win is trivial (in either version):

1. In normal play, if there are an odd number of heaps, take the entire heap that has 2 or more objects, which will leave an even number of heaps, which have exactly 1 object each.<br />
2. In normal play, if there are an even number of heaps, take all but one object from the heap that has 2 or more objects (leaving one object in that heap), which will leave an even number of heaps, which have exactly 1 object each.<br />
3. In a misère game, if there are an even number of heaps, take the entire heap that has 2 or more objects, which will leave an odd number of heaps, which have exactly 1 object each.<br />
4. In misère play, if there are an odd number of heaps, take all but one object from the heap that has 2 or more objects (leaving one object in that heap), which will leave an odd number of heaps, which have exactly 1 object each.<br />

Since none of the remaining heaps have more than one object, the players must simply alternate removing exactly one heap (of one object) until the game ends.

The first player who fails to leave at least two heaps with at least two objects each loses (in either version of the game, (normal play or misère game) if the other player employs this end game strategy.[[Special:Contributions/47.139.44.196|47.139.44.196]] ([[User talk:47.139.44.196|talk]]) 16:03, 22 February 2020 (UTC)
=== Not just you ===
It appears the strategy is incomplete. 1 xor 1 xor 1 is indeed 1, but it is also a winning strategy. 1 xor 1 is indeed 0, but it is a losing strategy. So it seems when every heap is size 1 then you need the nim sum to be 1 instead of zero.
[[Special:Contributions/72.234.110.47|72.234.110.47]] ([[User talk:72.234.110.47|talk]]) 10:32, 30 August 2015 (UTC)
Some examples:

3,3 is a winning combination with nimsum=0

2,2 is a winning combination with nimsum=0

1,1 is a losing combination with nimsum=0

1,1,1 is a winning combination with nimsum=1
[[Special:Contributions/72.234.110.47|72.234.110.47]] ([[User talk:72.234.110.47|talk]]) 03:54, 31 August 2015 (UTC)

:This is for the normal game, not the Misère game.  <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/115.82.178.88|115.82.178.88]] ([[User talk:115.82.178.88#top|talk]]) 11:36, 16 June 2018 (UTC)</small> <!--Autosigned by SineBot-->

It is complete.  Read closely the sentence "When played as a misère game, Nim strategy is different only when the normal play move would leave only heaps of size one. In that case, the correct move is to leave an odd number of heaps of size one (in normal play, the correct move would be to leave an even number of such heaps)."

In other words, "when every heap is size 1", or will be 1 after your move, then you ignore the nimsums and follow the trivial strategy of leaving an odd number of heaps of 1 in a misère game (or an even number of heaps of one in normal play).[[Special:Contributions/47.139.44.196|47.139.44.196]] ([[User talk:47.139.44.196|talk]]) 16:03, 22 February 2020 (UTC)

== Nim sum ==

Not being dim: can 'nim sum' be better sum-med up(given that the text says 'any number' of items can be removed)? [[Special:Contributions/193.132.104.10|193.132.104.10]] ([[User talk:193.132.104.10|talk]]) 15:28, 11 February 2016 (UTC)

== Confused ==

''finish'' or ''start'' every move with nim-sum 0 to win?

"In normal play, the winning strategy is to finish every move with a nim-sum of 0" - (so it's ''finish'')
"In a normal Nim game, the player making the first move has a winning strategy if and only if the nim-sum of the sizes of the heaps is zero" - (so it's ''start'')
"Lemma 1. If s = 0, the first player loses the normal play game by definition" - (so it's ''finish'')

who is ''you'' and who is ''I''?

"I take 2 from A, leaving a sum of 000, so I will win." - ''I'' is the computer
"return "You will lose :("" - ''You'' is the computer

== Requested move 11 January 2022 ==
<div class="boilerplate" style="background-color: #efe; margin: 2em 0 0 0; padding: 0 10px 0 10px; border: 1px dotted #aaa;"><!-- Template:RM top (modified) -->
:''The following is a closed discussion of a [[WP:requested moves|requested move]]. <span style="color:red">'''Please do not modify it.'''</span> Subsequent comments should be made in a new section on the talk page. Editors desiring to contest the closing decision should consider a [[Wikipedia:move review|move review]] after discussing it on the closer's talk page. No further edits should be made to this section. ''
----
<span id="reqmovetag"></span>{{check talk wp}}
{{Tmbox
|small = 
|imageright = 
|type = move
|text = '''It was proposed in this section that [[:Nim]] be [[Wikipedia:Moving a page|renamed and moved]]&#32;to {{no redirect| Nim (game) }}.''' 
----
<small>'''{{smallcaps|result:}}'''</small><br />'''No consensus.''' After a lengthy listing ''and'' a relist, there is no consensus to move. <small>([[Wikipedia:Requested moves/Closing instructions#Closure by a page mover|closed by non-admin page mover]])</small> -[[User:2pou|2pou]] ([[User talk:2pou|talk]]) 21:55, 2 February 2022 (UTC)
----
<div class="floatleft">''Links:'' [{{fullurl:Special:Log/move|page={{Urlencode:Nim}}}} current log] • [{{fullurl:Special:Log/move|page={{Urlencode: Nim (game) }}}} target log]</div>
<div class="floatright">{{resize|65%|''This is template {{tls|Requested move/end}}''}}</div>
<!-- This is template "subst:Requested move/end". -->
}}
[[:Nim]] → {{no redirect|Nim (game)}} – No clear primary topic for this 3 word term, the game has 7,838 views but the programming language has 4,084 and [[Nim Chimpsky]] who appears to commonly just be "Nim" gets 8,215[[https://pageviews.toolforge.org/massviews/?platform=all-access&agent=user&source=wikilinks&range=latest-20&sort=views&direction=1&view=list&target=https://en.wikipedia.org/wiki/NIM]]. Google mainly appears to return the game but the programming language is the 1st result, Images appears to be split between the game and chimp and Books is split between the game and various uses. It seems likely that the game is the most common usage in terms of PT#1 if the chimp is known more often by his full name, by PT#2 the game may be the most significant usage but <s>as a 3 word acronym</s> its not clear <s>it</s> <ins>the game</ins> would be primary <ins>for the 3 word acronym</ins> when some of them may also have more long-term significance. Redirect to [[NIM]] or move that to [[Nim]]. '''[[User:Crouch, Swale|<span style="color:Green">Crouch, Swale</span>]]''' ([[User talk:Crouch, Swale|<span style="color:Blue">talk</span>]])  18:32, 11 January 2022 (UTC)<small>—&nbsp;'''''Relisting.'''''&nbsp;<small style="color:#999;text-shadow:#D3D3D3 0.3em 0.3em 0.15em">— [[User:Coffee|<span style="font-size: larger; color:#ffa439">Coffee</span>]] // [[user talk:Coffee|<span style="color:#090">have a</span> ☕️]] // [[Special:Contribs/Coffee|<span style="color:#4682b4">beans</span>]] // </small> 02:55, 24 January 2022 (UTC)</small>
: This nomination seems confused.  The game has massive long-term significance: it is a fundamental example in the field of [[combinatorial game theory]] and has been studied for more than a century.  Where do you get the idea that the word "Nim" is a three-word acronym?  The article says "Its current name was coined by Charles L. Bouton of Harvard University, who also developed the complete theory of the game in 1901, but the origins of the name were never fully explained." --[[User:JayBeeEll|JBL]] ([[User_talk:JayBeeEll|talk]]) 13:11, 12 January 2022 (UTC)
::Because the [[NIM]] DAB lists things in the "Technology and engineering" and "Other uses" sections that are three word acronyms. '''[[User:Crouch, Swale|<span style="color:Green">Crouch, Swale</span>]]''' ([[User talk:Crouch, Swale|<span style="color:Blue">talk</span>]])  14:00, 12 January 2022 (UTC)
::: You wrote {{tq|the game may be the most significant usage but as a 3 word acronym its not clear it would be primary}}.  I parse this as an assertion that the name of the game Nim is a 3-word acronym (which is not true), and this is consistent with other comments in the proposal.  May I request you edit / clarify the rationale for the proposal? --[[User:JayBeeEll|JBL]] ([[User_talk:JayBeeEll|talk]]) 17:11, 12 January 2022 (UTC)
::::{{Ping|JayBeeEll}} done, I agree my wording was poor/confusing. '''[[User:Crouch, Swale|<span style="color:Green">Crouch, Swale</span>]]''' ([[User talk:Crouch, Swale|<span style="color:Blue">talk</span>]])  17:17, 12 January 2022 (UTC)
*'''Support''' WPNP [[Nim (disambiguation)]] move in. [[User:In ictu oculi|In ictu oculi]] ([[User talk:In ictu oculi|talk]]) 18:27, 14 January 2022 (UTC)
* '''Comment''' the game of Nim is the primary topic by long-term significance, but it's not for pageviews.  Also there are only 3 entries that are "Nim" rather than "NIM", and a hatnote + DAB for [[NIM]] can handle that (though it's a bit awkward).  This can really go either way. [[User:力]] (powera, [[User talk:力|<span style="color:#FA0;font-family:courier">π</span>]], [[Special:Contributions/力|<span style="font-family:courier">ν</span>]]) 18:41, 15 January 2022 (UTC)
*: Also the article has a ton of unsourced [[WP:NOTHOWTO]] content. [[User:力]] (powera, [[User talk:力|<span style="color:#FA0;font-family:courier">π</span>]], [[Special:Contributions/力|<span style="font-family:courier">ν</span>]]) 18:41, 15 January 2022 (UTC)
*'''Oppose'''. Primary topic by long-term significance, and I don't think it would be particularly beneficial to have a disambiguation page instead of this. I've added a hatnote for [[Nim Chimpsky]] so that's now easily covered too. &nbsp;&mdash;&nbsp;[[User:Amakuru|Amakuru]] ([[User talk:Amakuru|talk]]) 11:27, 20 January 2022 (UTC)
*'''Support move.''' No primary topic, at least for pageviews. '''[[User:Old Naval Rooftops|<span style="color:#002244">O.N.R.</span>]]'''&nbsp;<sup>[[User talk:Old Naval Rooftops|<span style="color:#002244">(talk)</span>]]</sup> 04:25, 24 January 2022 (UTC)
*'''Oppose'''.  I highly doubt anyone interested in Nim Chimsky searches it up by "Nim" - it's more likely they'd try "Noam Chomsky (monkey)" or the like instead.  The acronym use is covered by NIM being the disambiguation page, so I also doubt that "nim" is likely looking for acronyms.  Finally, the programming language...  I'm normally a big fan of using pageviews, but in this particular case, I distrust the pageview count.  Nim is a ''very'' obscure language, and the pageview count is likely being inflated by something IMO - somebody's programming test pinging the article every so often or the like.  I'm not sure what it is, but really all that you need to see is the article's line of "Nim has an active community on the self-hosted, self-developed official forum" which is cited to, uh, the Nim forums webpage itself.  I think that really says it all about how prominent this programming language really is.  [[User:SnowFire|SnowFire]] ([[User talk:SnowFire|talk]]) 06:25, 24 January 2022 (UTC)
*'''Oppose''' Per [[WP:PTM]]. The name is not an exact title match to the game so it doesn't need disambiguation.<sub><small>[[User:Zxcvbnm|ZXCVBNM]] ([[User Talk:Zxcvbnm|TALK]])</small></sub> 20:57, 24 January 2022 (UTC)
*'''Oppose''' per ptm [[User:Red Slash|<span style="color:#FF4131;">Red</span>]] [[User talk:Red Slash|<b><span style="color:#460121;">Slash</span></b>]] 23:44, 27 January 2022 (UTC)
<div style="padding-left: 1.6em; font-style: italic; border-top: 1px solid #a2a9b1; margin: 0.5em 0; padding-top: 0.5em">The discussion above is closed. <b style="color: #FF0000;">Please do not modify it.</b> Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.</div><!-- from [[Template:Archive bottom]] -->
</div><div style="clear:both;"></div>

== Reference to Survivor: Thailand is obscure ==

It really seems out of place. Does it contribute anything to the discussion by saying that certain constants 3 and 1 were used in a particular episode of a particular reality show at one particular point in time? That just reads weird. Ok to remove? [[User:Corwin.amber|Corwin.amber]] ([[User talk:Corwin.amber|talk]]) 11:59, 17 August 2022 (UTC)

:{{ping|Corwin.amber}} Yes, ok. --[[User:JayBeeEll|JBL]] ([[User_talk:JayBeeEll|talk]]) 18:32, 17 August 2022 (UTC)

== Single pile nim games and Sprague-Grundy ==

The following paragraph:

"Normal-play nim (or more precisely the system of nimbers) is fundamental to the Sprague–Grundy theorem, which essentially says that in normal play every impartial game is equivalent to a nim heap that yields the same outcome when played in parallel with other normal play impartial games (see disjunctive sum)."

Has been replaced with this paragraph:

"Nim is fundamental to the Sprague–Grundy theorem, which essentially says that every impartial game is equivalent to a nim game with a single pile."

I don't know enough about the subject to tell whether these statements are equivalent, but it seems to me that "a nim game with a single pile" would be trivial for a player to win in a single turn: either take all the matches under "normal game" rules or take all but the last match under ''misère'' rules. Clarification would be appreciated. [[Special:Contributions/38.27.102.50|38.27.102.50]] ([[User talk:38.27.102.50|talk]]) 01:35, 22 April 2024 (UTC)