## 🔹 What is Heuristic Search?
**Heuristic Search** মানে হলো এমন একটা search technique যেটা **“educated guess”** বা **“rule-of-thumb”** ব্যবহার করে goal-এর দিকে দ্রুত এগোয়।
👉 মানে, brute-force এর মতো সব state check না করে, একটা **heuristic function `h(n)`** ব্যবহার করে বোঝা হয় কোনটা “better” move হতে পারে।
—
## 🎯 Tic-Tac-Toe Game Goal
* দুইজন player থাকে: **X** এবং **O**
* Board: 3×3 grid
* **Goal:** একটানা (row, column, বা diagonal)-এ তিনটা mark পাওয়া।
—
## ⚙️ Applying Heuristic Search in Tic-Tac-Toe
ধরা যাক আমাদের AI player হলো **X** এবং human player হলো **O**।
AI যেন smart ভাবে move নিতে পারে, তার জন্য একটা **heuristic function** define করা হবে।
—
### 🔸 Step 1: Define Heuristic Function
একটা simple heuristic হতে পারে —
“`
h(board) = (number of lines where X can still win) – (number of lines where O can still win)
“`
👉 এখানে “line” মানে row, column বা diagonal।
যে line-এ X আর O দুজনেই আছে, সেই line-টা **blocked**, কেউ জিততে পারবে না।
—
### 🔸 Step 2: Example Board
ধরা যাক boardটা এমন —
“`
X | O | X
———
O | X |
———
| | O
“`
এখন আমরা **X** player-এর জন্য heuristic value বের করব।
—
### 🔸 Step 3: Check All 8 Lines
| Line Type | Cells | কে জিততে পারে |
| ———— | ———– | —————– |
| Row 1 | X, O, X | Blocked |
| Row 2 | O, X, _ | Blocked |
| Row 3 | _, _, O | O can win |
| Col 1 | X, O, _ | Blocked |
| Col 2 | O, X, _ | Blocked |
| Col 3 | X, _, O | Blocked |
| Diagonal 1 | X, X, O | Blocked |
| Diagonal 2 | X, X, _ | X can win |
✅ তাহলে X-এর জন্য possible line = 1
✅ O-এর জন্য possible line = 1
“`
h(board) = 1 (for X) – 1 (for O) = 0
“`
📊 মানে এই position টি balanced — কেউ clear advantage-এ নেই।
### 🔸 Step 4: Use Heuristic in Search
AI এখন তার possible সব move simulate করবে,
আর প্রতিটার জন্য `h(board)` calculate করবে।
যে move-এর heuristic value **সবচেয়ে বেশি**, সেটাই choose করবে।
👉 এতে 9! possible state check করতে হয় না — অনেক faster হয়।
—
### 🔸 Step 5: Example Decision
**Move A:** X plays (3,2)
“`
X | O | X
O | X |
| X | O
“`
এখানে X diagonal-এ জিতে গেছে → ✅ Winning state → `h = +∞`
**Move B:** X plays (2,3)
“`
X | O | X
O | X | X
| | O
“`
এখনও জেতেনি → `h = +1`
👉 তাই AI choose করবে **Move A** কারণ এটা maximum heuristic value দেয়।
## 🤖 Simple Heuristic Search Algorithm
“`python
def BestMove(board):
moves = all_possible_moves(board, ‘X’)
best_score = -float(‘inf’)
best_move = None
for move in moves:
new_board = apply_move(board, move, ‘X’)
score = heuristic(new_board)
if score > best_score:
best_score = score
best_move = move
return best_move
“`