เกม 24 กับ วิทยาการคอมพิวเตอร์

เกม 24 คืออะไร?

สำหรับคนที่ยังไม่เคยได้ยินมาก่อนเลยว่า “เกม 24” คืออะไร: มันเป็นเกมคิดเลขที่คนเล่นจะได้เลข 1-9 มา 4 ตัว แล้วเราจะเอาเลขพวกนั้นมาบวก ลบ คูณ หารให้ยังไงก็ได้ ให้ได้ผลลัพธ์เป็น 24

อย่างเช่น มีตัวเลข 3 2 5 9 ให้คำนวณให้ได้ 24

ซึ่งตัวอย่างนึงที่ทำได้ก็จะเป็นว่า

• $5 - 2 = 3$
• $9 \times 3 = 27$
• $27 - 3 = 24$

ถ้าเอามาเลองวาดความเชื่อมโยงเล่นๆก็จะได้ว่า

แน่นอนว่านี่เป็นแค่หนึ่งในรูปแบบที่ทำได้ แต่คำถามคือเราจะไปรู้ได้ยังไงล่ะว่าต้องทำอะไรบ้าง แล้วทำอันไหนก่อนหลัง

ถ้าอยากลองคิดข้ออื่นเล่นๆดูก็เข้าไปเล่นได้ที่ เกม 24 เว็บ KruPloyหรือไม่ก็ลองไปมองทะเบียนท้ายรถสักคันแล้วคิดตามดูก็ได้ (แอดทำบ่อย 🤣)

วิธีแก้เกม 24 เกี่ยวกับวิทยาการคอมพิวเตอร์อย่างไร?

สมมติก่อนว่าเราไม่รู้อะไรเลยเกี่ยวกับเทคนิกเกม 24 ปัญหาแรกเลยคือเราจะเริ่มตรงไหนก่อน

ด้วยความที่เราไม่รู้หรอกว่าวิธีไหนมันดี สิ่งที่เราทำได้ก็มีแค่ลองมันทุกแบบที่คิดได้นั่นแหละ ก็คือคิดไปเลยว่า “ถ้าเอา x กับ y มา บวก/ลบ/คูณ/หาร กันแล้วจะได้ค่าอะไร” แล้วหลังจากนั้นเราทำอะไรต่อได้บ้าง

แน่นอนว่าการทำแบบนี้ไม่ได้การันตีว่าเราจะได้คำตอบตั้งแต่การลองครั้งแรก แต่ก็เป็นการเริ่มต้นที่ดีเพราะมันทำให้เราได้ข้อมูลมากขึ้นเรื่อยๆ โดยวิธีแบบนี้ในทางวิทยาการคอมพิวเตอร์เราจะเรียกมันว่า Depth-First Search

ก็คือ เราก็ลองไปเรื่อยๆจากตอนแรกที่ได้ว่า $3\ 2\ 5\ 9$ เราสามารถคำนวณมันกลายเป็น $2\ 2\ 9$ ได้ และเป็น $4\ 9$ได้จากการทำ $5-3=2$ กับ $2 \times 2 = 4$

พอเราเหลือแค่ $4$ กับ $9$ เราก็ลองทุกวิธีคือ $4 + 9, 4 - 9, 9-4, 4 * 9, 4 / 9, 9 / 4$ แน่นอนว่าเราไม่ได้คำตอบที่เป็น $24$ เลย แต่นั่นก็ไม่เป็นไรเพราะเราตอนนี้เราก็รู้แล้วว่า การที่ได้คำตอบเป็น $4\ 9$ มาไม่ช่วยให้เราได้คำตอบ

ทีนี้พอ $4\ 9$ ทำไม่ได้เราก็แค่กลับไปหา $2\ 2\ 9$ ดูว่าแปลงเป็นอย่างอื่นต่อได้ไหม แล้วก็ลองในรูปแบบอื่นๆต่อไปเรื่อยๆ

แล้วถ้า $2\ 2\ 9$ ก็ยังไม่ได้อีก ก็ย้อนกลับไปหา $3\ 2\ 5\ 9$ แล้วดูวิธีอื่นๆเอา

แล้วมันแปลว่าอะไรล่ะ?

ไม่ว่าจะเป็น $2\ 2\ 9$ หรือ $4\ 9$ หรือ $3\ 2\ 5\ 9$ มันก็เป็นเหมือน สถานะๆนึง ที่เกมที่เริ่มต้นจาก $3\ 2\ 5\ 9$ สามารถทำได้ ดังนั้นเขาจะใช้คำว่า State ในการแทนสถานะที่เกิดขึ้นได้ทั้งหมด

และใช้คำว่า การกระทำ หรือ Action แทนการกระทำที่เกิดขึ้นระหว่าง State หรือก็คือที่เราหยิบเลขสองตัวมาบวกลบคูณหารกันนั่นแหละ

แล้วถ้าเราเอา State และ Action ที่เกิดขึ้นได้ทั้งหมดมาต่อกันก็จะได้เป็นกราฟที่เรียกว่า State-Space Graph และสิ่งที่เราต้องหาก็แค่ว่าจะโยงเส้นเชื่อมจาก State แรกสุด ไปหา $24$ ได้ยังไง

State-Space Search

พอวาดมันออกมาเป็นกราฟเนี่ย สิ่งที่เราทำได้ก็คือใช้ทฤษฎีกราฟมาแก้ไงล่ะ ซึ่งหลักๆที่เริ่มมาเลยก็ทำได้สองแบบคือ Depth-First Search กับ Breadth-First Search

ในส่วนของ Depth-First Search ที่ได้ยกตัวอย่างไปแล้วก่อนหน้านี้ ก็ยังเหมือนเดิมแหละ ก็คือเห็นว่า Action ไหนทำได้ ณ State นั้นๆ ก็ลองทำไปเลยถ้ามันไม่ถึง 24 (สถานะที่ต้องการ)ก็ย้อนกลับไปหา State ก่อนหน้านี้แล้วก็ทำไปเรื่อยๆ

ซึ่งลักษณะการลงไปใน State-Space Graph ก็จะได้แนวๆนี้

แต่ถ้าเราคิดอีกแบบนึงว่า เราลองดูก่อนว่าจาก State เริ่มต้นเนี่ย คิดทุกวิธีเลยว่าเราทำอะไรบ้างก่อน แล้วค่อยๆลองขยายออกไปเรื่อยๆ อย่างเช่น

จาก $3\ 2\ 5\ 9$ เราก็ลองแปลงมันเป็น $2\ 2\ 9$, $1\ 5\ 9$, $2\ 5\ 6$ ไปเรื่อยๆจนครบทุกแบบ แล้วถ้ามันยังไม่ได้ 24 สักตัว ก็เอาแบบที่ได้มาใหม่เนี่ย มาลองต่อไปเรื่อยๆจนกว่าจะได้ 24

วิธีแบบนี้จะเรียกว่า Breadth-First Search

ที่พอวาดเป็นกราฟก็จะได้ลักษณะแนวๆนี้เลย

ซึ่งสังเกตได้อย่างนึงคือทั้งสองแบบต้องคิดหลาย State มาก แททบจะลงไปดูเกือบทุก State เลยก็ว่าได้

แต่ลองคิดเล่นๆดูนะ พอเราเล่นเกม 24 ไปเรื่อยๆ เราจะเริ่มมีความรู้สึกว่า “เลขชุดนี้น่าจะทำได้/น่าจะทำไม่ได้แฮะ” แล้วทำไมเราต้องไปคิดเลขชุดที่มันไม่น่าจะทำได้ด้วยล่ะ?

อย่างเช่นว่า เราได้ State นึงมาที่เลขมันเป็นจำนวนเฉพาะที่คำนวณยากๆหน่อย แล้วเหลือเลขให้ใช้ไม่กี่ตัวแล้วจะทำให้มันกลายเป็น $24$ มันก็ยาก ไม่น่าจะทำได้ งั้นไม่คิดต่อเลยแล้วกัน

หรือแบบอื่นเช่น เราได้ $3$ มาแล้ว เอาเลขที่เหลือให้ได้ $8$ ก็จะได้คำตอบเลย เราก็จะทุ่มการคำนวณไปกับการแปลงเลขที่เหลือให้ได้ $8$ แทนที่จะมาลองสนใจเลข $3$ เผื่อเอาไปทำอย่างอื่นได้

ฮิวริสติก (Heuristic)

ตัวอย่างพวกนี้เราเรียกมันว่า Heuristic ซึ่งเป็นฟังก์ชัน หรือแพทเทิร์นที่ใช้วัดความน่าจะเป็นในการไปหา State ที่ต้องการ

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

อย่างในรูปจะแทน State Space graph ของ $3\ 2\ 5\ 9$ ที่ชี้ให้เห็นว่า ลองไปทาง $3\ 2\ 4$ แล้วไปหา $3\ 8$ ดีกว่า

แต่ถึงอย่างนั้นมันก็ไม่ได้การันตีว่าคำตอบจะอยู่ในเส้นที่ Heuristic เลือกอ่ะนะ ถ้ามันไม่ได้ก็ยังต้องกลับออกไปลองเส้นอื่นๆอยู่ดี

ส่งท้าย

ตัว State-Space Graph และวิธีการหาคำตอบ (State-Space Search) เนี่ยเป็นพื้นฐานของวิชา AI เลย ก็คือมันจะใช้ตอนที่ดูว่าทำ Action ไหนจะได้ผลลัพธ์ออกมาดีที่สุดในขณะนั้น จริงๆแล้วมันมีหลายแบบมาก บางอย่างอาจจะไม่ได้มี State สิ้นสุดที่ชัดเจนก็ได้ แต่เป็นว่า State ไหนมีคะแนน”ความดี” มากกว่ากันอะไรประมาณนั้น ซึ่งมันก็เอามาประยุกค์ใช้กับการทำโปรแกรมที่มีตัวเลือกการกระทำค่อนข้างจำกัดเช่น การทำ bot ในเกม เป็นต้น

แต่ถ้าถามว่านี่เกี่ยวกับ LLM ไหมก็ไม่นะ …คนละเรื่องกันเลยนะฮะ 😆

ลิงก์

เว็บเจนโจทย์เกม 24

https://www.kruploy.com/game24/

มีคนอธิบายเพิ่มเรื่อง BFS กับ DFS เพิ่มใน Medium ไปอ่านกันได้

https://medium.com/@pagongatchalee/state-space-search-%E0%B8%9E%E0%B8%B7%E0%B9%89%E0%B8%99%E0%B8%90%E0%B8%B2%E0%B8%99%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B9%81%E0%B8%81%E0%B9%89%E0%B8%9B%E0%B8%B1%E0%B8%8D%E0%B8%AB%E0%B8%B2%E0%B8%AA%E0%B8%B3%E0%B8%84%E0%B8%B1%E0%B8%8D%E0%B9%83%E0%B8%99-ai-885ec84ac000