ความคิดเห็นที่ 36
หมายเหตุเพิ่มเติม
มีความเห็นที่น่าสนใจครับ
โดยคุณชาติใน #20 สนใจว่า จะเขียนรูปแบบที่ชนะให้เป็นสมการคณิตศาสตร์ได้หรือไม่
คุณ 512 ใน #26 พูดถึงการใช้โปรแกรมจำพวก AI เพื่อให้หารูปแบบทั้ง 1024 states
คุณศล(สวัสดีครับ) ใน #28 ยกกรณีของเกมที่น่าจะอยู่ในตระกูลเดียวกันที่ชื่อว่านิม
และแนะว่าน่าจะใช้ทฤษฎีของ R.P. Sprague กับ P.M. Grundy ช่วยพิสูจน์ได้
(เป็นบล๊อกที่น่าสนใจมากครับ)
ความจริงตั้งแต่เห็นโจทย์ของคุณดอกต้อยติ่ง [3 5 7] และเห็นที่คุณชาติทักมา
ผมก็คิดว่าน่าสนใจเหมือนกันว่า ถ้าเราขยายให้เกมนี้ใหญ่ขึ้น ก็น่าจะพบสิ่งน่าสนใจในเชิงคณิตศาสตร์ได้
ขั้นแรก ผมลงมือเขียนโปรแกรม ในลักษณะของ backtracking
เพื่อค้นหา state-space สำหรับโจทย์ที่กระดานทีขนาดใดๆ (แถวแรกไม่จำเป็นต้องเป็น 1 ขีด)
(หมายเหตุสำหรับคุณ 512: กับปัญหาลักษณะนี้ ใช้ backtracking หรือ dynamic programming
จะดีกว่าการใช้ artificial neural network ครับ แล้วก็ดีกว่า brute-force ด้วยครับ
เพราะไม่ต้องค้นทุก state-space จริงๆ ถึงแม้พื้นฐานแล้ว จะคล้ายกันก็ตาม)
แนวคิดคือ ผมจะแบ่ง state ของเกม ออกเป็น 2 พวก คือ Winning state กับ Losing state
โดยถ้ากระดานของ Winning state นั้นๆ จะต้องมีอย่างน้อยหนึ่งทางเลือกที่ฝ่ายตรงข้ามจะต้องแพ้ทุกกรณี
ถ้าไม่อย่างนั้น จะถือว่า state นั้น เป็น Losing state
โดยถือว่ากระดาน [1] (กระดานที่มีขีดเหลือเพียงขีดเดียว) จะเป็น Losing state (ตามที่โจทย์กำหนด)
(ตรงนี้คล้ายๆ กับทฤษฎีของ Sprague-Grundy ในบล๊อกของคุณศล ซึ่งใช้ state N และ state P
แต่ปัญหาในการใช้ทฤษฎีของ Sprague-Grundy คือ เราจะต้องทราบฟังก์ชัน Sprague-Grundy ด้วย
ซึ่งการเขียนโปรแกรมนี้ ก็เพื่อทำความเข้าใจกับปัญหานี้ให้มากขึ้น แล้วดูว่าจะมี pattern ใดปรากฏขึ้นหรือไม่)
โปรแกรมสามารถค้นหาคำตอบได้ดีทีเดียว
สำหรับโจทย์ [4 3 2 1] (ขอเขียนกระดานโดยเรียงกลุ่มมากขีดขึ้นก่อนนะครับ) มันตอบว่า win via [3 2 1 1 1]
และสำหรับโจทย์ [7 5 3] มันตอบว่า win via [7 5 2]
(ส่วนโจทย์ [7 5 2] มันตอบว่า "sorry, this is a losing board")
ซึ่งมันทำให้ผมสรุปได้ว่า สำหรับการเล่นแบบดั้งเดิม ([4 3 2 1] split ได้)
กระดานที่ทำให้แพ้แน่ๆ (losing boards) จะมีลักษณะดังต่อไปนี้ครับ (ให้ m >= 2):
- [1 (1 1)*] (ได้แก่ [1], [1 1 1], [1 1 1 1 1] เป็นต้น)
- [m m (1 1)*] (ได้แก่ [2 2], [2 2 1 1], [3 3], [3 3 1 1] เป็นต้น)
- [3 2 1]
กระดานอื่นๆ นอกเหนือจากนี้ ก็จะเป็นกระดานที่ทำให้ชนะแน่ๆ (winning boards) นั่นเองครับ
หลังจากนั้น ผมลองวิเคราะห์เพิ่มเติมสักพัก
พบว่า set ของ lossing boards นั้น มีความสวยงามเชิงคณิตศาสตร์พอตัวทีเดียว
(set ของ lossing boards ที่มีแค่ 2 กองเท่านั้น ทำให้ผมนึกถึง set ของ prime number ตะหงิดๆ)
โดยสามารถสร้างทฤษฎี (ตั้งชื่อเล่นว่า Crossing-out Theorem) ที่ใช้พิสูจน์ได้ว่า
กระดานที่ยกมา เป็นกระดานแพ้ หรือกระดานชนะ
ด้วยการ transform (หรือจะเรียกว่า reduce ก็ได้ครับ) กระดาน ไปสู่กระดานที่ equivalent กัน (คือผลแพ้ชนะเหมือนกัน)
(ซึ่งการ reduce board นี้ ชวนให้นึกถึงวิชา matrix เลยครับ)
ตัวอย่างเช่น 2 กระดานข้างล่างนี้ จะมีอยู่กระดานนึงที่เป็นกระดานชนะ อีกกระดานจะเป็นกระดานแพ้ครับ
(ถ้าใครอยากปวดหัวเล่น จะลองคิดดูก็ได้นะครับ)
[11 9 8 7 5 4 3]
[11 9 8 7 5 4 3 1]
เกมเล็กๆ ที่เคยเล่นแบบไม่คิดอะไรมากตอนเด็กๆ
พอลองวิเคราะห์แล้ว เอาเรื่องเหมือนกันแฮะ
ขอขอบคุณทุกท่านที่เข้ามาร่วมสนุกกันครับ.
จากคุณ :
ลุงแว่นใจดี
- [
6 ต.ค. 51 08:20:33
A:202.91.18.194 X: TicketID:183630
]
|
|
|
