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):
- Initial:
- X plays center → successor:
_ X _
- O plays corner → successor:
O _ _
_ X _
- 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.