creatio ex nihilo

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

[Profile ทั้งหมด]

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




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

 
impartial Game

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



ถ้าเรากำหนดชื่อเรียกจุดใด ๆ ว่าเป็นจุด P (the previos player is to win) ก็ต่อเมื่อทุกจุดที่มันชี้เป็นจุด N (the next player is to win) หรือเป็นจุดสุดท้าย และเรียกจุดใด ๆ ว่าเป็นจุด N เมื่อมีบางจุดที่มันชี้เป็น P เราสามารถกำหนดกลยุทธ์เพื่อชัยชนะได้จากการดูจุด N-P นี่แหละครับ



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

แล้วในกรณีที่มีมากกว่า 1 เกมล่ะ เรารู้เฉพาะจุด N-P ของแต่ละเกมเพียงพอมั้ย ? เป็นโจทย์ที่นำไปสู่ทฤษฎีของ Sprague-Grundy ซึ่งเป็นการค้นพบของ R.P. Sprague (1935) กับ P.M. Grundy (1939) แยกกันนะครับ ไม่ได้ทำงานร่วมกัน ต่างคนต่างเสนอไอเดียคนละวาระกัน กรณีที่มากกว่า 1 เกมนี้หมายถึง แต่ละรอบ ผู้เล่นเลือกได้ว่าจะเล่นเกมไหน แล้วทำไปตามกติกาของเกมนั้น สมมติว่า 2 เกมคือ G1 กับ G2 ผลรวมของมัน G1 + G2 ถือเป็นอีกเกมหนึ่งต่างหาก ผู้ชนะคือผู้ที่ทำให้คู่ต่อสู้ไม่อาจเดินไปยังสถานะต่อไปได้อีกแล้ว (ติดอยู่ที่จุดสุดท้าย)

กราฟของเกม G1 + G2 มีลักษณะคล้ายกับกราฟที่เกิดจากผลคูณคาร์ทีเชียนของกราฟทั้งสอง ถ้า G1 = (V1,E1) และ G2 = (V2,E2) เกมที่รวม 2 เกมนี้แทนด้วย Gsum = (Vsum,Esum) เมื่อ

Vsum = V1 x V2
Esum = {(v1v2,w1v2)|(v1,w1 E1)} U {(v1v2, v1w2) | (v2, w2) E2}

การเล่นเกมที่รวมจากหลาย ๆ เกมแบบนี้รู้เฉพาะจุด N-P ไม่พอ แต่ต้องรู้ฟังก์ชัน Sprague-Grundy ด้วยครับ พูดง่าย ๆ ค่า Sprague-Grundy นี้ก็คือค่าจำนวนเต็มไม่ติดลบที่จะกำหนดให้กับจุด ที่จุด v ใด ๆ มีค่า Sprague-Grundy เท่ากับจำนวนเต็มไม่ติดลบที่น้อยที่สุดที่ไม่ใช่ค่า Sprague-Grundy ของจุดที่มันชี้ หรือหากจะพูดให้เป็นทางการ กำหนด N = {0,1,2,...} เมื่อ S N แล้ว mex (minimum excluded value) S ได้แก่สมาชิกใน N ที่มีค่าน้อยที่สุดที่ไม่เป็นสมาชิกของ S

mex S = min (N\S)

กราฟ G = (V,E) มีฟังก์ชั่น Sprague-Grundy g: V → N นิยามโดย

g(v) = mex {g(w) | (v, w) E}

ดังนั้นที่สถานะสุดท้าย (ใครเริ่มเล่นเกม ณ สถานะนี้เป็นคนแพ้) มีค่า g(v) = 0 ดูตัวอย่างดังรูป



คุณสมบัติที่น่าสนใจคือจุด P เป็นจุดที่ g(v) = 0 พิสูจน์ง่าย ๆ ครับ จุด P คือจุดที่ชี้ไปยังจุด N ในขณะที่จุด N ต้องมีอย่างน้อย 1 เส้นทางที่ชี้ไปยัง P ดังนั้นไม่มีจุด N ใด ๆ ที่มี g(v) = 0 เท่ากับทุก ๆ จุด P มี g(v) = 0

ที่น่าสนใจจริง ๆ คือ ถ้า G = G1 + G2 เป็นเกมที่รวม 2 เกม และ v = v1v2 เป็นจุดบน G แล้ว g(v) = g(v1) g(v2) เครื่องหมาย แทน XOR ในที่นี้เป็น bitwise ดังนั้นเราต้องเขียนมันเป็นเลขฐาน 2 ก่อน การทำ XOR ระหว่างบิตคือการดูความเหมือนหรือความต่างระหว่างบิต ถ้าเหมือนกัน เช่น 1 1 หรือ 0 0 จะได้ผลลัพธ์เป็น 0 แต่ถ้าต่างกัน เช่น 1 0 หรือ 0 1 จะได้ผลลัพธ์เป็น 1 เครื่องหมาย นี้บางทีก็เรียกมันว่า nim-sum ตัวอย่าง 3 5 = 0112 1012 = 1102 = 6 กล่าวคือจุด v1v2 ที่ g(v1) = g(v2) จะมี g(v1v2) = 0

ลองมาพิสูจน์ทฤษฎีที่อ้างว่า g(v1v2) = g(v1) g(v2) กันนะครับ (คุณอาจขยายเป็นกรณี n เกมใด ๆ ) เริ่มต้น จุด v = v1v2 และกำหนดให้ b = g(v1) g(v2) โดยเราจะแสดงว่าสำหรับ g(v1v2):

(1) ทุกจำนวนเต็มไม่ติดลบ a < b จะมีจุด x1x2 ที่ถูกชี้โดย v1v2 ที่มี g(x1x2) = a

(2) ไม่มีจุด x1x2 ที่ถูกชี้โดย v1v2 มี g(x1x2) เท่ากับ b

ในการแสดงตาม (1) ให้ d = a b และ k เท่ากับจำนวนหลักของ d เมื่อเขียนเป็นเลขฐาน 2 ดังนั้น 2k-1 ≤ d < 2k และ d มี 1 อยู่ตำแหน่งหลักที่ k (นับหลักที่ 1 จากทางขวามือ) เมื่อเรากำหนดให้ a < b และ b ก็ต้องมี 1 อยู่ตำแหน่งหลักที่ k ดังนั้น ณ ตำแหน่งเดียวกันของ a ต้องเป็น 0 และ g(v1) หรือ g(v2) ต้องมี 1 ตัว ที่ตำแหน่งหลักที่ k เป็น 1 (ส่วนอีกตัวก็ต้องเป็น 0) ไม่งั้น หลักที่ k ของ b จะไม่เป็น 1 สมมติว่า g(v1) มีหลักที่ k เป็น 1 ก็แล้วกันนะครับ ถ้าเราเอามันมา XOR กับ d มันจะมีค่าน้อยกว่าตัวมันเอง หรือเขียนว่า d g(v1) < g(v1) ดังนั้นย่อมมีทางเดินจาก v1 สู่ x1 ที่ g(x1) = d g(v1) เท่ากับว่าการเดินจากจุด v1v2 ไปยังจุด x1v2 เป็นการเดินที่เป็นไปได้ตามกติกา และ g(x1) g(v2) = d g(v1) g(v2) = d b = a

พิสูจน์ (2) โดยใช้ข้อขัดแย้ง กำหนดให้ v1v2 ชี้ไปยัง x1x2 ที่มี g(x1x2) = b สมมติให้ x1x2 คือ x1v2 และ g(x1) g(v2) = g(v1) g(v2) อย่างนี้ก็แปลว่า g(x1) = g(v1) นะสิ เกิดข้อขัดแย้งครับ เพราะต้องไม่มีจุดที่มีค่า Sprague-Grundy เท่ากันเชื่อมด้วย edge เดียวตามนิยาม

กลยุทธ์ คือ ถ้านี่เป็นตาของเรา และสถานะที่เราอยู่มีค่า Sprague-Grundy ไม่เท่ากับ 0 แล้ว ณ สถานะนี้มันจะต้องชี้ไปยังจุด ๆ หนึ่งที่มี nim-sum เป็น 0 เลือกเส้นทางที่มันชี้นั่นแหละครับ แล้วคู่ต่อสู้ของเราจะถูกบีบให้เลือกเส้นทางที่ชี้ไปยังจุดที่ nim-sum ไม่เป็น 0 อีกครั้ง สุดท้ายเราชนะ เพราะเราคือผู้ที่เดินครั้งสุดท้ายในเกมสุดท้าย คู่ต่อสู้คือผู้ที่ติดอยู่ในจุดสุดท้าย





Create Date : 14 พฤษภาคม 2551
Last Update : 17 พฤษภาคม 2551 10:30:01 น. 0 comments
Counter : 1048 Pageviews.

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