เผอิญค้นไปเจอรูปนี้ในเครื่อง 🙂 หยิมมาแปะไว้บนบล็อกกันหาย
เคยมั้ยครับ? เล่นเกมแล้วสงสัยว่า คอมมันคิดยังไงนะ… ผมเคยเล่นเกมต่อจุดแล้วแพ้มันตลอดเลย (เกมที่ใครต่อจุด 5 จุดเป็นเส้นตรงได้ก่อนชนะ)
พอไปเข้าค่าย อาจารย์ก็ให้ลองเขียนเกม OX ขึ้นมา ให้คอมคิดเองได้บนตาราง 3×3 แล้วเราก็ WOW!!
ผมได้รู้จักกับ Minimax ครั้งแรกก็ตอนเขียนโปรแกรมในค่ายหละครับ พอดีมีน้องๆ ที่โรงเรียนอยากทำ project เกมหมากรุก… ให้คอมเล่นสู้กับคนได้ เลยลองวาดๆ รูปข้างบน อธิบายให้น้องฟัง
ไม่แน่ใจว่าน้องฟังเข้าใจรึเปล่า แต่ก็เห็นเขียนออกมาได้แฮะ 😀
เกม OX: ใครเรียง O หรือ X ได้ครบ 3 ในแนวตั้ง แนวนอน หรือทแยงมุมได้ก่อนเป็นผู้ชนะ
ภาพข้างบนอธิบายวิธีคิดของ คอม กับ คน(จำลอง) ในแต่ละตาครับ
คอม จะลองลงในช่องว่างที่เหลือ แต่ละช่อง และตัดสินใจเลือกว่า ลงช่องไหนแล้วทำให้ตัวเองชนะได้
คน จะลองลงในช่องว่างที่เหลือ แต่ละช่อง และพยายามเลือกว่า ลงช่องไหนแล้วทำให้ตัวเองชนะได้
ถ้าการลงครั้งนั้น ยังไม่รู้ว่าผลจะออกมาเป็นยังไง ก็คิดต่อไปจนกว่าจะจบเกมส์… คิดลึกลงไปเรื่อยๆ ตาม Pseudocode นี้
เกม OX ที่มีตารางขนาด 3×3 เราสามารถคิดรูปแบบที่เป็นไปได้จนจบเกมส์ได้…
แต่เกมส์ที่ซับซ้อนขึ้นเช่น OX ขนาด 4×4 (คอมคิดนานหน่อย) หรือหมากรุกไทย หมากรุกฝรั่ง
โปรแกรมอาจไม่สามารถคิดล่วงหน้าไปจนจบได้… เพราะรูปแบบที่เป็นไปได้เยอะมากกกก
คนเขียนโปรแกรมเลยต้องตัดสินใจว่าจะคิดล่วงหน้าไปกี่ตา… แล้ววัดว่า กระดานหมากรุกนั้น คอมหรือคนมีโอกาสชนะ/แพ้มากน้อยแค่ไหน 🙂
nattster 