เมื่อทำแลบนี้เสร็จสิ้น นักศึกษาจะสามารถ:
Minimax เป็น Algorithm สำหรับการตัดสินใจในเกมแบบ Two-Player Zero-Sum Game โดยมีหลักการดังนี้:
function minimax(node, depth, isMaximizingPlayer):
if depth == 0 or node is terminal:
return evaluate(node)
if isMaximizingPlayer:
maxEval = -∞
for each child of node:
eval = minimax(child, depth-1, false)
maxEval = max(maxEval, eval)
return maxEval
else:
minEval = +∞
for each child of node:
eval = minimax(child, depth-1, true)
minEval = min(minEval, eval)
return minEval
Alpha-Beta Pruning เป็นเทคนิคการ Optimize Minimax โดยการตัด Branch ที่ไม่จำเป็นต้องสำรวจออก:
function alphabeta(node, depth, α, β, isMaximizingPlayer):
if depth == 0 or node is terminal:
return evaluate(node)
if isMaximizingPlayer:
maxEval = -∞
for each child of node:
eval = alphabeta(child, depth-1, α, β, false)
maxEval = max(maxEval, eval)
α = max(α, eval)
if β ≤ α:
break // Beta cutoff
return maxEval
else:
minEval = +∞
for each child of node:
eval = alphabeta(child, depth-1, α, β, true)
minEval = min(minEval, eval)
β = min(β, eval)
if β ≤ α:
break // Alpha cutoff
return minEval
| สถานะ | คะแนน |
|---|---|
| AI ชนะ | +10 |
| มนุษย์ชนะ | -10 |
| เสมอ | 0 |
evaluate() สำหรับประเมินคะแนนของสถานะเกมminimax() ตาม Pseudocode ที่ให้ไว้findBestMove() เพื่อหา Move ที่ดีที่สุดสำหรับ AIminimaxAlphaBeta() โดยเพิ่ม Alpha-Beta PruningfindBestMoveAlphaBeta()| รายการ | รายละเอียด |
|---|---|
| ขนาดกระดาน | 3 × 3 |
| ผู้เล่น | มนุษย์ vs คอมพิวเตอร์ (AI) |
| สัญลักษณ์ | X และ O |
| ผู้เริ่มก่อน | ให้ผู้ใช้เลือกได้ |
ตำแหน่งบนกระดาน: ใช้ระบบพิกัด (row, col) โดย row และ col มีค่า 0-2
(0,0) | (0,1) | (0,2)
------+-------+------
(1,0) | (1,1) | (1,2)
------+-------+------
(2,0) | (2,1) | (2,2)
หรือ ใช้ระบบหมายเลข 1-9
1 | 2 | 3
---+---+---
4 | 5 | 6
---+---+---
7 | 8 | 9
ต้องมีการตรวจสอบ Input ว่าถูกต้องและตำแหน่งนั้นว่างอยู่
โปรแกรมต้องมีฟังก์ชันอย่างน้อยดังต่อไปนี้:
# ฟังก์ชันพื้นฐาน
def print_board(board) # แสดงกระดาน
def check_winner(board) # ตรวจสอบผู้ชนะ
def is_draw(board) # ตรวจสอบเสมอ
def is_game_over(board) # ตรวจสอบเกมจบ
def get_available_moves(board) # หาตำแหน่งที่ว่าง
def make_move(board, row, col, player) # ลงหมาก
# ฟังก์ชัน AI
def evaluate(board) # ประเมินคะแนน
def minimax(board, depth, is_max) # Minimax Algorithm
def minimax_alpha_beta(board, depth, alpha, beta, is_max) # Alpha-Beta
def find_best_move(board, use_alpha_beta=False) # หา Move ที่ดีที่สุด
============================================
TIC-TAC-TOE with AI (Minimax)
============================================
Select your symbol:
1. X (play first)
2. O (play second)
Enter choice (1 or 2): 1
Select AI algorithm:
1. Minimax
2. Minimax with Alpha-Beta Pruning
Enter choice (1 or 2): 2
You are X, AI is O
You play first!
Current board:
| |
1 | 2 | 3
_____|_____|_____
| |
4 | 5 | 6
_____|_____|_____
| |
7 | 8 | 9
| |
Your turn (X). Enter position (1-9): 5
Your move:
| |
1 | 2 | 3
_____|_____|_____
| |
4 | X | 6
_____|_____|_____
| |
7 | 8 | 9
| |
AI is thinking...
[Alpha-Beta] Nodes explored: 2320
[Alpha-Beta] Pruned branches: 1847
[Alpha-Beta] Time: 0.015 sec
AI plays position 1:
| |
O | 2 | 3
_____|_____|_____
| |
4 | X | 6
_____|_____|_____
| |
7 | 8 | 9
| |
Your turn (X). Enter position (1-9): 9
Current board:
| |
O | X | 3
_____|_____|_____
| |
4 | X | 6
_____|_____|_____
| |
7 | O | X
| |
Your turn (X). Enter position (1-9): 5
Error: Position 5 is already taken! Try again.
Your turn (X). Enter position (1-9): 10
Error: Invalid input! Please enter a number between 1-9.
Your turn (X). Enter position (1-9): abc
Error: Invalid input! Please enter a number between 1-9.
Your turn (X). Enter position (1-9): 3
AI plays position 7:
| |
O | X | X
_____|_____|_____
| |
4 | O | 6
_____|_____|_____
| |
O | 8 | X
| |
============================================
GAME OVER - AI WINS!
============================================
Game Statistics:
- Total moves: 7
- AI Algorithm: Alpha-Beta Pruning
- Total nodes explored by AI: 8,547
- Total branches pruned: 6,234
- Average time per AI move: 0.023 sec
Play again? (y/n):
AI plays position 8:
| |
X | O | X
_____|_____|_____
| |
X | X | O
_____|_____|_____
| |
O | O | X
| |
============================================
GAME OVER - IT'S A DRAW!
============================================
Game Statistics:
- Total moves: 9
- AI Algorithm: Minimax (without pruning)
- Total nodes explored by AI: 45,623
- Average time per AI move: 0.156 sec
Play again? (y/n):
============================================
ALGORITHM COMPARISON MODE
============================================
Running same game state with both algorithms...
Board state:
| |
X | 2 | 3
_____|_____|_____
| |
4 | O | 6
_____|_____|_____
| |
7 | 8 | 9
| |
Finding best move for O...
+------------------+-----------+---------------+----------+
| Algorithm | Best Move | Nodes Explored| Time(ms) |
+------------------+-----------+---------------+----------+
| Minimax | 3 | 16,167 | 89.2 |
| Alpha-Beta | 3 | 2,451 | 12.4 |
+------------------+-----------+---------------+----------+
| Reduction | - | 84.84% | 86.10% |
+------------------+-----------+---------------+----------+
Both algorithms found the same optimal move!
evaluate() ก่อนว่าให้คะแนนถูกต้องcheck_winner() กับทุกรูปแบบการชนะ (8 รูปแบบ)# Test Case 1: AI ควรป้องกันการแพ้
X | X | _ AI (O) ต้องลงช่อง 3
_ | O | _
_ | _ | _
# Test Case 2: AI ควรเลือกชนะ
O | X | X AI (O) ต้องลงช่อง 4 เพื่อชนะ
_ | O | _
X | _ | _
# Test Case 3: กระดานว่าง
_ | _ | _ AI ควรลงมุมหรือกลาง
_ | _ | _
_ | _ | _