1 of 36

Graph 2: Depth First and Breadth First Search

2 of 36

Our Tic-Tac-Toe State Space

["X", "X", "O", "X", "O", "-", "O", "O", "X"]

3 of 36

["X", "-", "O", "-", "-", "-", "O", "X", "-"]

4 of 36

["X", "-", "O", "-", "-", "-", "O", "X", "-"]

5 of 36

Optimal Move Assumption

6 of 36

Optimal Move Assumption

7 of 36

Optimal Move Assumption

8 of 36

Depth First Search

There are several algorithms to transverse a tree. One of the most basic ones is a depth first search.

  • Idea: Explore the entire depth of each sub-tree before advancing to the next subtree.
  • Results in exploring deep solutions immediately.

9 of 36

Depth First Search

10 of 36

Depth First Search

11 of 36

Depth First Search

12 of 36

Depth First Search

13 of 36

Depth First Search

14 of 36

Depth First Search

15 of 36

Depth First Search

16 of 36

Depth First Search

17 of 36

Depth First Search

18 of 36

Depth First Search

19 of 36

Depth First Search

20 of 36

Depth First Search

21 of 36

Breadth First Search

Another algorithm to transverse a tree is a breadth first search.

  • Idea: Explore all of the children before your grand-children.
  • Results in a shallow search, often eliminating needs for deep dives for some state spaces.

22 of 36

Breadth First Search

1

2

3

4

5

6

7

23 of 36

Breadth First Search

1

2

3

4

5

6

7

24 of 36

Breadth First Search

1

2

3

4

5

6

7

8

25 of 36

Breadth First Search

26 of 36

Drawing the board

​

27 of 36

Drawing the board

​

width == height

height == width

28 of 36

Drawing the board

​

width/3

width/3

29 of 36

width/3

width/3

(0, 0)

30 of 36

Drawing the board

​

width/3

width/3

(0, width/3) ⇒ (width, width/3)

(0, 2*width/3) ⇒ (width, 2*width/3)

(width/3, 0) ⇒ (width/3, width)

(2*width/3, 0) ⇒ (2*width/3, width)

31 of 36

Drawing the board

​

width/3

width/3

10% padding on each side

32 of 36

Drawing the board

​

width/3

width/3

0.1*width/3

0.1*width/3

0.8*width/3

33 of 36

Drawing the board

​

width/3

width/3

0.1*width/3

0.1*width/3

0.8*width/3

34 of 36

Drawing the board

​

width/3

width/3

0.1*width/3

0.1*width/3

0.8*width/3

(0, 0)

35 of 36

Drawing the board

​

width/3

width/3

0.1*width/3

0.1*width/3

0.8*width/3

(0, 0)

(0, 0) ⇒ (0.8*width/3, 0.8*width/3)�(0, 0.8*width/3) ⇒ (0.8*width/3, 0)

36 of 36

Drawing the board

​

width/3

width/3

0.1*width/3

0.1*width/3

0.8*width/3

(0, 0)

cx: 0.4*width/3�cy: 0.4*width/3� r: 0.4*width/3