-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
executable file
·222 lines (164 loc) · 9.93 KB
/
index.html
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
219
220
221
222
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Lewis Matos</title>
<meta content="TicTacToe Minimax AI" name="description">
<meta content="width=device-width, initial-scale=1" name="viewport">
<meta content="Lewis Matos" name="author">
<link href="main.css" rel="stylesheet">
<link href='http://fonts.googleapis.com/css?family=Open+Sans' rel='stylesheet' type='text/css'>
<script src="public/JS/jquery-3.2.1.min.js"></script>
<script src="public/JS/game.js"></script>
</head>
<body class="body">
<!-- Nav -->
<div id="container">
<div id="topbar">
<div id='welcome'>
MiniMax Tic Tac Toe
</div>
<div id="logodiv">
<a id="clicklogo">
<div id="roundLogo">
</div>
</a>
</div>
</div>
</div>
<!--NAV END-->
<!--TTT BOARD -->
<div id="TicTacToeBoard">
<!-- Grid system using table. Consist of 3 table rows with each row having 3 boxes. Each box has a unique id
to be able to independetly control each box on the board-->
<table class="Board">
<tr>
<td class="square" id="0" onclick="clickBox(id)">
</td>
<td class="square" id="1" onclick="clickBox(id)">
</td>
<td class="square" id="2" onclick="clickBox(id)">
</td>
</tr>
<tr>
<td class="square" id="3" onclick="clickBox(id)">
</td>
<td class="square" id="4" onclick="clickBox(id)">
</td>
<td class="square" id="5" onclick="clickBox(id)">
</td>
</tr>
<tr>
<td class="square" id="6" onclick="clickBox(id)">
</td>
<td class="square" id="7" onclick="clickBox(id)">
</td>
<td class="square" id="8" onclick="clickBox(id)">
</td>
</tr>
</table>
<div id="playerInfo">
<h3 id="gameInfo" style="text-align: center">
</h3>
<form action="" id="resetForm" method="get" name="resetForm">
<input id="reset" name="button" onclick="start()" type="button" value="ResetGame">
</form>
</div>
<div class="difficulty">
Change Difficulty Level: <select id="setLevel" onchange="setDiffRestart();">
<option value="1">
Easy
</option>
<option value="2">
Medium
</option>
<option value="6">
Difficult
</option>
</select>
</div>
</div>
<!--TTT BOARD END -->
<hr>
<div class=WordSection1>
<p class=MsoNormal style='margin-bottom:12.0pt'> </p>
<p class=MsoNormal align=center style='text-align:center'><span style='font-size:24.0pt;line-height:105%'>Tic Tac Toe with Artificial
intelligence using Minimax search algorithm.</span></p>
<p class=MsoNormal align=center style='text-align:center'><span style='font-size:22.0pt;line-height:105%'>What is Minimax?</span></p>
<p class=MsoNormal align=center style='text-align:center;;max-width:80%;margin:0 auto;'><span style='font-size:14.0pt;line-height:105%;'>Minimax is a recursive algorithm that
is used to find the most optimal move in a two player zero sum
perfect information game such as tic tac toe, connect four, checkers and chess.
Zero sum game means that the score of each player sums to 0. Let's say the first player has a score of 1 then the second player gets a score of -1. Perfect information just means that the
game doesn’t have any element of chance like Poker or Yahtzee.</span></p>
<p class=MsoNormal align=center style='text-align:center'><span style='font-size:20.0pt;line-height:105%'>How does it work?</span></p>
<p class=MsoNormal style='text-align:justify;text-indent:.5in;max-width:80%;margin:0 auto;'><span style='font-size:14.0pt;line-height:105%;'>Minimax algorithm works by looking ahead
checking all possible moves and then determining the best move to make by
a heuristic evaluation function. When you play tic tac toe before you choose a
square you try to look ahead to see if that move will lead you to a victory or
block the chance of your opponent getting a victory. You are sort of making a
search tree in your head and then traversing different paths down the tree to
find the best move to maximize your chance of winning and minimize the
opponent’s chance of winning.</span></p>
<br>
<div align=center>
<table class=MsoTable15Plain4 border=0 cellspacing=0 cellpadding=0 style='border-collapse:collapse'>
<tr>
<td width=312 valign=top style='width:233.75pt;padding:0in 5.4pt 0in 5.4pt'>
<h1><img width=600 height=471 src='public/images/image001.png' align=left hspace=12></h1>
</td>
</tr>
</table>
<br>
</div>
<p class=MsoNormal style='text-align:justify;text-indent:.5in;max-width:80%;margin:0 auto;'><span style='font-size:14.0pt;line-height:105%;'>Minimax works the same way but it can
look ahead a lot further then a human. Minimax uses a tree in which the top
level of the tree represents the maximizing player. Minimax max moves in a
depth first search. In the image below the max player is shown
as a circle and the min player (AI) is represented as a square. The leaf nodes
at the bottom of the tree is calculated by a heuristic evaluation function. For
tic tac toe I chose to represent moves that lead to a maximizing player victory
to 1 and moves that leads to a minimizing player to win -1. The algorithm is minimizing
the opponents chance of winning and maximizing it's chance of winning..
Searching all moves down a tree is achievable in tic tac toebecause the
amount of possible moves is under 300,000 but for a game like chess
it takes 10^123 known as the Shannon number. There are more moves in chess then
there are atoms 10^80 in the observable universe!</span></p>
<p class=MsoNormal align=center style='text-align:center'><span style='font-size:20.0pt;line-height:105%'>Check out this great video on Game Theory from Computerphile</span></p>
<p class=MsoNormal style='text-align:center;text-indent:.5in'><span style='font-size:14.0pt;line-height:105%'><iframe width="560" height="315" src="https://www.youtube.com/embed/5oXyibEgJr0" frameborder="0" allowfullscreen></iframe></span></p>
<p class=MsoNormal align=center style='text-align:center'><span style='font-size:20.0pt;line-height:105%'>Grab code from <a href='https://github.com/LewisMatos/MiniMaxTicTacToe'>GitHub</a></span></p>
<p class=MsoNormal align=center style='text-align:center'><span style='font-size:24.0pt;line-height:105%'> </span></p>
<p class=MsoNormal align=center style='text-align:center'> </p>
<hr>
<p class=MsoNormal align=center style='text-align:center'><span style='font-size:24.0pt;line-height:105%'>How to make Minimax more efficient.</span></p>
<p class=MsoNormal style='text-align:justify;text-indent:.5in;max-width:80%;margin:0 auto;'><span style='font-size:14.0pt;line-height:105%'>Although Minimax checks for the best
possible move it needs to check every node of the tree to find the best
possible move. Alpha-beta pruning is an algorithm that can be applied to
minimax to decrease the amount of nodes it evaluates down the search tree. For
alpha beta-pruning, Alpha represents the maximum score and beta
represents the minimum score. Alpha/Beta are both initialized with the worst
possible score for both players. We use both Alpha and Beta to prun the tree by
checking to see if alpha is greater or equal to beta.</span></p>
<p class=MsoNormal align=center style='text-align:center;text-indent:.5in'><img width=825 height=432 src=public/images/image002.png></p>
<p class=MsoNormal style='text-align:justify;text-indent:.5in'> </p>
<p class=MsoNormal style='text-align:justify;text-indent:.5in'> </p>
<p class=MsoNormal style='text-align:justify;text-indent:.5in'> </p>
<p class=MsoNormal style='text-indent:.5in'><b><span style='font-size:14.0pt;
line-height:105%'>REFERENCES & RESOURCES</span></b></p>
<p class=MsoNormal style='text-indent:.5in'><span style='font-size:14.0pt;
line-height:105%'>"Beej's Bit Bucket." Minimax. Sat. 21 April 2017.</span></p>
<p class=MsoNormal style='text-indent:.5in'><span style='font-size:14.0pt;
line-height:105%'>"CSCI 6350 Artificial Intelligence: Minimax and
Alpha-Beta Pruning Algorithms and Psuedocodes." YouTube. YouTube, n.d.
Sat. 21 April 2017.</span></p>
<p class=MsoNormal style='text-indent:.5in'><span style='font-size:14.0pt;
line-height:105%'>Wikipedia. Wikimedia Foundation, n.d. Sat. 21 April 2017.</span></p>
<p class=MsoNormal style='text-indent:.5in'><span style='font-size:14.0pt;
line-height:105%'>"An Exhaustive Explanation of Minimax, a Staple AI
Algorithm." An Exhaustive Explanation of Minimax, a Staple AI Algorithm.
N.p., n.d. Sat. 21 April 2017.</span></p>
<p class=MsoNormal style='text-align:justify;text-indent:.5in'><span style='font-size:14.0pt;line-height:105%'> </span></p>
<p class=MsoNormal style='text-align:justify;text-indent:.5in'><span style='font-size:14.0pt;line-height:105%'> </span></p>
<p class=MsoNormal style='text-align:justify;text-indent:.5in'> </p>
</div>
</body>
</html>