เกมอ็อกทัล
เกมอ็อกทัลเป็นประเภทย่อยของเกมฮีปที่เกี่ยวข้องกับการนำโทเค็น (ชิ้นส่วนเกมหรือหิน) ออกจากกองโทเค็น เกมเหล่านี้ได้รับการศึกษาในทฤษฎีเกมเชิงผสมในฐานะที่เป็นการขยายความของเกมนิมเกมเคย์ลและเกมที่คล้ายกัน[ 1 ] [ 2 ]
เกมเลขฐานแปดเป็นเกมที่ยุติธรรมหมายความว่าทุกการเคลื่อนไหวที่ผู้เล่นคนหนึ่งสามารถทำได้ ผู้เล่นอีกคนหนึ่งก็สามารถทำได้เช่นกัน เกมแต่ละแบบจะแตกต่างกันที่จำนวนโทเค็นที่สามารถนำออกได้ในการเคลื่อนไหวครั้งเดียว และ (ขึ้นอยู่กับจำนวนนี้) ว่าอนุญาตให้นำโทเค็นออกทั้งกอง ลดขนาดของกอง หรือแบ่งกองออกเป็นสองกองได้หรือไม่ กฎที่แตกต่างกันเหล่านี้สามารถอธิบายได้อย่างกระชับด้วยระบบการเข้ารหัสโดยใช้เลขฐานแปด
ข้อกำหนดของเกม
เกมแปดเหลี่ยมเป็นเกมที่เล่นโดยใช้โทเค็นที่แบ่งออกเป็นกองๆ ผู้เล่นสองคนผลัดกันเดินจนกว่าจะไม่มีการเดินใดๆ อีกต่อไป การเดินแต่ละครั้งประกอบด้วยการเลือกกองใดกองหนึ่ง และเลือกอย่างใดอย่างหนึ่ง
- ลบโทเค็นทั้งหมดในฮีป ทำให้ไม่มีฮีปเหลืออยู่
- การลบโทเค็นบางส่วนแต่ไม่ใช่ทั้งหมด ทำให้เหลือกลุ่มโทเค็นที่เล็กลง หรือ
- โดยการนำโทเค็นบางส่วนออก และแบ่งโทเค็นที่เหลือออกเป็นสองกองที่ไม่ว่างเปล่า
กองอื่นๆ นอกเหนือจากกองที่เลือกไว้จะไม่มีการเปลี่ยนแปลง ผู้เล่นคนสุดท้ายที่เดินหมากจะเป็นผู้ชนะในการเล่นแบบปกติเกมนี้อาจเล่นในรูปแบบมิแซร์ ได้เช่นกัน ซึ่งผู้เล่นคนสุดท้ายที่เดินหมากจะเป็นผู้แพ้
เกมที่เล่นด้วยกองในลักษณะนี้ ซึ่งการเคลื่อนไหวที่อนุญาตสำหรับแต่ละกองจะถูกกำหนดโดยขนาดของกองเดิม เรียกว่าเกม Taking and Breakingในเอกสาร[ 1 ] เกม Octal เป็นชุดย่อยของเกม Taking and Breaking ซึ่งการเคลื่อนไหวที่อนุญาตจะถูกกำหนดโดยจำนวนโทเค็นที่ถูกนำออกจากกอง
รหัสฐานแปดของเกมระบุไว้ดังนี้
- 0 . d d d d …,
โดยที่เลขฐานแปดd ระบุว่าผู้เล่นได้รับอนุญาตให้ทิ้งกองเหรียญไว้ศูนย์ หนึ่ง หรือสองกอง หลังจากนำ เหรียญ n เหรียญออก จากกอง เลขd คือผลรวมของ
- 1 หากอนุญาตให้เว้นฮีปเป็นศูนย์ 0 หากไม่อนุญาตให้เว้นฮีป
- 2 ถ้าอนุญาตให้เหลือเศษกองเดียว 0 ถ้าไม่ได้รับอนุญาต และ
- 4 ถ้าอนุญาตให้เหลือเศษสองกอง 0 ถ้าไม่อนุญาตให้เหลือสองกอง
โทเค็นศูนย์จะไม่ถูกนับรวมในกอง ดังนั้นตัวเลขd จะเป็นเลขคี่หากสามารถนำโทเค็นn ตัวออกจากกองได้ทั้งหมด และเป็นเลขคู่ในกรณีอื่น ๆ เงื่อนไขของผลลัพธ์แบบหนึ่งกอง (one-heap) ใน d หมายถึงการนำ โทเค็น n ตัวออก จากกองที่มีขนาดมากกว่าn ส่วน ผลลัพธ์แบบสองกอง (two-heap) ในd หมายถึงการนำ โทเค็น n ตัวออก จากกองที่มีขนาดอย่างน้อยn + 2 และแบ่งส่วนที่เหลือออกเป็นสองกองที่ไม่ว่างเปล่า
เกมเลขฐานแปดอาจอนุญาตให้แบ่งกองออกเป็นสองส่วนโดยไม่ต้องนำโทเค็นออก โดยใช้เลข 4 ทางด้านซ้ายของจุดทศนิยม ซึ่งคล้ายกับการเดินหมากในเกมของกรุนดีที่เป็นการแบ่งกองออกเป็นสองส่วนที่ไม่เท่ากัน อย่างไรก็ตาม สัญลักษณ์เกมเลขฐานแปดมาตรฐานไม่มีความสามารถในการแสดงข้อจำกัดของส่วนที่ไม่เท่ากันนี้
เกมเลขฐานแปดที่มีจำนวนหลักที่ไม่ใช่ศูนย์เพียงจำนวนจำกัด เรียกว่าเกมเลขฐานแปดจำกัด
เกมเลขฐานแปดเฉพาะ
นิม
เกมพื้นฐานที่สุดในทฤษฎีเกมเชิงการจัดเรียงคือเกมนิม (Nim ) ซึ่งผู้เล่นสามารถนำโทเค็นออกจากกองได้จำนวนเท่าใดก็ได้ ทำให้เหลือกองโทเค็นอยู่ศูนย์หรือหนึ่งกอง รหัสฐานแปดของเกมนิมคือ0.333...ซึ่งปรากฏในเอกสารทางวิชาการที่ตีพิมพ์แล้วดังนี้เพื่อแสดงส่วนที่ซ้ำกัน เช่น ในทศนิยมซ้ำอย่างไรก็ตาม สิ่งสำคัญคือต้องตระหนักว่าส่วนที่ซ้ำกันนั้นไม่ได้มีบทบาทเช่นเดียวกับในเศษส่วนฐานแปด ในแง่ที่ว่าเกมและถึงแม้จะเป็นเศษส่วนฐานแปด แต่ก็ไม่เหมือนกันเสียทีเดียว
เคย์ลส์
เกมKaylesมักจะแสดงให้เห็นภาพโดยใช้แถวของ หมุด nตัว แต่ก็อาจจำลองโดยใช้กองของ ตัวนับ nตัวได้เช่นกัน ผู้เล่นสามารถนำตัวนับหนึ่งหรือสองตัวออกจากกอง และจัดเรียงส่วนที่เหลือเป็นกองศูนย์ หนึ่ง หรือสองกอง รหัสฐานแปดของเกม Kayles คือ0.77
หมากรุกของดอว์สัน
หมากรุกของดอว์สันเป็นเกมที่เกิดขึ้นจากปริศนาหมากรุกที่โทมัส เรย์เนอร์ ดอว์สัน ตั้งขึ้น ใน Caissa's Wild Rosesปี 1938 [ 3 ] ปริศนานี้ตั้งขึ้นโดยเกี่ยวข้องกับแถวเบี้ยที่อยู่ตรงข้ามกันซึ่งคั่นด้วยแถวเดียว แม้ว่าปริศนานี้จะไม่ได้ตั้งขึ้นเป็นเกมที่เป็นกลางแต่สมมติฐานที่ว่าการจับกินเป็นสิ่งที่จำเป็นหมายความว่าการเคลื่อนที่ของผู้เล่นในแถวใด ๆ จะส่งผลให้แถวนั้นและแถวข้างเคียง (ถ้ามี) ถูกลบออกจากการพิจารณาต่อไปเท่านั้น โดยผู้เล่นฝ่ายตรงข้ามจะเป็นฝ่ายเดินหมาก การจำลองสิ่งนี้เป็นกอง โทเค็น nอัน ผู้เล่นอาจลบโทเค็นทั้งกองหนึ่ง สอง หรือสามอัน อาจลดจำนวนโทเค็นในกองลงสองหรือสามอัน หรืออาจแบ่งกองออกเป็นสองส่วนหลังจากลบโทเค็นสามอัน ดังนั้นหมากรุกของดอว์สันจึงแสดงด้วยรหัสฐานแปด 0.137
เคย์ลส์ของดอว์สัน
ในเกมเวอร์ชัน 0.07ที่เรียกว่าDawson's Kaylesการเดินหมากคือการนำโทเค็นออกจากกองจำนวนสองชิ้นพอดี และกระจายโทเค็นที่เหลือไปยังกองใหม่ศูนย์ หนึ่ง หรือสองกอง เกม Dawson's Kayles ได้ชื่อมาจากความคล้ายคลึง (ที่ไม่ชัดเจนนัก) กับเกม Dawson's Chess กล่าวคือ กอง โทเค็น n + 1 ในเกม Dawson's Kayles จะทำงานเหมือนกับกอง โทเค็น n ในเกม Dawson's Chess ทุกประการ กล่าวกันว่า Dawson's Kayles เป็นญาติสนิทของเกม Dawson's Chess
การสรุปผลไปยังฐานอื่นๆ
เกมฐานแปด เช่นนิมซึ่งการเคลื่อนไหวแต่ละครั้งจะเปลี่ยนกองให้เป็นกองศูนย์หรือหนึ่ง เรียกว่าเกมฐานสี่ เนื่องจากตัวเลขที่ปรากฏมีเพียง 0, 1, 2 และ 3 เท่านั้น สัญกรณ์ฐานแปดอาจขยายไปถึงเกมฐาน สิบหก ได้เช่นกัน ซึ่งตัวเลขจะอนุญาตให้แบ่งกองออกเป็นสามส่วน อันที่จริง ฐานที่มีขนาดใหญ่ตามอำเภอใจก็เป็นไปได้ การวิเคราะห์เกมฐานสี่ ฐานแปด และฐานสิบหกแสดงให้เห็นว่าเกมประเภทเหล่านี้แตกต่างกันอย่างเห็นได้ชัด[ 1 ]และพฤติกรรมของฐานที่ใหญ่กว่านั้นไม่ได้รับการตรวจสอบอย่างละเอียดมากนัก
ลำดับนิม
ทฤษฎีบทSprague–Grundyบ่งชี้ว่าฮีปขนาด n เทียบเท่ากับฮีปนิมที่มีขนาดที่กำหนด ซึ่งโดยทั่วไปจะใช้สัญลักษณ์ G(n) การวิเคราะห์เกมแปดเหลี่ยมจึงประกอบด้วยการหาลำดับของค่านิมสำหรับฮีปที่มีขนาดเพิ่มขึ้น ลำดับนี้ G(0), G(1), G(2) ... โดยทั่วไปเรียกว่าลำดับนิมของเกม
เกมอ็อกทัล จำกัดทั้งหมดที่วิเคราะห์มาจนถึงตอนนี้แสดงให้เห็นลำดับนิมที่เป็นคาบในที่สุด และไม่ว่าเกมอ็อกทัลจำกัดทั้งหมดจะเป็นคาบในที่สุดหรือไม่นั้นยังเป็นคำถามที่เปิดอยู่ ริชาร์ด กาย ได้ระบุไว้ว่าเป็นปัญหาสำคัญในสาขาเกมเชิงคอมบินาทอริก[ 4 ]
Computation records
A complete analysis of an octal game results in finding its period and preperiod of its nim-sequence. It is shown in Winning Ways for your Mathematical Plays that only a finite number of values of the nim-sequence is needed to prove that a finite octal game is periodic, which opened the door to computations with computers.
Octal games with at most 3 octal-digits have been analyzed through the years. There are 167 inequivalent octal games with no more than 3 octal-digits: 144 beginning with 0 and 23 beginning with 4. Of those, 79 of the former and 14 of the latter have nim-sequences that repeat within 250 terms. Of the rest, only 20 have been solved, despite the computation of millions of nim-values by Achim Flammenkamp:[5]