นิมเป็นเกมคณิตศาสตร์ เชิงการจัดเรียง ที่ผู้เล่นสองคนผลัดกันหยิบ (หรือ "นิมมิง") วัตถุออกจากกองหรือกลุ่มที่แตกต่างกัน ในแต่ละตา ผู้เล่นจะต้องหยิบวัตถุอย่างน้อยหนึ่งชิ้น และสามารถหยิบได้กี่ชิ้นก็ได้ ตราบใดที่วัตถุเหล่านั้นมาจากกองหรือกลุ่มเดียวกัน เป้าหมายของเกมอาจแตกต่างกันไป ขึ้นอยู่กับเวอร์ชันที่เล่น อาจเป็นการหลีกเลี่ยงการหยิบวัตถุชิ้นสุดท้าย หรือการหยิบวัตถุชิ้นสุดท้าย

เกมนิมเป็นพื้นฐานสำคัญของทฤษฎีบทสปราก-กรุนดีซึ่งโดยพื้นฐานแล้วกล่าวว่าเกมที่เป็นกลาง ทุกเกม เทียบเท่ากับเกมนิมที่มีกองหมากเพียงกองเดียว (เมื่อพิจารณาว่าเป็นเกมย่อยของเกมที่เป็นกลางขนาดใหญ่กว่า)

เกมนิมมีการเล่นกันมาตั้งแต่สมัยโบราณ^{[ 1 ]}กล่าวกันว่าเกมนี้มีต้นกำเนิดในประเทศจีน —มันคล้ายคลึงกับเกมเจียนซือจื่อ (捡石子) หรือ "การหยิบหิน" ของจีน ^{[ 2 ]} —แต่ต้นกำเนิดนั้นไม่แน่นอน การอ้างอิงถึงนิมในยุโรปที่เก่าแก่ที่สุดมาจากต้นศตวรรษที่ 16 ชื่อปัจจุบันของเกมนี้ตั้งโดยCharles L. Boutonจากมหาวิทยาลัยฮาร์วาร์ดซึ่งเป็นผู้พัฒนาทฤษฎีที่สมบูรณ์ของเกมนี้ในปี 1901 ^{[ 3 ]}แต่ที่มาของชื่อนี้ไม่เคยได้รับการอธิบายอย่างครบถ้วนพจนานุกรมภาษาอังกฤษของอ็อกซ์ฟอร์ดระบุว่าชื่อนี้มาจากคำกริยาภาษาเยอรมันnimmซึ่งหมายถึง "หยิบ"

ในงานมหกรรมโลกที่นิวยอร์กปี 1939เวสติงเฮาส์ได้จัดแสดงเครื่องเล่น เกมนิม ชื่อนิมัทรอ น ^{[ 4 ]}ตั้งแต่วัน ที่ 11 พฤษภาคมถึง 27 ตุลาคม 1940 มีเพียงไม่กี่คนที่สามารถเอาชนะเครื่องนี้ได้ในช่วงเวลาหกเดือนนั้น หากพวกเขาทำได้ พวกเขาจะได้รับเหรียญที่มีข้อความว่า "แชมป์นิม" ^{[ 5 ]}นอกจากนี้ยังเป็นหนึ่งในเกมคอมพิวเตอร์อิเล็กทรอนิกส์เกมแรกๆ อีกด้วยเฟอร์รันติได้สร้างคอมพิวเตอร์สำหรับเล่นเกมนิมซึ่งจัดแสดงในงาน Festival of Britainในปี 1951 ในปี 1952 เฮอร์เบิร์ต คอปเปล ยูจีน แกรนต์ และฮาวเวิร์ด บอลเลอร์ วิศวกรจากบริษัท WL Maxson ได้พัฒนาเครื่องที่มีน้ำหนัก23 กิโลกรัม (50 ปอนด์)ซึ่งเล่นเกมนิมกับคู่ต่อสู้ที่เป็นมนุษย์และชนะเป็นประจำ^{[ 6 ]}มีการอธิบายถึงเครื่องเล่นเกมนิมที่ทำจากทิงเกอร์ทอย^{[ 7 ]} 

เกมนิมเป็นหัวข้อของคอลัมน์ "เกมคณิตศาสตร์"ของมาร์ติน การ์ดเนอร์ในScientific American ฉบับเดือนกุมภาพันธ์ พ.ศ. 2491 มีการเล่นเกมนิมเวอร์ชันหนึ่ง—และมีความสำคัญเชิงสัญลักษณ์—ในภาพยนตร์ฝรั่งเศสยุคใหม่เรื่อง Last Year at Marienbad (1961) ^{[ 8 ]}

เกมนิมมักเล่นในรูปแบบเกมมิแซร์ (misère game ) ซึ่งผู้เล่นที่หยิบวัตถุชิ้นสุดท้ายจะเป็นผู้แพ้ แต่ก็สามารถเล่นในรูปแบบ "การเล่นปกติ" ได้เช่นกัน โดยผู้เล่นที่หยิบวัตถุชิ้นสุดท้ายจะเป็นผู้ชนะ ไม่ว่าจะเป็นการเล่นปกติหรือเกมมิแซร์ เมื่อมีกองวัตถุเหลืออยู่เพียงกองเดียวที่มีวัตถุอย่างน้อยสองชิ้น ผู้เล่นที่หยิบวัตถุชิ้นต่อไปสามารถชนะได้อย่างง่ายดาย หากการหยิบนั้นทำให้กองที่มีวัตถุสองชิ้นขึ้นไปถูกเอาออกไปทั้งหมดหรือเหลือไว้เพียงชิ้นเดียว จะทำให้ไม่มีกองใดที่มีวัตถุมากกว่าหนึ่งชิ้น ดังนั้นผู้เล่นจึงต้องผลัดกันหยิบวัตถุออกไปทีละชิ้นจนกว่าเกมจะจบ หากผู้เล่นเหลือจำนวนกองที่ไม่เป็นศูนย์เป็นเลขคู่ (เช่นเดียวกับการเล่นปกติ) ผู้เล่นคนนั้นจะเป็นคนหยิบวัตถุชิ้นสุดท้าย แต่ถ้าผู้เล่นเหลือจำนวนกองเป็นเลขคี่ (เช่นเดียวกับการเล่นมิแซร์) ผู้เล่นอีกคนจะเป็นคนหยิบวัตถุชิ้นสุดท้าย

เกมปกติจะเล่นระหว่างผู้เล่นสองคน โดยใช้กองสิ่งของสามกองที่มีจำนวนเท่าใดก็ได้ ผู้เล่นทั้งสองจะผลัดกันหยิบสิ่งของจากกองใดกองหนึ่ง โดยมีเป้าหมายคือการเป็นผู้ที่หยิบสิ่งของเป็นคนสุดท้าย ในเกมมิแซร์ เป้าหมายคือการทำให้ฝ่ายตรงข้ามถูกบังคับให้หยิบสิ่งของชิ้นสุดท้ายที่เหลืออยู่

ตัวอย่างต่อไปนี้เป็นเกมปกติที่เล่นระหว่างผู้เล่นสมมติบ็อบ และอลิซซึ่งเริ่มต้นด้วยกองสิ่งของสาม สี่ และห้าชิ้นตามลำดับ

กลยุทธ์ที่ใช้ได้ผลในการชนะเกมนิมคือ การที่ผู้เล่นคนหนึ่งทำให้ฝ่ายตรงข้ามตกอยู่ในตำแหน่งใดตำแหน่งหนึ่งต่อไปนี้ และในตาเดินต่อๆ ไป ผู้เล่นควรจะสามารถทำให้ฝ่ายตรงข้ามตกอยู่ในตำแหน่งที่เล็กลงได้ ความแตกต่างระหว่างการเล่นแบบมิแซร์และการเล่นแบบปกติมีเพียงแค่ตาเดินสุดท้ายเท่านั้น

โดยทั่วไปแล้วnและmสามารถมีค่าใดๆ ที่มากกว่า 0 ได้ และอาจเป็นค่าเดียวกันก็ได้

ระบบนิมแบบเล่นปกติ (หรือกล่าวให้แม่นยำยิ่งขึ้นคือ ระบบของนิมเบอร์ ) เป็นพื้นฐานสำคัญของทฤษฎีบทสปราก-กรุนดีซึ่งโดยพื้นฐานแล้วกล่าวว่า ในการเล่นปกติเกมที่เป็นกลาง ทุกเกม จะเทียบเท่ากับกองนิมที่ให้ผลลัพธ์เดียวกันเมื่อเล่นควบคู่ไปกับเกมที่เป็นกลางแบบเล่นปกติอื่นๆ (ดูผลรวมแบบแยกส่วน )

ในขณะที่เกมปกติที่ไม่ลำเอียงทุกเกมสามารถกำหนดค่า nim ได้ แต่ภายใต้ข้อตกลง misère นั้นไม่เป็นเช่นนั้น มีเพียงเกมที่อ่อนกว่า เท่านั้น ที่สามารถเล่นได้โดยใช้กลยุทธ์เดียวกับ misère nim

นิมเป็นกรณีพิเศษของเกมโพเซตโดยที่โพเซตประกอบด้วยสายโซ่ ที่ไม่ทับซ้อนกัน (กองข้อมูล)

กราฟวิวัฒนาการของเกมนิมที่มีสามกองนั้นเหมือนกับกราฟวิวัฒนาการสามสาขาของออโตมาตาอูลัม-วอร์เบอร์ตัน^{[ 9 ]}

เกม Nim ได้รับการแก้ไข ทางคณิตศาสตร์ แล้วสำหรับจำนวนกองและวัตถุเริ่มต้นใด ๆ และมีวิธีการคำนวณที่ง่ายเพื่อระบุว่าผู้เล่นคนใดจะชนะและมีท่าเดินใดบ้างที่ผู้เล่นคนนั้นสามารถเลือกใช้ได้เพื่อชัยชนะ

หัวใจสำคัญของทฤษฎีเกมนี้คือผลรวมดิจิทัลไบนารี ของขนาดฮีป กล่าวคือ ผลรวม (ในไบนารี) โดยไม่คำนึงถึงตัวทดจากหลักหนึ่งไปยังอีกหลักหนึ่ง การดำเนินการนี้ยังเป็นที่รู้จักกันในชื่อ " xor บิต " หรือ "การบวกเวกเตอร์เหนือGF (2) " (การบวกบิตโมดูล 2) ในทฤษฎีเกมเชิงคอมบิ นาทอริก มักเรียกว่าผลรวมนิม (nim-sum)ดังที่จะเรียกในที่นี้ ผลรวมนิมของxและyเขียนด้วยx ⊕ yเพื่อแยกความแตกต่างจากผลรวมธรรมดาx + yตัวอย่างการคำนวณด้วยฮีปขนาด 3, 4 และ 5 มีดังนี้:

เลขฐานสอง เลขฐานสิบ  011  3  ฮีป A 100  4  กอง B 101  5  กอง C --- 010  2  ผลรวมนิมของกอง A, B และ C คือ 3 ⊕ 4 ⊕ 5 = 2

อีกวิธีที่เทียบเท่ากัน ซึ่งมักจะทำได้ง่ายกว่าเมื่อคิดในใจ คือ การแสดงขนาดของกองข้อมูลเป็นผลรวมของกำลัง ที่แตกต่างกัน ของ 2 ตัดคู่ที่มีกำลังเท่ากันออก แล้วจึงบวกส่วนที่เหลือเข้าด้วยกัน:

3 = 0 + 2 + 1 = 2 1 กอง A 4 = 4 + 0 + 0 = 4 กอง B 5 = 4 + 0 + 1 = 4 1 กอง C -------------------------------------------------------------------- 2 = 2 เหลือเท่าไหร่หลังจากตัดเลข 1 และ 4 ออกไป

ในการเล่นปกติ กลยุทธ์ที่ชนะคือการจบทุกตาเดินด้วยผลรวมนิม (nim-sum) เท่ากับ 0 ซึ่งเป็นไปได้เสมอหากผลรวมนิมไม่เป็นศูนย์ก่อนการเดิน หากผลรวมนิมเป็นศูนย์ ผู้เล่นคนถัดไปจะแพ้หากผู้เล่นคนแรกไม่ทำผิดพลาด เพื่อหาว่าควรเดินอย่างไร ให้ X เป็นผลรวมนิมของขนาดฮีปทั้งหมด หาฮีปที่ผลรวมนิมของ X และขนาดฮีปน้อยกว่าขนาดฮีป กลยุทธ์ที่ชนะคือการเล่นในฮีปดังกล่าว ลดขนาดฮีปนั้นให้เหลือผลรวมนิมของขนาดเดิมด้วย X ในตัวอย่างข้างต้น ผลรวมนิมของขนาดคือX = 3 ⊕ 4 ⊕ 5 = 2ผลรวมนิมของขนาดฮีป A=3, B=4 และ C=5 เมื่อ X=2 คือ

A ⊕ X = 3 ⊕ 2 = 1 [เนื่องจาก (011) ⊕ (010) = 001 ]

B ⊕ X = 4 ⊕ 2 = 6

C ⊕ X = 5 ⊕ 2 = 7

กองเดียวที่ลดขนาดลงคือกอง A ดังนั้นการเดินหมากที่ชนะคือการลดขนาดของกอง A ให้เหลือ 1 (โดยการนำวัตถุออกสองชิ้น)

ในกรณีง่ายๆ อย่างเช่น ถ้าเหลือกองวัตถุเพียงสองกอง กลยุทธ์คือการลดจำนวนวัตถุในกองที่ใหญ่กว่าเพื่อให้ทั้งสองกองมีจำนวนเท่ากัน หลังจากนั้น ไม่ว่าคู่ต่อสู้จะขยับอย่างไร ผู้เล่นก็สามารถทำเช่นเดียวกันกับอีกกองหนึ่งได้ เพื่อรับประกันว่าจะได้วัตถุชิ้นสุดท้าย

เมื่อเล่นในรูปแบบเกมมิแซร์ กลยุทธ์นิมจะแตกต่างออกไปก็ต่อเมื่อการเดินหมากตามปกติจะเหลือเพียงกองขนาดหนึ่งเท่านั้น ในกรณีนั้น การเดินหมากที่ถูกต้องคือการเหลือกองขนาดหนึ่งเป็นจำนวนคี่ (ในการเล่นปกติ การเดินหมากที่ถูกต้องคือการเหลือกองขนาดหนึ่งเป็นจำนวนคู่)

กลยุทธ์เหล่านี้สำหรับการเล่นแบบปกติและการเล่นแบบมิแซร์นั้นเหมือนกันจนกว่าจำนวนกองที่มีวัตถุอย่างน้อยสองชิ้นจะเท่ากับหนึ่งพอดี ณ จุดนั้น ผู้เล่นคนถัดไปจะนำวัตถุทั้งหมด (หรือทั้งหมด ยกเว้นหนึ่งชิ้น) ออกจากกองที่มีวัตถุสองชิ้นขึ้นไป เพื่อไม่ให้มีกองใดมีวัตถุมากกว่าหนึ่งชิ้น (กล่าวคือ กองที่เหลือทั้งหมดจะมีวัตถุเพียงชิ้นเดียว) ดังนั้นผู้เล่นจึงต้องผลัดกันนำวัตถุออกทีละชิ้นจนกว่าเกมจะจบ ในการเล่นแบบปกติ ผู้เล่นจะเหลือจำนวนกองที่ไม่เป็นศูนย์เป็นเลขคู่ ดังนั้นผู้เล่นคนเดิมจะได้เล่นเป็นคนสุดท้าย ในการเล่นแบบมิแซร์ ผู้เล่นจะเหลือจำนวนกองที่ไม่เป็นศูนย์เป็นเลขคี่ ดังนั้นผู้เล่นอีกคนจะได้เล่นเป็นคนสุดท้าย

ในเกมมิแซร์ที่มีกองขนาดสาม สี่ และห้า กลยุทธ์จะถูกนำมาใช้ดังนี้:

ความถูกต้องของกลยุทธ์ที่เหมาะสมที่สุดที่อธิบายไว้ข้างต้นได้รับการพิสูจน์โดย ซี. บูตัน

ทฤษฎีบทในเกมนิมปกติ ผู้เล่นที่เดินหมากก่อนจะมีกลยุทธ์ที่ชนะก็ต่อเมื่อผลรวมนิมของขนาดกองหมากไม่เป็นศูนย์ มิฉะนั้น ผู้เล่นคนที่สองจะเป็นฝ่ายชนะ

พิสูจน์:สังเกตว่าผลรวมนิม (⊕) เป็นไปตาม กฎ การสลับที่และการจัดกลุ่ม ตามปกติ ของการบวก (+) และยังเป็นไปตามคุณสมบัติเพิ่มเติมอีกประการหนึ่งคือx  ⊕ x = 0   

ให้x , ..., x เป็นขนาดของกองข้อมูลก่อนการเคลื่อนย้าย และy ,  ..., y เป็นขนาดที่สอดคล้องกันหลังการเคลื่อนย้าย ให้s = x ⊕ ... ⊕ x และt = y ⊕ ... ⊕ y ถ้าการเคลื่อนย้ายเกิดขึ้นในกองข้อมูลkเราจะได้x = y สำหรับทุกi ≠ kและx > y โดยอาศัยคุณสมบัติของ ⊕ ที่กล่าวถึงข้างต้น เราจะได้ว่า                 

$${\displaystyle {\begin{aligned}t&=0\oplus t\\&=s\oplus s\oplus t\\&=s\oplus (x_{1}\oplus \cdots \oplus x_{n})\oplus (y_{1}\oplus \cdots \oplus y_{n})\\&=s\oplus (x_{1}\oplus y_{1})\oplus \cdots \oplus (x_{n}\oplus y_{n})\\&=s\oplus 0\oplus \cdots \oplus 0\oplus (x_{k}\oplus y_{k})\oplus 0\oplus \cdots \oplus 0\\&=s\oplus x_{k}\oplus y_{k}\\[10pt](*)\quad t&=s\oplus x_{k}\oplus y_{k}\end{aligned}}}$$

กล่าวคือ เพื่ออัปเดตผลรวมนิมทั้งหมด${\displaystyle s}$หลังจากอัปเดตแล้ว${\displaystyle x_{k}}$กองนั้น เราต้องยกเลิกมันจาก${\displaystyle s}$โดยการรวมแบบนิมด้วย${\displaystyle x_{k}}$และจากนั้นผลรวมนิมใน${\displaystyle y_{k}}$.

ทฤษฎีบทนี้ได้มาจากการอุปมานตามความยาวของเกมจากบทพิสูจน์ย่อยสองข้อนี้

บทตั้งที่ 1.ถ้าs = 0 แล้วt ≠ 0 ไม่ว่าจะมีการเคลื่อนไหวใดก็ตาม

บทพิสูจน์:หากไม่มีการเคลื่อนไหวที่เป็นไปได้ บทพิสูจน์ย่อยนั้นจะเป็นจริงโดยปริยาย (และผู้เล่นคนแรกจะแพ้เกมเล่นปกติโดยนิยาม) มิฉะนั้น การเคลื่อนไหวใดๆ ในกองkจะสร้างt  = x ⊕ y จาก (*) ตัวเลขนี้ไม่ใช่ศูนย์ เนื่องจากx ≠ y      

บทตั้งที่ 2.ถ้าs ≠ 0 สามารถทำการเคลื่อนไหวเพื่อให้t = 0 ได้

บทพิสูจน์:ให้dเป็นตำแหน่งของบิตที่ไม่เป็นศูนย์ซ้ายสุด (สำคัญที่สุด) ในการแสดงเลขฐานสองของsและเลือกkโดยที่ บิตที่ dของx ก็ไม่เป็นศูนย์ด้วย ( k ดังกล่าว ต้องมีอยู่จริง เพราะมิฉะนั้น บิตที่ dของsจะเป็น 0) จากนั้นให้y   = s ⊕ x เราอ้างว่าy < x : บิตทั้งหมดทางซ้ายของdจะเหมือนกันในx และy บิตdลดลงจาก 1 เป็น 0 (ลดลง 2 ^d ) และการเปลี่ยนแปลงใดๆ ในบิตที่เหลือจะมีค่าอย่างมากที่สุด 2 ^d −1 ผู้เล่นคนแรกจึงสามารถทำการเคลื่อนไหวโดยการหยิบวัตถุx − y จากกอง kจากนั้น       

t = s ⊕ x  ⊕ y  (by (*)) = s ⊕ x  ⊕ ( s ⊕ x  ) = 0.

การปรับเปลี่ยนสำหรับการเล่นแบบมิแซร์แสดงให้เห็นได้จากการสังเกตว่าการปรับเปลี่ยนนี้เกิดขึ้นครั้งแรกในตำแหน่งที่มีกองขนาด 2 หรือมากกว่าเพียงกองเดียว โปรดสังเกตว่าในตำแหน่งดังกล่าวs ≠ 0 ดังนั้นสถานการณ์นี้จะต้องเกิดขึ้นเมื่อถึงตาของผู้เล่นที่ใช้กลยุทธ์การชนะ กลยุทธ์การเล่นปกติคือผู้เล่นจะลดขนาดกองนี้ให้เหลือ 0 หรือ 1 โดยเหลือจำนวนกองที่มีขนาด 1 เป็นจำนวนคู่ ส่วนกลยุทธ์มิแซร์คือการทำตรงกันข้าม จากจุดนั้นเป็นต้นไป การเคลื่อนไหวทั้งหมดจะถูกบังคับ

• WW Rouse Ball: Mathematical Recreations and Essays , The Macmillan Company, 1947.
• จอห์น ดี. บีสลีย์: คณิตศาสตร์ของเกม , สำนักพิมพ์มหาวิทยาลัยออกซ์ฟอร์ด, 1989
• Elwyn R. Berlekamp, ​​John H. Conway และ Richard K. Guy: Winning Ways for your Mathematical Plays , Academic Press, Inc., 1982.
• แมนเฟรด ไอเกนและรูธิลด์ วิงเคลอร์ : กฎแห่งเกม , สำนักพิมพ์มหาวิทยาลัยพรินซ์ตัน, 1981
• Walter R. Fuchs: คอมพิวเตอร์: ทฤษฎีสารสนเทศและไซเบอร์เนติกส์ , สำนักพิมพ์ Rupert Hart-Davis Educational Publications, 1971
• GH HardyและEM Wright : บทนำสู่ทฤษฎีจำนวน , สำนักพิมพ์มหาวิทยาลัยออกซ์ฟอร์ด, 1979
• เอ็ดเวิร์ด คาสเนอร์และเจมส์ นิวแมน : คณิตศาสตร์และจินตนาการ , สำนักพิมพ์ไซมอน แอนด์ ชูสเตอร์, 1940
• M. Kaitchik: Mathematical Recreations , WW Norton, 1942.
• Donald D. Spencer: การเล่นเกมด้วยคอมพิวเตอร์ , สำนักพิมพ์ Hayden Book Company, Inc., 1968.

• " คอมพิวเตอร์หนัก 50 ปอนด์เล่นเกม Nim " – เดอะนิวยอร์กเกอร์ - "ข่าวเด่นประจำเมือง" สิงหาคม 1952 (ต้องสมัครสมาชิกจึงจะอ่านได้)
• เกมยอดนิยมของนิม – ทฤษฎีนิมและความเชื่อมโยงกับเกมอื่นๆ ที่cut-the-knot
• นิม และ ซูเปอร์นิม 2 มิติที่cut-the-knot