# Is there a "most intelligent" search method?

> A CS51 project by Victoria Gong and Shawn Shivdat

**Contents**
[ToC]

## Introduction
Solving puzzles, or more specifically, identifying a path to achieve a desired goal state is a hallmark of human intelligence and a central task in search algorithms. The purpose of our project is to assess search algorithms which begin with an initial state and determine a move sequence to reach a desired state.

Identifying the highest performing, or "most intelligent" search methods across different input types is important because implementing the correct search algorithm for a given input type could save time and improve efficiency, especially in solving large, complex problems. In addition, certain input types could cause a search method to consume unfeasible amounts of time, making them effectively useless for certain input types. Knowing the best usage of specific search algorithms for a given context in advance improves efficiency and saves valuable time from being wasted.

Our project involves testing three search algorithms which differ in underlying methodology. Depth-first search (DFS) explores trees in a last-in, first-out method, while Breadth-first search (BFS) explores trees in a first-in, first-out method operating using a queue list. Fast breadth-first search (FBFS) implements an improved methodology of BFS using two stacks. We test these search methods in two types of puzzles: tile boards and mazes.

### Hypotheses

Based on the search methodologies of DFS, BFS, FBFS, we predicted that DFS will outperform BFS and FBFS on one-dimensional tile board puzzles, and that DFS will underperform on multi-dimensional tile board puzzles, particularly for square tile boards.

In the maze puzzle, due to their breadth-first search method, BFS algorithms will provide a more move-efficient path to the goal state than DFS.

## Methods

We tested depth vs. breadth-first searching algorithms on linear and square tile puzzles of varying dimensions and mazes of increasing sizes.

Both algorithms explored a game state tree, or a graph with the possible states of the puzzle as vertices and moves as edges. For each state, they checked if it was the goal state (returning the solution if it was), then added the neighbors of that state to a "pending" (i.e. "to be visited") collection and the state itself to a "visited" set. The algorithms differed in the data structures they used to form this pending collection, however, which allowed for us to implement the last-in, first-out and first-in, first-out search methodologies.

### Last-in, First-out

Depth-first search was implemented using a **stack** for the pending collection, which visits states in a last-in, first-out order. Due to the LIFO nature of DFS, for each current state, each branch of the game tree would be fully explored before the branches of the current state's neighbors. This search method is predictably less efficient for games where each state has many neighboring states, such as chess.

### First-in, First-out

Breadth-first search was implemented using a **queue** for the pending collection, which allowed for pending states to be visited in a first-in, first-out order. Therefore, each neighboring state would be explored before any subsequent state in the search tree was visited. We also implemented a Fast BFS search algorithm by creating a FIFO **queue** with two **stacks**, with one stack representing the front of the queue and the second stack the back of the queue reversed.

### Testing Square and Rectangular Tile Game Boards

In order to test a diverse range of tile board inputs practically and efficiently, we added improved functionality to the distribution code in "experiments.ml" which allowed us to automatically generate the "target" game board configuration with only the input dimensions. This allowed us to quickly run our tests for each of the input dimensions without hard-coding the desired tile boards.

###### Figure 1: Code snippet of custom 'target' board creation function and usage

let create_board w h : board = 
  Array.init h (fun a -> 
    Array.init w (fun b ->
                     let i = a * w + b + 1 in 
                        if i = w * h then EmptyTile 
                        else Tile i)) ;;

let cDIMS = 10, 1 ;; (* initializing a 10x1 game board *)
let solved = create_board (snd cDIMS) (fst cDIMS) ;;
...

We then implemented the testing framework within a for loop, allowing us to run the data collection 10 times for each dimension automatically.

###### Figure 2: '1 by 10' example desired tile board

###### Figure 3: '3 by 3' example desired tile board
![](https://i.imgur.com/5KUXFu5.png "5by5" =220x220)

#### Failing Criteria
During testing, if an individual search algorithm remained in progress for longer than 2 minutes, we assigned that the algorithm "failed" and did not report data for those iterations. For example, if BFS remained stuck for over 2 minutes on a '5 by 5' input tile board, we did not report any data.

### Testing Mazes of Increasing Sizes
In addition to the sample tests given in "tests.ml", we specified 5 different square mazes to test during this experiment, with the expectation that performance time would increase as the maze size increased.

###### Figure 4: '5 by 5' maze example

![](https://i.imgur.com/6E7Kt4r.png "5by5_maze" =200x200)

###### Figure 5: '15 by 15' maze example

![](https://i.imgur.com/ABDS19S.png "15by15_maze" =200x200)

### Data Analysis
We collected all of the time quantities for each of the 10 iterations of the experiments. In total, we ran 8 experiments for tile board inputs and 5 experiments for maze inputs. We averaged the 10 iterations for each of the search algorithms in the experiments, and we compiled these values into figures for performance analysis.

## Results

### Tile Board Tests
We found that DFS greatly underperformed in the majority of cases against BFS and FBFS implementations. DFS performed comparably against BFS and FBFS in 'thin' tile boards, specifically in both '1 by 10' and '10 by 1' tile boards. However, our hypothesis was not validated that DFS would outperform BFS and FBFS on 'thin' tile boards.

###### Figure 6: Average Solving Time for Tile Boards (log scale)


In all of the trials for '1 by 10,' DFS performed comparably against BFS and FBFS, and DFS even outperformed BFS and FBFS by a small margin in many of the trials.

###### Table 1: Raw trial performance for '1 by 10' for all methods
| Trials | DFS | BFS | FBFS | DFS < BFS, FBFS |
|--------|-----------|-----------|-----------|-----------------|
| 1 | 0.156879 | 0.164032 | 0.16284 | TRUE |
| 2 | 0.204086 | 0.112057 | 0.155926 | FALSE |
| 3 | 0.230074 | 0.212908 | 0.228167 | FALSE |
| 4 | 0.173092 | 0.203133 | 0.204802 | TRUE |
| 5 | 0.200987 | 0.206947 | 0.210047 | TRUE |
| 6 | 0.204086 | 0.211954 | 0.221968 | TRUE |
| 7 | 0.228882 | 0.216007 | 0.217199 | FALSE |
| 8 | 0.268936 | 0.090837 | 0.094175 | FALSE |
| 9 | 0.143766 | 0.152826 | 0.159979 | TRUE |
| 10 | 0.172853 | 0.183105 | 0.185966 | TRUE |
| AVG | 0.1983641 | 0.1753806 | 0.1841069 | FALSE |

### Maze Tests

We found that DFS outperformed BFS and FBFS for all four maze dimensions we tested below '25 by 25' and performed comparably to BFS and FBS on the '25 by 25' maze.

###### Figure 7: Average Solving Time for Mazes


Further investigation revealed that the path lengths taken by DFS were much longer than those identified by FBFS. The number of states visited by DFS, however, was less than for FBFS. The most notable element that we observed here was the efficiency of the solution found by FBFS, which by minimizing the path length taken to the goal state, indicated that it was a more intelligent search method.

###### Table 2: Comparison of FBFS and DFS maze-solving performance metrics
| Maze Size | Path length (FBFS) | Path length (DFS) | Visited states (FBFS) | Visited states (DFS) |
|--|:--|:---|:--|:--|
| 5 | 8 | 16 | 21 | 21|
| 10 | 18 | 56 | 84 | 75|
| 15 | 28 | 144 | 189 | 172|
| 20 | 38 | 272 | 336 | 309|
| 25 | 48 | 440 | 525 | 486|

## Discussion

### Contextualizing Key Findings

#### Tile Board Tests
Our initial hypothesis was that DFS would outperform BFS and FBFS on one-dimensional tile boards and underperform on more square tile boards. Our experiments partially confirmed our hypothesis. Our hypothesis that DFS would underperform on multi-dimensional tile boards was correct, since DFS failed to find solutions for all square tile boards tested and took significantly longer than BFS and FBFS to find solutions for '2 by 3' and '2 by 4' tile boards. However, our hypothesis that DFS would outperform on one-dimensional tile boards was not validated, since DFS only performed comparably to BFS and FBFS on one-dimensional tile boards. While these results are not exactly what we anticipated, they are not far from our hypothesis because the only circumstances in which DFS performed comparably to BFS and FBFS in the tile board experiments were for one-dimensional tile boards, where the number of neighbors was significantly less for each state than puzzles with greater dimensions. In multi-dimensional boards, DFS significantly underperformed.

#### Maze Tests
In almost all of the maze dimensions tested, DFS consistently outperformed BFS and FBFS in search time. This is particularly interesting because DFS significantly underperformed in the tile board experiment. We found that the reason DFS performs well on mazes is because its implementation allows DFS to skip neighboring states if exploring the path from its current state leads to a favorable position, which is particularly easy to do in these "copied" mazes. On the other hand, the BFS and FBFS implementations are forced to test many more states in the maze as shown in **table 2**, due to their searching method that favors nearest neighbors. We supported this finding by analyzing the movement path for DFS and BFS cases, which are shown in the figures below, with states in the visited set taken by the search algorithm shaded in and unvisited states left unshaded. These support our hypothesis that FBFS provides a more move-efficient path to the goal state, compared to DFS. Additionally, in line with our observations in **table 2**, DFS visits less states than FBFS.

###### Figure 8: '25 by 25' DFS search pathway
![](https://i.imgur.com/8OpgUw4.png "25by25BFS" =300x300)

###### Figure 9: '25 by 25' BFS search pathway
![](https://i.imgur.com/7TaO2ay.png "25by25DFS" =300x300)

### Future Directions

#### Horizontal vs. Vertical 'Thin' Tile Boards
Our hypothesis was that DFS would outperform BFS and FBFS on thinner input matrices. While we found this to be largely true based on the average times across the trials, we observed that there were more trials in which the DFS time was not smaller than both the BFS and FBFS times in the '10 by 1' case than the '1 by 10' case. This suggests that even though DFS still performs better on average in the 'thin' input case, the higher performance of DFS over BFS and FBFS is less consistent across trials when the 'thin' input is oriented in the vertical direction instead of the horizontal direction. Future investigations could determine using larger dimensions whether DFS performance varies in a suggestive way when 'thin' inputs are oriented in the vertical versus horizontal orientations.

#### Non-Square Mazes
Due to limitations in the distribution code, we were unable to test performance differences across DFS, BFS, and FBFS between rectangular mazes and square mazes. We hypothesize that DFS would continue to outperform on more rectangular mazes.

#### Failing Criteria
For tile boards, we set the maximum time to complete a search computation to be 30 seconds. However, in the '5 by 5' and '10 by 10' cases, we even went further to allow 2 minutes for a search computation to complete. Still, multiple tests resulted in missing data, for DFS in 4 cases and for BFS and FBS in 2 cases. Future investigations should consider allowing even more time, perhaps tens of minutes to hours, to see if the computations actually complete.

## Conclusion
Our experiments confirmed our hypothesis that DFS would underperform on multi-dimensional tile boards and showed that the only DFS performance comparable to the other methods was with one-dimensional tile boards.

We also saw that DFS outperformed both BFS and FBFS in finding a path to the goal state in the maze puzzle, and we confirmed our hypothesis that BFS algorithms would find a path to the goal state that required less moves, compared to DFS.

Particularly in the maze puzzles, we saw that the solution found by a BFS algorithm was more representative of intelligent behavior because it found the shortest path to the goal state. This suggests an opportunity for optimization of search using BFS in certain use cases, since breadth-first search behavior is indeed desirable when optimizing certain real-world systems.

Overall, we achieved our goal to investigate the performance of BFS, FBFS, and DFS algorithms in different contexts in order to gain a deeper understanding for their most effective usage in practice. Since different algorithms perform better given different input types, we can conclude that the 'most intelligent' search algorithm is the one that is best suited for the scenario based on prior evidence.