creatio ex nihilo

ศล
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 85 คน [?]




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 
the game of Nim

นิมถือเป็นเกมที่สุดแห่งความยอดฮิตในการเกริ่นนำทฤษฎีเกม กติกาง่าย ๆ แบ่งเหรียญเป็น n กอง กองที่ i มีจำนวน xi เหรียญ ผู้เล่น 2 คนผลัดกันหยิบเหรียญออกคนละครั้ง ครั้งละกอง กองละกี่เหรียญก็ตามใจ ตั้งแต่ 0 ถึง xi (แต่ถ้าใครคิดจะหยิบ 0 เหรียญก็อย่าเล่นดีกว่าครับ ต่างฝ่ายต่างหยิบ 0 เหรียญก็นั่งมองตากันเท่านั้นเอง) ใครหยิบเหรียญสุดท้ายเป็นคนชนะ



เรามาวิเคราะห์แบบเบสิกกรณี n = 1 คือมีเหรียญกองเดียว จำนวน x1 เหรียญ คนเล่นก่อนก็หยิบมันทั้งกองคว้าชัยชนะไป กรณี n = 2 แต่ละกองมีเหรียญจำนวน x1 และ x2 ตามลำดับ เขียนแทนด้วย (x1,x2) ถ้า x1 ไม่เท่ากับ x2 คนแรกหยิบเหรียญเพื่อทำให้ x1 = x2 ซะ ก็จะชนะ ถูกมั้ยครับ สถานะ (x1,x1) แบบนี้เราเรียกสถานะ P คือสถานะที่หากผู้ใดเริ่มเล่นในสถานะนี้ย่อมแพ้ สถานะต่อไปถัดจาก P ต้องเป็น N เท่านั้น, N คือสถานะที่หากผู้ใดเริ่มเล่นในสถานะนี้ย่อมมีกลยุทธ์ที่นำไปสู่ชัยชนะ เพราะสถานะที่ต่อจาก N ต้องมีอย่างน้อย 1 สถานะที่เป็น P ฉะนั้นกลยุทธ์ของผู้เล่นเกมที่ได้เล่นในสถานะ N คือ เลือกทางเดิน (หรือเลือกหยิบเหรียญ) ที่ทำให้คู่ต่อสู้เผชิญหน้ากับสถานะ P อย่างเช่นในกรณี n = 2 ผู้เริ่มที่ (x1,x2) ต้องหยิบเหรียญเพื่อทำให้เป็น (x1,x1) หรือ (x2,x2) ก็จะชนะครับ กรณี n = 3 ก็ทำนองเดียวกัน คงมองออกได้ไม่ยากว่า (1,1,1) เป็น N หรือ (1,1,2), (1,1,3), (1,2,2) เหล่านี้ก็เป็น N เพราะมันสามารถหยิบแล้วทำให้เกิด (0,1,1), (1,1,0), (1,1,0) และ (0,2,2) ซึ่งเป็น P ได้ ตามลำดับ หรือสถานะ (1,2,3) เป็น P ไม่ว่าคนที่เล่นในสถานะนี้จะหยิบแบบใด สถานะถัดไปคือ N คำถามที่น่าสนใจคือ มันมีวิธีการทั่วไปใดจะตรวจสอบได้มั้ยว่า (x1,x2,x3) เป็น N หรือ P ?

มีครับ นั่นคือทฤษฎีของ Charles L. Bouton เขาว่า สถานะ (x1,x2,x3,...,xn) เป็น P ก็ต่อเมื่อ x1 x2 x3 ... xn = 0, เครื่องหมาย แทน bitwise XOR ในเลขฐาน 2 อาจเรียกว่า nim-sum (ใครที่เรียนดิจิทัลมาจะรู้ว่า มันก็คือการบวกเลขฐาน 2 บิตเดียวที่ไม่มี carry)

พิสูจน์ได้โดยกำหนดให้ P แทนเซ็ตสถานะทั้งหมดที่มี nim-sum เท่ากับศูนย์ และ N แทนเซ็ตสถานะอื่น ๆ ที่เหลือ เรารู้ว่า ณ สถานะสุดท้ายคือ (0,0,0,...,0) เป็น P หรือ 0 0 0 ... 0 = 0 และทุกสถานะที่อยู่ใน N ย่อมมีทางที่ไปสู่ P ทำได้โดยการเขียน (x1,x2,x3,...,xn) เป็นเลขฐาน 2 แล้วเปลี่ยน 1 เป็น 0 สำหรับ xi เพื่อทำให้ใน nim-sum เท่ากับ 0 ด้วยวิธีการนี้ xi* ที่เกิดจากการเปลี่ยนดังกล่าวจะมีค่าน้อยกว่า xi นั่นคือทุกสถานะใน N จะมีอย่างน้อยหนึ่งทางนำไปสู่สถานะใดสถานะหนึ่งใน P และจากสถานะใน P ทุกทางจะนำไปสู่สถานะใดสถานะหนึ่งใน N เพราะการเปลี่ยนจาก xi* ที่เป็น P ซึ่งมี x1 x2 x3 ... xi* ... xn = 0 ไปเป็น xi** ไม่สามารถทำให้ x1 x2 x3 ... xi** ... xn = 0 ได้ เนื่องจาก หากมันเท่ากับ 0 แล้ว xi* = xi** ซึ่งเป็นไปไม่ได้ครับ ดังนั้น (x1,x2,x3,...,xi**,...,xn) อยู่ใน N

เช่นเกมเริ่มต้นด้วยเหรียญ 3 กอง มีจำนวนกองละ 13 12 และ 8 ตามลำดับ เขียนแทน (13,12,8) ด้วยเลขฐาน 2

11012 = 13
11002 = 12
10002 = 8

nim-sum = 10012 = 9 มันเป็น N ดังนั้นผู้เล่นคนแรกทำให้เป็น P ได้โดยเปลี่ยน 11012 ให้เป็น 01002 หรือเปลี่ยน 11002 ให้เป็น 1012 หรือเปลี่ยน 10002 ให้เป็น 12 ซึ่งได้แก่การหยิบ 9 เหรียญออกจากกงอ 13 เหรียญ หรือหยิบ 7 เหรียญออกจากกอง 12 เหรียญ หรือหยิบ 7 เหรียญออกจากกอง 8 เหรียญตามลำดับ เลือก 1 ใน 3 แบบนี้ผู้เล่นคนแรกบังคับให้คู่ต่อสู้เผชิญหน้า P และพ่ายแพ้ในที่สุดครับ

พูดมาตั้งนาน สงสัยมั้ยครับ ทำไมเรียกเกมนิม นิมนี่ว่ากันว่า (อย่าเชื่อมากนะ) เริ่มแรกมาจากเกมหยิบหิน หรือ Jianshizi ของจีน ที่เรียก Nim อาจแผลงมาจาก Nimm! ซึ่งเป็น imperative รูป du ในภาษาเยอรมันจากอินฟินิทีฟ Nehmen แปลว่า take (ในภาษาอังกฤษโบราณเอง nim ก็แปลว่า take) ทั้งมีคนสังเกตว่าแอมบิแกรมของ NIM ก็คือ WIN





Create Date : 16 พฤษภาคม 2551
Last Update : 17 พฤษภาคม 2551 10:09:32 น. 0 comments
Counter : 2466 Pageviews.

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.