เกมโพเซ็ต
ในทฤษฎีเกมเชิงคอมบินา ทอริก เกมโพเซตเป็นเกมกลยุทธ์ทางคณิตศาสตร์ ซึ่งเป็นการขยายความเกมที่รู้จักกันดีหลายเกม เช่นนิมและชอมป์ [ 1 ] ในเกมดังกล่าว ผู้เล่นสองคนเริ่มต้นด้วยโพเซต ( เซตที่มีลำดับบางส่วน ) และผลัดกันเลือกจุดหนึ่งในโพเซต โดยนำจุดนั้นและจุดทั้งหมดที่มากกว่าออกไป ผู้เล่นที่ไม่มีจุดให้เลือกเหลืออยู่จะเป็นผู้แพ้
เกมเพลย์
กำหนดให้เซตที่มีลำดับบางส่วน ( P , <)
แทนเซตลำดับที่เกิดจากการลบx ออกจากP
เกมโพเซตบนPที่เล่นระหว่างผู้เล่นสองคนซึ่งตั้งชื่อตามธรรมเนียมว่าอลิซและบ็อบมีดังนี้:
- อลิซเลือกจุดx ∈ Pโดยแทนที่Pด้วยP จากนั้นส่งตาให้บ็อบซึ่งเล่นที่P แล้วส่งตาให้อลิซอีกครั้ง
- ผู้เล่นจะแพ้หากถึงตาของตนแล้วไม่มีคะแนนให้เลือก
ตัวอย่าง
ถ้าPเป็นเซตที่มีลำดับสมบูรณ์และจำกัด การเล่นเกมในPจะเหมือนกับการเล่นเกมNimที่มีฮีปขนาด | P | ทุกประการ เพราะในทั้งสองเกม สามารถเลือกการเคลื่อนไหวที่นำไปสู่เกมประเภทเดียวกันที่มีขนาดเล็กกว่า | P | ได้ ในทำนองเดียวกัน เกม poset ที่มีการรวมกันแบบไม่ทับซ้อนกันของลำดับสมบูรณ์จะเทียบเท่ากับเกม Nim ที่มีฮีปหลายฮีปที่มีขนาดเท่ากับสายโซ่ใน poset
กรณีพิเศษของเกม Hackenbushซึ่งขอบทั้งหมดเป็นสีเขียว (สามารถตัดได้โดยผู้เล่นทั้งสองฝ่าย) และทุกการจัดเรียงมีลักษณะเป็นป่าอาจแสดงออกมาในทำนองเดียวกันได้ ในรูปของเกมโพเซตบนโพเซต ซึ่งสำหรับทุกองค์ประกอบxจะมีองค์ประกอบy อย่างมากที่สุดเพียงหนึ่งเดียว ที่x ครอบคลุมyถ้าxครอบคลุมyแล้วyจะเป็นองค์ประกอบแม่ของxในป่าที่ใช้เล่นเกม
Chompอาจแสดงออกมาในทำนองเดียวกันได้ โดยเป็นเกมโพเซตบนผลคูณของลำดับทั้งหมดซึ่งได้ลบค่าต่ำสุด ออกไปแล้ว
ค่ากรุนดี้
เกมโพเซตเป็นเกมที่เป็นกลางหมายความว่าทุกการเคลื่อนไหวที่อลิซสามารถทำได้นั้น บ็อบก็สามารถทำได้เช่นกันหากอลิซได้รับอนุญาตให้ผ่านและในทางกลับกัน ดังนั้น ตามทฤษฎีบทสปราก-กรุนดีทุกตำแหน่งในเกมโพเซตจะมีค่ากรุนดี ซึ่งเป็นตัวเลขที่อธิบายตำแหน่งที่เทียบเท่ากันในเกมนิม ค่ากรุนดีของโพเซตสามารถคำนวณได้จากจำนวนธรรมชาติที่น้อยที่สุดที่ไม่ใช่ค่ากรุนดีของP x ๆ x ∈ Pนั่นคือ[ 2 ]
ตัวเลขนี้อาจใช้เพื่ออธิบายกลยุทธ์การเล่นเกมที่ดีที่สุดในเกมโพเซ็ต โดยเฉพาะอย่างยิ่ง ค่ากรุนดีจะมีค่าไม่เป็นศูนย์เมื่อผู้เล่นที่ถึงตาเล่นมีกลยุทธ์ที่ชนะ และจะมีค่าเป็นศูนย์เมื่อผู้เล่นปัจจุบันไม่สามารถเอาชนะคู่ต่อสู้ที่เล่นได้ดีที่สุด กลยุทธ์ที่ชนะในเกมประกอบด้วยการย้ายไปยังตำแหน่งที่มีค่ากรุนดีเป็นศูนย์ เมื่อใดก็ตามที่เป็นไปได้
การขโมยกลยุทธ์
การโต้แย้งแบบขโมยกลยุทธ์แสดงให้เห็นว่าค่า Grundy ไม่เป็นศูนย์สำหรับทุก poset ที่มีค่าสูงสุดเพราะให้xเป็นค่าสูงสุดของเซตที่มีลำดับบางส่วนPถ้าP มีค่า Grundy เป็นศูนย์ แสดงว่าPเองมีค่าไม่เป็นศูนย์ ตามสูตรข้างต้น ในกรณีนี้xเป็นการเดินหมากที่ชนะในPในทางกลับกัน ถ้าP มีค่า Grundy ไม่เป็นศูนย์ แสดงว่าต้องมีการเดินหมากที่ชนะyในP เช่นกัน โดยที่ค่า Grundy ของ ( P ) เป็นศูนย์ แต่ตามสมมติฐานที่ว่าxเป็นค่าสูงสุดx > yและ ( P ) = P ดังนั้นการเดินหมากที่ชนะyก็มีอยู่ในP เช่น กัน และPก็ต้องมีค่า Grundy ไม่เป็นศูนย์ด้วย[ 1 ]
ด้วยเหตุผลที่ไม่สำคัญนัก เซตลำดับที่มีค่าต่ำสุดจะมีค่า Grundy ที่ไม่เป็นศูนย์ด้วยเช่นกัน กล่าวคือ การเดินไปยังค่าต่ำสุดนั้นเป็นการเดินที่ได้เปรียบเสมอ
ความซับซ้อน
การตัดสินผู้ชนะของเกม poset จำกัดใดๆ ถือเป็นPSPACE-complete [ 3 ] ซึ่งหมายความว่า เว้นแต่ P=PSPACE การคำนวณค่า Grundy ของเกม poset ใดๆ จะทำได้ยากในเชิงการคำนวณ
- 1 2 Soltys, Michael; Wilson, Craig (2011), "เกี่ยวกับความซับซ้อนของการคำนวณกลยุทธ์การชนะสำหรับเกม poset จำกัด", Theory of Computing Systems , 48 (3): 680– 692, CiteSeerX 10.1.1.150.3656 , doi : 10.1007/s00224-010-9254-y , MR 2770813 , S2CID 2720334 .
- ↑ Byrnes, Steven (2003), "Poset game periodicity" (PDF) , Integers , 3 (G3): 1– 16, MR 2036487 .
- ↑ Grier, Daniel (2012), "การตัดสินผู้ชนะของเกม Poset จำกัดใดๆ ก็ตามนั้นสมบูรณ์แบบ PSPACE", Automata, Languages, and Programming , Lecture Notes in Computer Science, vol. 7965, pp. 497–503 , arXiv : 1209.1750 , Bibcode : 2012arXiv1209.1750G , doi : 10.1007/978-3-642-39206-1_42 , ISBN 978-3-642-39205-4, S2CID 13129445 .