กลับไปหน้าบทความ

อ่าน 3 นาที

เกมโพเซ็ต

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

เกมโพเซ็ต

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

เกมเพลย์

กำหนดให้เซตที่มีลำดับบางส่วน ( P ,  <)

พีx=พี{เอเอx}{\displaystyle P_{x}=P-\{a\mid a\geq x\}}

แทนเซตลำดับที่เกิดจากการลบ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 ]  

จี(พี)=นาที(เอ็น{จี(พีx)xพี}).{\displaystyle G(P)=\min {\bigl (}\mathbb {N} \setminus \{G(P_{x})\mid x\in P\}{\bigr )}.}

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

การขโมยกลยุทธ์

การโต้แย้งแบบขโมยกลยุทธ์แสดงให้เห็นว่าค่า 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. 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   .
  2. Byrnes, Steven (2003), "Poset game periodicity" (PDF) , Integers , 3 (G3): 1– 16, MR 2036487 .
  3. 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 .

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ เกมโพเซ็ต

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

ตัวอย่าง

ถ้า P เป็น เซตที่มีลำดับสมบูรณ์และ จำกัด การเล่นเกมใน P จะเหมือนกับการเล่นเกม Nim ที่มีฮีปขนาด | P | ทุกประการ เพราะในทั้งสองเกม สามารถเลือกการเคลื่อนไหวที่นำไปสู่เกมประเภทเดียวกันที่มีขนาดเล็กกว่า | P | ได้ ในทำนองเดียวกัน เกม poset...

ค่ากรุนดี้

เกมโพเซตเป็น เกมที่เป็นกลาง หมายความว่าทุกการเคลื่อนไหวที่อลิซสามารถทำได้นั้น บ็อบก็สามารถทำได้เช่นกันหากอลิซได้รับอนุญาตให้ ผ่าน และในทางกลับกัน ดังนั้น ตาม ทฤษฎีบทสปราก-กรุนดี ทุกตำแหน่งในเกมโพเซตจะมีค่ากรุนดี...

การขโมยกลยุทธ์

การ โต้แย้งแบบขโมยกลยุทธ์ แสดงให้เห็นว่าค่า Grundy ไม่เป็นศูนย์สำหรับทุก poset ที่มี ค่าสูงสุด เพราะให้ x เป็นค่าสูงสุดของเซตที่มีลำดับบางส่วน P ถ้า P มีค่า Grundy เป็นศูนย์ แสดงว่า P เองมีค่าไม่เป็นศูนย์ ตามสูตรข้างต้น ในกรณีนี้ x เป็นการเดินหมากที่ชนะใน P...