State Space Search

Tic‑Tac‑Toe — State‑space search (Bengali + English mix)

• State (স্টেট): 3×3 board configuration, each cell ∈ {X, O, _}.
• Initial state (প্রাথমিক স্টেট): empty board (সব ঘর খালি).
• Actions / Operators (অ্যাকশন): place X or O in any empty cell (turn‑based) — নির্ধারিত গেম টার্ন অনুসারে।
• Successor function (সাকসেসর): current state থেকে প্রতিটি empty cell‑এ একটি নতুন state তৈরি করে যেখানে সেই সেলে current player এর মার্ক বসে।
• Goal test (গোল টেস্ট): কোন state এ তিনটি একই মার্ক সারিতে/স্তম্ভে/ডায়াগোনালে আছে (win) বা সব ঘর ভর্তি হলে draw।
• Path / Solution (পাথ/সমাধান): sequence of moves leading from initial state to a terminal state (win/lose/draw) — এই sequence গেমের history।

Example (short walkthrough):

1. Initial:

---

---

---

2. X plays center → successor:

---

_ X _

---

3. O plays corner → successor:
   O _ _
   _ X _

---

4. X plays corner → …
   Continue until terminal state (win/draw).

Search algorithms use:

• Minimax (with game tree traversal) to choose optimal moves — maximize X’s utility, minimize O’s.
• Alpha‑beta pruning to prune branches and speed up.
• State space size: ≤ 3^9 possible boards, but legal game states far fewer due to move order.

Key points (সংক্ষিপ্ত):

• State = board configuration.
• Actions = legal moves (place mark).
• Goal = win/lose/draw terminal state.
• Use Minimax/Alpha‑beta for optimal play.