Combinatorial Game ไขความลับ เกมนับหนึ่งถึงสิบที่สามารถการันตีชัยชนะได้

Combinatorial Game ไขความลับ เกมนับหนึ่งถึงสิบที่สามารถการันตีชัยชนะได้

Combinatorial Game

หลายคนคงเคยเล่นเกมนับเลข 1 ถึง 10 สลับกัน โดยกติกามีอยู่ว่าแต่ละครั้งนับเพิ่มได้มากสุด 3 ตัวเลข คือ นับเพิ่ม 1, 2 หรือ 3 ใครนับคนสุดท้ายชนะ หรือใครนับคนสุดท้ายแพ้

เกมนี้อาจเป็นเกมธรรมดาทั่วไปที่เด็กประถมเล่นกัน เป็นเกมง่ายๆ ที่หลายคนคิดว่าถ้าโชคดีก็ชนะเอง แต่แท้จริงแล้วมันมีวิธีการันตีชัยชนะด้วยนะ

ชัยชนะที่ไม่ได้เกิดจากความบังเอิญ

เกมนับ 1 ถึง 10 เล่นกัน 2 คน(A กับ B) นับเพิ่มได้มากสุด 3 ตัวเลข คือ นับเพิ่ม 1, 2 หรือ 3 ใครนับ 10 ชนะ เริ่มได้

exgame1

เห็นมั้ยครับ ไม่ว่า B จะเล่นอย่างไร ก็ไม่สามารถชนะ A ได้เลย

ลองดูอีกตัวอย่างละกัน คราวนี้ให้ B เริ่มก่อนบ้าง แต่ขอเปลี่ยนจากนับ 10 ชนะ เป็นนับ 20 ชนะ แล้วกัน

exgame2

เช่นกันครับ A ชนะ ฮ่า ฮ่า หลายคนอาจเห็นสิ่งที่ A ได้ทำเหมือนกัน 3 ครั้ง ในการเล่นแต่ละเกม (เกมนับ10 และ เกมนับ20) อย่างที่บอกไว้ครับเกมนับเลขนี้การันตีชัยชนะตั้งแต่เลือกแล้วว่าจะเริ่มเกมก่อนหรือหลัง เพราะเกมนี้มีรูปแบบการเล่นที่เรียกว่า Combinatorial Game ซึ่งเป็นรูปแบบเกมรูปแบบหนึ่งที่นักคณิตศาสตร์ศึกษากันใน เรื่อง ทฤษฎีเกม (Game Theory)

Combinatorial Game คืออะไร

Combinatorial Game เป็นเกมที่มีผู้เล่น 2 คน สลับกันเล่น มีกฎการเล่นตายตัวสำหรับผู้เล่นทั้งคู่ และเกมจบลงเมื่อผู้เล่นฝ่ายใดฝ่ายหนึ่งไม่สามารถเล่นต่อไปได้ นอกจากเกมนับเลขนี้แล้ว หมากรุก, โกะ หรือเกมง่าย ๆ ที่เล่นฆ่าเวลาอย่าง เอ็กซ์โอ (Tic-Tac-Toe) ก็เป็น Combinatorial Game เช่นกัน

Combinatorial Game นี้ล้วนเป็นเกมที่มีแผนการเล่นที่การันตีชัยชนะได้ ย้ำนะว่าต้องมีแผนการเล่นที่ดี อย่างเกมหมากรุกที่เราเล่นกับคอมพิวเตอร์นั้น คอมพิวเตอร์จะมีวิธีการในการตัดสินใจเดินเกมที่นำไปสู่ชัยชนะ หรืออย่าง Alpha Go ก็มีวิธีการในการตัดสินใจเดินเกมเช่นกัน

เรากลับมาเข้าเรื่องเกมนับเลขกัน หลายคนคงสงสัยกันแล้วว่าเกมนี้มีแผนการเล่นอย่างไรกันถึงได้การันตีชัยชนะได้ ก่อนอื่นมาทำความรู้จัก 5 คำนี้กันก่อน คือ P-positions, N-positions, Terminal Position, กฎการเล่นปกติ และกฎการเล่นสลับ

P-positions คือ ตำแหน่งที่ผู้เล่นก่อนหน้าหรือผู้เล่นที่เพิ่งเดินเกมเป็นฝ่ายชนะ (Previos player win)

N-positions คือ ตำแหน่งที่เล่นแล้วผู้เล่นถัดไปเป็นฝ่ายชนะ (Next player win)

Terminal position คือ ตำแหน่งที่ไม่สามารถเล่นต่อได้หรือตำแหน่งจบเกม เช่น เกมนับ 10 มี 10 เป็น Terminal position

กฎการเล่นปกติ คือ ผู้เล่นที่เล่นคนสุดท้ายเป็นฝ่ายชนะ

กฎการเล่นสลับ คือ ผู้เล่นที่เล่นคนสุดท้ายเป็นฝ่ายแพ้

ท่านผู้อ่านคงดูออกแล้วว่า ตำแหน่งไหนเป็น Terminal position แต่ไม่เห็นเข้าใจเลยจะรู้ได้อย่างไรว่า ตำแหน่งไหนเป็น P ตำแหน่งไหนเป็น N

โดยกฎการเล่นปกติ จะให้ Terminal position เป็น  P-position เสมอ ส่วนกฎการเล่นสลับ จะให้ Terminal position เป็น  N-position เสมอ สำหรับตำแหน่งอื่น ๆ ที่เหลืออยู่จะใช้วิธีการ 3 ขั้นตอนง่าย ๆ คือ

  1. ตำแหน่งที่เข้าถึง P ใน 1 ตา เป็นตำแหน่ง N
  2. ตำแหน่งถัดจาก N ที่ยังว่างอยู่ เป็นตำแหน่ง P
  3. ทำซ้ำข้อ 1. และ 2. กับตำแหน่ง P ใหม่นี้ ระบุตำแหน่งได้ครบทุกตัวเลข

หนทางสู่ชัยชนะ

table1
ระบุตำแหน่ง P

เกมนับ 10 นับเพิ่มได้มากสุด 3 ตัวเลข คือ นับเพิ่ม 1, 2 หรือ 3 ใครนับคนสุดท้ายชนะ เป็น Combinatorial Game ที่มีกฎการเล่นปกติ (ผู้เล่นคนสุดท้ายเป็นฝ่ายชนะ) จะได้ Terminal position คือ 10 เพราะฉะนั้น 10 คือ ตำแหน่ง P

table2
ระบุตำแหน่ง N

เข้าถึง P ใน 1 ตา เป็น N คือ ถ้านับ 9 เพิ่ม 1,  นับ 8 เพิ่ม 2 หรือ นับ 7 เพิ่ม 3 จะได้ 10 เพราะฉะนั้น 7,8 และ 9 เป็นตำแหน่ง N

table3
ระบุตำแหน่ง P

ตำแหน่งถัดจาก N ที่ยังว่างอยู่ คือ 6 เพราะฉะนั้น 6 เป็นตำแหน่ง P ใหม่

table4
ระบุตำแหน่ง N

ทำซ้ำวิธีการเดิมจะได้ลำดับการระบุตำแหน่ง ดังนี้

table5
ระบุตำแหน่ง P
table6
ระบุตำแหน่ง N

การการันตีชัยชนะ

ภายใต้กฎการเล่นผู้เล่นที่เริ่มเกมต่อจากตำแหน่ง P ไม่มีทางไปหยุดที่ตำแหน่ง P ถัดไปได้ ไม่ว่าอย่างไรต้องมาหยุดที่ตำแหน่ง N และผู้เล่นที่เริ่มเกมต่อจากตำแหน่ง N สามารถหยุดที่ตำแหน่ง P ได้ใน 1 ตา ซึงเกมนี้มีกฎการเล่นปกติ (ผู้เล่นคนสุดท้ายชนะ) และเรากำหนดตำแหน่งสุดท้ายเป็น P ดังนั้น แผนการเล่นที่การันตีชัยชนะ คือ ให้เราหยุดที่ตำแหน่ง P ในทุกตา

จากตัวอย่างการเล่นของ A กับ B ที่เล่นให้ดูในตอนต้น ทุกตาที่ A เล่นจะหยุดที่ 2, 6 และ 10 เสมอ ซึ่งทั้ง 3 ตำแหน่งนี้ คือ ตำแหน่ง P นั่นเอง หรือเขียนเป็นภาษาคณิตศาสตร์ได้ว่า P = { x | x mod 4 = 2}

หลายคนอาจจะสงสัยทำไมต้องเขียนเป็นภาษาคณิตศาสตร์ให้มันยุ่งยากด้วยในเมื่อมีเลขเพียง 3 ตัวเท่านั้นเอง ใช่ครับ เกมนี้มีตำแหน่ง P เพียง 3 ตำแหน่งเท่านั้น แต่ถ้าเราเปลี่ยนเป็นนับถึง 20, นับถึง 100 หรือนับถึง 200 ล่ะ เราคงนั่งไล่หา P กันหลายนาที จนเพื่อนเรารอไม่ไหวหนีไปเล่นกับคนอื่นแทน ฮ่า ฮ่า ฮ่า

ถ้าเราสังเกตดี ๆ ตำแหน่ง P และ N จะมีรูปแบบการเกิดเหมือนเดิมเสมอ อย่างเกมนับ 10 จะเกิดรูปแบบเป็น “N P N N” ซ้ำไปเรื่อย ๆ หรือพูดให้ง่ายก็คือ ทุก ๆ  4 ตัว ตั้งแต่เริ่มเกม P จะเกิดที่ตำแหน่ง 2 ใน 4 ตัวนั้นเสมอ นั่นคือตำแหน่งที่หารด้วย 4 แล้วเหลือเศษ 2 (x mod 4 = 2) จะเป็นตำแหน่ง P

คราวนี้ไม่ว่าใครชวนเล่นเกมนับถึง 20 นับเพิ่มทีละ 1,2 หรือ 3, เกมนับถึง 100 นับเพิ่มทีละ 2, 3, 5 หรือ 8 หรือเกมนับแบบอื่น ๆ  เราก็สามารถการันตีชัยชนะได้แล้ว เพียงแค่เลือกให้ถูกว่าเราจะเริ่มก่อน หรือเริ่มทีหลัง เพื่อให้การนับของเราไปหยุด ณ ตำแหน่ง P

อ้างอิง:

เขียนโดย

Jetzada Chuaychuwong

นิสิตภาควิชาคณิตศาสตร์ ผู้หลงใหลในความเรียบง่ายที่แฝงไปด้วยความซับซ้อน
   
Tags: ,