A* Search

## 🔹 What is A* Search?

**A*** (উচ্চারণঃ “A star”) হলো একটা **informed search algorithm**,

যা ব্যবহার করে দুইটা important function:

[

f(n) = g(n) + h(n)

]

👉 এখানে,

* `g(n)` = cost so far (start থেকে current state পর্যন্ত cost)

* `h(n)` = heuristic estimate (goal এ পৌঁছাতে বাকি distance বা effort এর অনুমান)

A* always selects the node যার **f(n)** value সবচেয়ে কম —

মানে যেটা সবচেয়ে promising path মনে হয়।

## 🎯 Applying A* Search in Tic Tac Toe

Tic Tac Toe-তে আমরা use করতে পারি A* logic to find **best move** for player X.

প্রতিটা move একটা **state** এবং প্রতিটা move-এর সাথে একটা **cost (g)** আর একটা **heuristic (h)** থাকবে।

### 🔸 Step 1: Define the Problem

We want to find **X-এর winning path** — অর্থাৎ এমন move sequence যাতে X জেতে।

—

### 🔸 Step 2: Define f(n), g(n), h(n)

* **g(n)** → যত move নেয়া হয়েছে (depth of the node)

* **h(n)** → কতটা কাছে আমরা জেতার (winning) অবস্থায় আছি, তার estimate

  যেমন:

  * যদি X already জিতে যায় → `h = 0`

  * যদি X-এর দুইটা mark একসাথে আছে কিন্তু তৃতীয়টা ফাঁকা → `h = 1`

  * যদি X-এর chances কম → `h = 2` বা তার বেশি

তাহলে আমরা চাই **minimum f(n)** → অর্থাৎ **কম move (g)** + **কম remaining effort (h)**।

—

### 🔸 Step 3: Example Board

ধরা যাক game state টা এমন

X	O
O	X

এখন X-এর turn.

### 🔸 Step 4: Generate Possible Moves (Successors)

Possible moves for X:

1. Move A → X plays (1,3)

X	O	X
O	X

2. Move B → X plays (3,1)

X	O
O	X
X

3. Move C → X plays (3,2)

X	O
O	X
	X

4. Move D → X plays (3,3)

X	O
O	X
		X

### 🔸 Step 5: Evaluate Each State with f(n) = g(n) + h(n)

ধরি আমরা এখন 3rd move-এ আছি → so `g(n) = 3` (3 move done by X so far)

Now estimate **h(n)** for each move:

Move	Description	g(n)	h(n)	f(n)	Comment
A-(1,3)	X has diagonal 2 chance	3	1	4	4-good
B-(3,1)	X already wins diagonally (X,O,_) → X,X,X	3	0	3	✅ Best
C-(3,2)	no immediate win	3	2	5	average
D-(3,3)	win diagonal 1 → X wins	3	0	3	✅ Best

So minimum **f(n) = 3** (Move B or D).

AI chooses one of them → **Winning move**!

### 🔸 Step 6: How A* Chooses Path

A* keeps an **Open List** (nodes yet to explore) and a **Closed List** (already explored).

Each step it:

1. Picks node with **lowest f(n)** from Open List

2. Expands its children

3. Updates Open and Closed Lists accordingly

In Tic Tac Toe, this means AI tests all possible moves, picks the one with lowest cost to win.

### 🔸 Step 7: Algorithm (Simplified)

“`python

def a_star_tictactoe(board, player):

    open_list = [board]

    g = {str(board): 0}  # move cost so far

    h = {str(board): heuristic(board, player)}  # estimated remaining

    f = {str(board): g[str(board)] + h[str(board)]}

    while open_list:

        current = min(open_list, key=lambda b: f[str(b)])

        if is_goal(current, player):

            return current  # winning board found

        open_list.remove(current)

        for move in possible_moves(current, player):

            new_board = apply_move(current, move, player)

            g[str(new_board)] = g[str(current)] + 1

            h[str(new_board)] = heuristic(new_board, player)

            f[str(new_board)] = g[str(new_board)] + h[str(new_board)]

            open_list.append(new_board)

    return None

“`

💡 এই algorithm-টা game tree explore করে

এবং সবসময় **minimum f(n)** value-এর node বেছে নেয় —

অর্থাৎ **সবচেয়ে কাছের winning path**।

## ✅ Final Summary

So, in Tic Tac Toe,

A* search evaluates every possible move with **f(n) = g + h**,

and chooses the move that brings **fastest win** (minimum total cost).

👉 সহজভাবে বললে —

**A*** হলো এমন একটা smart system,

যা ভাবে — *”Which move will take me closer to winning, in the fewest steps?”*