คลังเก็บป้ายกำกับ: minimax

เล่น OX กัน

minimax

เผอิญค้นไปเจอรูปนี้ในเครื่อง 🙂 หยิมมาแปะไว้บนบล็อกกันหาย

เคยมั้ยครับ? เล่นเกมแล้วสงสัยว่า คอมมันคิดยังไงนะ… ผมเคยเล่นเกมต่อจุดแล้วแพ้มันตลอดเลย (เกมที่ใครต่อจุด 5 จุดเป็นเส้นตรงได้ก่อนชนะ)

พอไปเข้าค่าย อาจารย์ก็ให้ลองเขียนเกม OX ขึ้นมา ให้คอมคิดเองได้บนตาราง 3×3 แล้วเราก็ WOW!!

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

ไม่แน่ใจว่าน้องฟังเข้าใจรึเปล่า แต่ก็เห็นเขียนออกมาได้แฮะ 😀

เกม OX: ใครเรียง O หรือ X ได้ครบ 3 ในแนวตั้ง แนวนอน หรือทแยงมุมได้ก่อนเป็นผู้ชนะ

ภาพข้างบนอธิบายวิธีคิดของ คอม กับ คน(จำลอง) ในแต่ละตาครับ

คอม จะลองลงในช่องว่างที่เหลือ แต่ละช่อง และตัดสินใจเลือกว่า ลงช่องไหนแล้วทำให้ตัวเองชนะได้
คน จะลองลงในช่องว่างที่เหลือ แต่ละช่อง และพยายามเลือกว่า ลงช่องไหนแล้วทำให้ตัวเองชนะได้

ถ้าการลงครั้งนั้น ยังไม่รู้ว่าผลจะออกมาเป็นยังไง ก็คิดต่อไปจนกว่าจะจบเกมส์… คิดลึกลงไปเรื่อยๆ ตาม Pseudocode นี้

เกม OX ที่มีตารางขนาด 3×3 เราสามารถคิดรูปแบบที่เป็นไปได้จนจบเกมส์ได้…

แต่เกมส์ที่ซับซ้อนขึ้นเช่น OX ขนาด 4×4 (คอมคิดนานหน่อย) หรือหมากรุกไทย หมากรุกฝรั่ง

โปรแกรมอาจไม่สามารถคิดล่วงหน้าไปจนจบได้… เพราะรูปแบบที่เป็นไปได้เยอะมากกกก

คนเขียนโปรแกรมเลยต้องตัดสินใจว่าจะคิดล่วงหน้าไปกี่ตา… แล้ววัดว่า กระดานหมากรุกนั้น คอมหรือคนมีโอกาสชนะ/แพ้มากน้อยแค่ไหน 🙂

Advertisements