เกม OX ด้วย Minimax

Minimax คือวิธีที่โปรแกรมเล่นเกมใช้เลือกตาเดิน: สมมติว่าผู้เล่นทั้งสองเล่นได้สมบูรณ์แบบ ให้คะแนนทุกเกมที่จบแล้ว แล้วส่งคะแนนขึ้นไปตามต้นไม้เกม ผู้เล่นที่ถึงตาจะเลือกลูกที่ได้คะแนนสูงสุดสำหรับตัวเอง

กระดานเป็นสตริง 9 ตัวอักษรที่อ่านทีละแถว (index 0-8) ประกอบด้วย "X", "O" หรือ "." สำหรับช่องว่าง X เดินก่อนเสมอ ดังนั้นเป็นตาของ X เมื่อทั้งสองฝ่ายมีจำนวนเครื่องหมายเท่ากัน มิฉะนั้นเป็นตาของ O

ให้คะแนนเกมที่จบแล้วจากมุมมองของผู้เล่นที่ถึงตา: +1 ถ้าชนะ 0 ถ้าเสมอ -1 ถ้าแพ้ คืนช่องว่างที่ตาเดินนั้นได้คะแนน minimax ดีที่สุด ถ้ามีหลายช่องดีเท่ากัน ให้คืน index ที่น้อยที่สุด

จง implement best_move(board)

อินพุต

board: ตำแหน่งที่ถูกต้อง ยังไม่มีใครชนะ และมีช่องว่างอย่างน้อยหนึ่งช่อง

เอาต์พุต

คืน index (0-8) ของตาเดินที่ดีที่สุด

เงื่อนไข

board มี 9 ตัวอักษรพอดี แต่ละตัวคือ X, O หรือ .

ตำแหน่งนี้เกิดขึ้นได้ในเกมจริง ยังไม่มีใครชนะ และมีช่องว่างอย่างน้อยหนึ่งช่อง

ตัวอย่าง

อินพุต:
board = "XX.OO...."

ผลลัพธ์ที่คาดหวัง:
expected = 2

อินพุต:
std::string board = "XX.OO....";

ผลลัพธ์ที่คาดหวัง:
long long expected = 2;

อินพุต:
string board = "XX.OO....";

ผลลัพธ์ที่คาดหวัง:
long expected = 2;

อินพุต:
board = "X..OO...X"

ผลลัพธ์ที่คาดหวัง:
expected = 5

อินพุต:
std::string board = "X..OO...X";

ผลลัพธ์ที่คาดหวัง:
long long expected = 5;

อินพุต:
string board = "X..OO...X";

ผลลัพธ์ที่คาดหวัง:
long expected = 5;

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

• Russell and Norvig, Artificial Intelligence: A Modern Approach
• UC Berkeley CS188, Introduction to Artificial Intelligence