-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
218 lines (209 loc) · 13.2 KB
/
index.html
File metadata and controls
218 lines (209 loc) · 13.2 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
<!DOCTYPE html>
<html>
<head>
<title>Sliding Tile Puzzle Solver</title>
<meta charset="utf-8">
<link rel="stylesheet" href="main.css">
<link rel="icon" type="image/png" sizes="32x32" href="favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="favicon-16x16.png">
<meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
<!-- Bootstrap -->
<link href="https://cdn.jsdelivr.net/npm/bootstrap@5.0.2/dist/css/bootstrap.min.css" rel="stylesheet" integrity="sha384-EVSTQN3/azprG1Anm3QDgpJLIm9Nao0Yz1ztcQTwFspd3yD65VohhpuuCOmLASjC" crossorigin="anonymous">
<!-- Mathjax -->
<script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.7/MathJax.js?config=TeX-MML-AM_CHTML"> </script>
</head>
<body class="bg-light">
<header>
<div class="container">
<div class="jumbotron">
<div class="row">
<div class="col-sm-11 offset-sm-1">
<h1>Sliding Tile Puzzle Solver</h1>
<h5>Interactive demonstration of various search algorithms, including BFS, DFS, Greedy BFS, and A*.</h5>
</div>
</div>
</div>
</header>
<div class="bg-light" id="main_body">
<div class="container" id="demo_content">
<div class="row">
<div class="col-sm-8">
<table id="display_table">
<tbody>
</tbody>
</table>
</div>
<div class="col-sm-4">
<form onsubmit="return false;">
<button type="button" id="new_board">Create Board</button>
<label for="size">of size:</label>
<select name="size" id="size">
<option value="2">4</option>
<option value="3" selected>9</option>
<option value="4">16</option>
<option value="5">25</option>
</select>
<label for="scramble">and</label>
<button name="scramble" type="button" id="scramble">Scramble</button>
</form>
<br>
<form>
<button type="button" id="solve" disabled>Solve</button>
<label for="search_method">using: </label>
<select name="search_method" id="search_method">
<option hidden>Select a search algorithm</option>
<option value="bfs">Breadth-First Search</option>
<option value="dfs">Depth-First Search</option>
<option value="greedy">Greedy BFS</option>
<option value="astar">A* Search</option>
</select>
<button type="checkbox" id="cancel" class="original" disabled>Cancel</button>
<br>
<form>
<div id="heuristic_div" style="display: none;" >
<label for="heuristic">with</label>
<select name="heuristic" id="heuristic">
<option hidden value="">Select a heuristic</option>
<option value="wrong"># of Misplaced Tiles</option>
<option value="manhattan">Sum of Manhattan Distances</option>
</select>
<button type="checkbox" id="hidden_cancel" class="hidden" disabled>Cancel</button>
</div>
<form>
<label for="visualize">
<input type="checkbox" id="visualize" name="visualize" title="WARNING: Will significantly slow down search time.">
<span>Visualize search algorithm?</span></label>
</form>
<hr>
<div id="nodes_expanded_label" class="search_info_labels">
Search nodes expanded:
<br>
<center>
<span id="nodes_expanded">0</span>
</center>
</div>
<div id="solution_container" class="search_info_labels">
Solution:
<div id="solution">
</div>
</div>
</div>
</div>
</div>
<br>
<br>
<br>
<div class="container" id="about">
<div class="row">
<h1>About</h1>
<hr>
<h4>Introduction</h4>
<p class="to_be_continued">
The 8-puzzle, 15-puzzle, and other variations of sliding tile puzzles are classic examples of problems that can be solved using search techniques, even
being mentioned in AIMA's section on standardized problems for search techniques.
</p>
<p>
This demo is intended to be a tool to illustrate the differences in performance of various search algorithms. The board itself can be controlled either by clicking the tile you want to move the empty square,
or by pushing the arrow/WASD key corresponding to the direction of how you want to move the (unique) piece available to be moved in that direction, if one exists.
</p>
<h4>Search Methods</h4>
<p>
This demonstration includes two non-heuristic methods (breadth-first and depth-first search), along with
two heuristic search methods (greedy breadth-first and A* search), with two heuristics for each.
It also keeps track of how many search nodes the algorithm needed to expand before finding its solution.
Thus, by applying different search methods to the same starting state, one can get an informal sense of
how effective these search variations are.
</p>
<h4>Heuristics</h4>
<p>
The two heuristics included are the number-of-misplaced-tiles and and the Manhattan-distance heuristics.
In this application of heuristic search, these heuristics guess how many more moves might be required in the solution.
The number-of-misplaced-tiles heuristic, as implied by the name, assigns to each state in consideration the number of tiles out of place.
The Manhattan-distance heuristic assigns to each state the sum of the Manhattan distances of each tile from its correct location.
I claim (but you can use the demo above to convince yourself!) that the Manhattan distance heuristic tends to find a solution faster
than number-of-misplaced-tiles, since, for admissible heuristics (more on that in the next paragraph), a heuristic that on average
assigns larger values to states than another heuristic tends to find an optimal solution after expanding fewer nodes.
It is clear that the value assigned to a state by the Manhattan distance is always at least that assigned by the
number-of-misplaced-tiles heuristics.
</p>
<h4>Comparison of Outputs</h4>
<p>
Note that these search algorithms will not all find the same solutions.
In particular, depth-first search and greedy BFS, are both non-optimal in that they are not guaranteed to
return the best solution (i.e, the one requiring the fewest moves). One can observe through experimentation that
DFS, in particular, can often result in solutions that are orders of magnitude larger in length than that of the optimal solution.
A* is optimal so long as the heuristic is admissible, which means that the true number of
moves away from the optimal solution from that state is never more than the guess made by our heuristic.
Our two heuristics are admissible because they both solved relaxed versions of the sliding tile problem.
To be precise, the number of misplaced tiles is equivalent to the path cost of a version of the problem in which any
tile can be put in its correct place in one move; the Manhattan distance heuristic is equivalent to the path cost of a version of the problem
in which tiles can overlap (i.e, multiple tiles can be placed in one location).
</p>
<h4>Technical Limitations</h4>
<p>
Because sets in JS compare objects by reference and not element-wise equality, for the search algorithm to remember which states have been visited,
each state that is explored has to be converted to a string. This significantly slows down execution.
Due to this slowness, a search will automatically stop if 300,000 nodes have been expanded without finding a solution (as
this is roughly after how much time I lose patience waiting for a solution).
Given this cap, how likely is it that a solution is found? We can get a sense of it by considering the ratio of the maximum number of search nodes
we allow ourselves to visit to the total number of unique states in the search space, as in the following chart:
</p>
<table id="search_size_table">
<tr>
<th>Board size</th>
<th>Size of search space</th>
<th>Ratio of max nodes to the size of the search space</th>
</tr>
<tr>
<td>\( n \) <br> <span class="smaller_text">\( (n\geq 4, \sqrt{n} \in \mathbb{N})\)</span></td>
<td>\( \frac{n!}{2} \)</td>
<td>\( \frac{300{,}000}{\frac{n!}{2}} \)</td>
</tr>
<tr>
<td>\( 4 \)</td>
<td>\( 12 \)</td>
<td>\( >1 \)</td>
</tr>
<tr>
<td>\( 9 \)</td>
<td>\( 181{,}440 \)</td>
<td>\( >1 \)</td>
</tr>
<tr>
<td>\( 16 \)</td>
<td>\( 10{,}461{,}394{,}944{,}000 \)</td>
<td>\( 0.000000028676863994324312 \)</td>
</tr>
<tr>
<td>\( 25 \)</td>
<td>\( 7{,}755{,}605{,}021{,}665{,}493{,}000{,}000{,}000 \)</td>
<td>\( 0.00000000000000000003868170170630684 \)</td>
</tr>
<table>
<br>
<p>
From this chart, we can see that the boards of sizes 4 and 9 will always be solved, but a solution should almost never be found for the boards of sizes 16 and 25.
However, as one can gleam from playing around with boards of size 16, A* with the Manhattan heuristic can solve boards of size 16 with surprising frequency, a
testament to its intelligence in deciding in which order to check states!
</p>
<h4>Acknowledgments</h4>
<ul>
<li>Brian Scassellati's CPSC 475 (Spring 2021)</li>
<li>Russell, Stuart J., and Peter Norvig. Artificial Intelligence: A Modern Approach. Pearson, 2020. </li>
</ul>
</div>
</div>
<footer>
<br>
<p><b>Made by Evan Gerritz, 2021</b></p>
</footer>
</div>
<!-- Execute JS - order here matters for dependencies!-->
<script src="node_modules/mathjs/lib/browser/math.js"></script>
<script type="text/javascript" src="util.js"></script>
<script type="text/javascript" src="heuristics.js"></script>
<script type="text/javascript" src="search.js"></script>
<script type="text/javascript" src="game.js"></script>
<script type="text/javascript" src="main.js"></script>
</body>
</html>