-
Notifications
You must be signed in to change notification settings - Fork 1
/
2048-AI.html
483 lines (457 loc) · 28.9 KB
/
2048-AI.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
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
<!DOCTYPE html>
<html lang="en">
<head>
<!-- Global site tag (gtag.js) - Google Analytics -->
<script async src="https://www.googletagmanager.com/gtag/js?id=UA-154262640-1"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag() {
dataLayer.push(arguments);
}
gtag('js', new Date());
gtag('config', 'UA-154262640-1');
</script>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>The Black Prism</title>
<meta name="description" content="some very important website">
<meta name="author" content="TheBlackPrism">
<meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
<link rel="stylesheet" href="./css/styles.css">
<link rel="stylesheet" href="css/fancybox.min.css">
<link rel="stylesheet" href="./css/gallery-style.css">
<link rel="stylesheet" href="css/magnific-popup.css">
<link href='https://fonts.googleapis.com/css?family=Nunito' rel='stylesheet' type='text/css'>
<link rel="apple-touch-icon" sizes="120x120" href="/apple-touch-icon.png">
<link rel="icon" type="image/png" sizes="32x32" href="favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="favicon-16x16.png">
<link rel="manifest" href="/site.webmanifest">
<link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5">
<meta name="msapplication-TileColor" content="#da532c">
<meta name="theme-color" content="#ffffff">
<meta property="og:title" content="The Black Prism" />
<meta property="og:url" content="https://theblackprism.ch" />
<meta property="og:image" content="https://theblackprism.ch/images/Black-Prism_Logo_V05_Black.png" />
</head>
<body>
<!-- Preloader -->
<div class="preloader d-flex align-items-center justify-content-center">
<div class="lds-ellipsis">
<div></div>
<div></div>
<div></div>
<div></div>
</div>
</div>
<!-- ##### Header Area Start ##### -->
<!-- ##### Header Area Start ##### -->
<header class="header-area">
<!-- Navbar Area -->
<div class="newsbox-main-menu">
<div class="classy-nav-container breakpoint-off">
<div class="container-fluid">
<!-- Menu -->
<nav class="classy-navbar justify-content-between" id="newsboxNav">
<!-- Nav brand -->
<a href="index.html" class="nav-brand">The Black Prism</a>
<!-- Navbar Toggler -->
<div class="classy-navbar-toggler">
<span class="navbarToggler"><span></span><span></span><span></span></span>
</div>
<!-- Menu -->
<div class="classy-menu">
<!-- Close Button -->
<div class="classycloseIcon">
<div class="cross-wrap"><span class="top"></span><span class="bottom"></span></div>
</div>
<!-- Nav Start -->
<div class="classynav">
<ul>
<li><a href="index.html">Home</a></li>
<li><a href="blogs.html">Blog</a>
<ul class="dropdown">
<li><a href="blogs.html">All Blogs</a></li>
<li><a href="AI-Lab3.html">AI Lab3</a></li>
<li><a href="AI-Lab2.html">AI Lab2</a></li>
<li><a href="AI-Lab1.html">AI Lab1</a></li>
<li><a href="2048-AI.html">Artificial Intelligence</a></li>
<li><a href="dragnet.html">CSP & Datalog</a></li>
</ul>
</li>
<li><a href="photos.html">Photos</a>
<ul class="dropdown">
<li><a href="photos.html">All Photos</a></li>
<li><a href="africa.html">Africa</a></li>
<li><a href="mountains.html">Mountains</a></li>
<li><a href="diverse.html">Diverse</a></li>
</ul>
</li>
<li><a href="https://github.com/TheBlackPrism.html">Github</a></li>
<li><a href="about.html">About</a></li>
</ul>
</div>
<!-- Nav End -->
</div>
</nav>
</div>
</div>
</div>
</header>
<!-- ##### Header Area End ##### -->
<!-- ##### Hero Area Start ##### -->
<section class="section-padding-200">
<div class="container">
<h2>Artificial Intelligence for 2048</h2>
<h4 class="subtitle">An approach to beat 2048 with AI</h4>
<h5 class="author">By Jennifer Schürch & Yves Lütjens</h5>
<div class="blogpost">
<p>The game 2048 is a hard game to beat. As there are many random variables during play, one has a hard time to implement a good algorithm for it.
We started off by implemented a heuristic algorithm and set the aim that it can reach 10'000 points in average.<br>
</p>
<h4>Heuristic</h4>
<p>Our first approach consisted of creating an algorithm which moved alternately down and right and as soon as he was stuck trying to find if the
bottom row or the lefthand row was full and move in that direction. The idea behind this "Pretty Good" algorithm was to keep the highest tile in the bottom right corner.
After a short time we realised that this strategy will not bear fruits as it's average score was around 4'000 points, so we discarded our algorithm and started over.<br>
This time we made the "Check Score" algorithm which chose the turn that would lead to the greatest score, ignoring the random tile spawn. The scoring itself was a combination of different experiences that we obtained from the previous version.
On one hand it gave penalties to moves that would lead to badly shaped boards and on the otherhand it gave bonus for same neighbours.<br>
Built on the Check Score algorithm we build the "Hierarchical" algorithm which also did look two steps in the future in every possible direction (still ignoring the random tile spawn) and assessed the board at that stage. We valued the board
by a score which was strongly depending on the position of the tiles. A better positioning of a tile lead to a higher factor. This factor will then be multiplied the value of the tile.
A good position was the closeness to the bottom right corner, and the tile in the corner itself got an additional bonus,
to force the algorithm to keep the highest value there. The board score distribution for this version looked like this:
</p>
<figure>
<a href="images/blogs/ai/board_bonus_heuristic.jpg" class="d-block photo-item" data-fancybox="gallery">
<img class="article-image-rect" src="images/blogs/ai/board_bonus_heuristic.jpg" alt="Bonus distribution heuristic" class="img-fluid">
<div class="photo-text-more">
<span class="icon icon-search">Bonus distribution Hierarchical</span>
</div>
</a>
</figure>
<p>These improvements got us way closer to our aim, overall the algorithm scored an average of 7'000 points.<br>
We further improved it by giving a neighbourbonus which we had in the Check Score algorithm, for tiles of the same value and weighted empty tiles too, so the algorithm had more interest in merging tiles.
This small tweaks finally pushed our algorithm slightly over the 10'000 points threshold.<br>
The following graphs show how the different heuristic algorithms did perform over 200 games and how they perform against the given random agent.
</p>
<table>
<caption>Comparison of the implemented heuristics</caption>
<tbody>
<tr>
<th>Algorithm Name</th>
<th>Highscore</th>
<th>Average Score</th>
<th>Highest Tile</th>
<th>Time Per Move [s]</th>
</tr>
<tr>
<td>Random Agent</td>
<td>2'960</td>
<td>1'052</td>
<td>256</td>
<td>0.010664</td>
</tr>
<tr>
<td>Pretty Good</td>
<td>8'012</td>
<td>4'121</td>
<td>512</td>
<td>0.003739</td>
</tr>
<tr>
<td>Check Score</td>
<td>17'080</td>
<td>6'975</td>
<td>1024</td>
<td>0.009889</td>
</tr>
<tr>
<td>Hierarchical Rating</td>
<td>62'800</td>
<td>14'752</td>
<td>4096</td>
<td>0.008578</td>
</tr>
</tbody>
</table>
<figure>
<div class="single-slide">
<div class="container-fluid">
<div class="row">
<div class="col-md-6">
<a href="images/blogs/ai/scores_heuristicai.png" class="d-block photo-item" data-fancybox="gallery">
<img src="images/blogs/ai/scores_heuristicai.png" alt="scores heuristic ai" class="img-fluid">
<div class="photo-text-more">
<span class="icon icon-search">Distribution of the heuristics score over 200 games</span>
</div>
</a>
</div>
<div class="col-md-6">
<a href="images/blogs/ai/highest_tiles_reached_heuristicai.png" class="d-block photo-item" data-fancybox="gallery">
<img src="images/blogs/ai/highest_tiles_reached_heuristicai.png" alt="highest reached tiles heuristic ai" class="img-fluid">
<div class="photo-text-more">
<span class="icon icon-search">Distribution of the highest reached tiles of the heuristics over 200 games</span>
</div>
</a>
</div>
</div>
</div>
</div>
</figure>
<h4>Expectimax</h4>
<p>As 2048 contains a random factor in regard of the randomly spawned 2 or 4 value tile, Expectimax is the most obvious approach to implement an AI.
We used the Hierarchicals heuristics score function (called Heuristic in the following) to value the board, as well as an adaptive depth going from depth one to depth three depending on the number of empty tiles.
This allowed us to speed up the early phase of the game, as depth 3 with our score function needed up to 20 seconds for a move, depending on the number of empty tiles after a move.
As we urged for more speed, we also implemented multiprocessing into our AI that created a process for each top level move, in order to speed it up further.
Thanks to the two mentioned measurements we achieved an average time per move of under one second.
Overall the first iteration of our AI did alot better than the heuristic, it regularly won the game and the average score increased to 30'000 points.
It was a good first step but we wanted to do better!<br>
The next thing we tried was implementing a bonus if the neighbour was half as big, so that the AI can merge more smoothly. In contrary to what we expected,
this measurement destroyed the algorithm and scored lower than the heuristic. We came up with the idea to distribute the factors like a snake and give the corner a hefty bonus, according to the following image:
</p>
<figure>
<a href="images/blogs/ai/board_bonus_searchai_heuristic.jpg" class="d-block photo-item" data-fancybox="gallery">
<img class="article-image-rect" src="images/blogs/ai/board_bonus_searchai_heuristic.jpg" alt="Bonus distribution second iteration" class="img-fluid">
<div class="photo-text-more">
<span class="icon icon-search">Bonus distribution Improved Heuristic</span>
</div>
</a>
</figure>
<p>The results showed further improvement in the average score up to 44'000 points. The problem was that the algorithm still did not stack the tiles in a perfect descending order.
Sometimes small numbers where caught in the bottom left corner which disturbed the system and lead to big problems after the 4096 tile has been reached. Therefore we came up with the Snakey variation of the heuristic
score system. In the Snakey variation we generated an array of big numbers with great distances between each other and in a descending order that would force the AI to fill up all the ranks in the bottom rows.
This approach finally was the breakthrough we where looking for!<br>
With an average score of 90'000 points it exceeded all previous implementations we made by far.
Furthermore this variant was alot faster than previous iterations as it only needs to make one
matrix multiplication instead of two for loops and multiple if statements.<br>
We tested out multiple other distributions, which we thought could work well with the same system as the Snakey.
One was a diagonal decreasing distribution of the bonuses, another one was squares, and the last one was Snakey+ which also had a neighbourbonus implemented.
At the end Snakey still was the most succesfull variation we created and if we wanted to improve it it just got worse.
The score distribution for the different versions looked as follows:
</p>
<figure>
<div class="single-slide">
<div class="container-fluid">
<div class="row">
<div class="col-md-4">
<a href="images/blogs/ai/board_bonus_searchai_snakey.jpg" class="d-block photo-item" data-fancybox="gallery">
<img class="article-image-rect" src="images/blogs/ai/board_bonus_searchai_snakey.jpg" alt="Bonus distribution Snakey" class="img-fluid">
<div class="photo-text-more">
<span class="icon icon-search">Bonus distribution Snakey</span>
</div>
</a>
</div>
<div class="col-md-4">
<a href="images/blogs/ai/board_bonus_searchai_diagonaled.jpg" class="d-block photo-item" data-fancybox="gallery">
<img class="article-image-rect" src="images/blogs/ai/board_bonus_searchai_diagonaled.jpg" alt="Bonus distribution Snakey" class="img-fluid">
<div class="photo-text-more">
<span class="icon icon-search">Bonus distribution Diagonal</span>
</div>
</a>
</div>
<div class="col-md-4">
<a href="images/blogs/ai/board_bonus_searchai_squared.jpg" class="d-block photo-item" data-fancybox="gallery">
<img class="article-image-rect" src="images/blogs/ai/board_bonus_searchai_squared.jpg" alt="Bonus distribution Snakey" class="img-fluid">
<div class="photo-text-more">
<span class="icon icon-search">Bonus distribution Square</span>
</div>
</a>
</div>
</div>
</div>
</div>
</figure>
<p>
</p>
<h4>Conclusion</h4>
<p>In the following table we listed the performance of each expectimax scoring function we developed, to compare them against each other.
</p>
<table>
<caption>Comparison of the implemented expectimax scoring functions</caption>
<tr>
<th>Algorithm Name</th>
<th>Highscore</th>
<th>Average Score</th>
<th>Highest Tile</th>
<th>Time Per Move [s]</th>
</tr>
<tr>
<td>Snakey</td>
<td>167'888</td>
<td>90'813</td>
<td>8192</td>
<td>0.58130573</td>
</tr>
<tr>
<td>Snakey+</td>
<td>113'180</td>
<td>68'555</td>
<td>8192</td>
<td>1.30097970</td>
</tr>
<tr>
<td>Diagonal</td>
<td>132'996</td>
<td>65'321</td>
<td>8192</td>
<td>0.54674995</td>
</tr>
<tr>
<td>Heuristic</td>
<td>112'776</td>
<td>44'194</td>
<td>8192</td>
<td>0.15212381</td>
</tr>
<tr>
<td>Square</td>
<td>36'772</td>
<td>19'658</td>
<td>2048</td>
<td>0.08806930</td>
</tr>
</table>
<p>The following two graphs show how the score and the tiles have been distributed over 20 games. As one can see, is the Snakey scoring function
mostly in the range between 60'000 to 80'000 points, which means that he often fails just before merging to the 8192. Whereas the Diagonal scoring function seems to have
less problems merging to the 8192 tile when it even comes as far as the 4096 tile. This leads to the conclusion that in the Diagonal function the distribution of tiles
seems to be better when the board is loaded with high tiles.
A next step could be to combine the Snakey and Diagonal function, that the Snakey handles the part until the 4096 tile and then the Diagonal function takes over to reach an even higher score.
</p>
<figure>
<div class="single-slide">
<div class="container-fluid">
<div class="row">
<div class="col-md-6">
<a href="images/blogs/ai/scores.png" class="d-block photo-item" data-fancybox="gallery">
<img class="article-statistic" src="images/blogs/ai/scores.png" alt="score distribution" class="img-fluid">
<div class="photo-text-more">
<span class="icon icon-search">Distribution of the score over 20 games</span>
</div>
</a>
</div>
<div class="col-md-6">
<a href="images/blogs/ai/highest_tiles_reached.png" class="d-block photo-item" data-fancybox="gallery">
<img class="article-statistic" src="images/blogs/ai/highest_tiles_reached.png" alt="highest reached tiles" class="img-fluid">
<div class="photo-text-more">
<span class="icon icon-search">Distribution of the highest reached tiles over 20 games</span>
</div>
</a>
</div>
</div>
</div>
</div>
</figure>
<p>As a last step we analysed the speed of our AI and how much multiprocessing speeded the calculation up for different depths.
We started always from the same board as seen on the graphic below and made three moves with every variation.
The variations reached from depth one to depth five and once with multiprocessing enabled and once without.
We calculated the average time per move and compared them to each other.</br>
In conclusion we saw that multiprocessing is already a bit faster at depth one and nearly double as fast at depth two.
As expected the performance boost increased quickly and at depth five multiprocessing was already four times faster than singleproccessing.
</p>
<figure>
<div class="single-slide">
<div class="container-fluid">
<div class="row">
<div class="col-md-4">
<a href="images/blogs/ai/time_measure_starting_point.png" class="d-block photo-item" data-fancybox="gallery">
<img class="article-statistic" src="images/blogs/ai/time_measure_starting_point.png" alt="starting point time measurement" class="img-fluid">
<div class="photo-text-more">
<span class="icon icon-search">Startingboard of the time measurement</span>
</div>
</a>
</div>
<div class="col-md-4">
<a href="images/blogs/ai/time_per_move_per_depths.png" class="d-block photo-item" data-fancybox="gallery">
<img class="article-statistic" src="images/blogs/ai/time_per_move_per_depths.png" alt="average time per move per depths" class="img-fluid">
<div class="photo-text-more">
<span class="icon icon-search"></span>
</div>
</a>
</div>
<div class="col-md-4">
<table class="article-statistic">
<tr>
<th>Depth</th>
<th>Singleprocess [s]</th>
<th>Multiprocess [s]</th>
</tr>
<tr>
<td>1</td>
<td>0.010971</td>
<td>0.008644</td>
</tr>
<tr>
<td>2</td>
<td>0.067817</td>
<td>0.040891</td>
</tr>
<tr>
<td>3</td>
<td>2.558497</td>
<td>0.620329</td>
</tr>
<tr>
<td>4</td>
<td>48.070847</td>
<td>24.369725</td>
</tr>
<tr>
<td>5</td>
<td>1641.396178</td>
<td>416.629117</td>
</tr>
</table>
<figcaption>Average times per move per depths</figcaption>
</div>
</div>
</div>
</div>
</figure>
</div>
<div id="disqus_thread"></div>
<script>
/**
* RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS.
* LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables*/
/**
var disqus_config = function () {
this.page.url = PAGE_URL; // Replace PAGE_URL with your page's canonical URL variable
this.page.identifier = PAGE_IDENTIFIER; // Replace PAGE_IDENTIFIER with your page's unique identifier variable
};
**/
(function() { // DON'T EDIT BELOW THIS LINE
var d = document,
s = d.createElement('script');
s.src = 'https://blackprism.disqus.com/embed.js';
s.setAttribute('data-timestamp', +new Date());
(d.head || d.body).appendChild(s);
})();
</script>
<noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
</div>
</section>
<!-- ##### Footer Area Start ##### -->
<footer class="footer-area">
<!-- Footer Logo -->
<div class="footer-logo mb-100">
<a href="index.html">The Black Prism</a>
</div>
</footer>
<!-- ##### Footer Area Start ##### -->
<div id="particles-js"></div>
<!-- ##### All Javascript Script ##### -->
<!-- jQuery-2.2.4 js -->
<script src="js/jquery/jquery-2.2.4.min.js"></script>
<!-- Popper js -->
<script src="js/bootstrap/popper.min.js"></script>
<!-- Bootstrap js -->
<script src="js/bootstrap/bootstrap.min.js"></script>
<!-- All Plugins js -->
<script src="js/plugins/plugins.js"></script>
<!-- Active js -->
<script src="js/active.js"></script>
<!-- Gallery js -->
<script src="js/jquery/jquery.fancybox.min.js"></script>
<script src="js/jquery/jquery.magnific-popup.min.js"></script>
<script src="js/gallery-main.js"></script>
<script src="https://cdn.jsdelivr.net/particles.js/2.0.0/particles.min.js"></script>
<script src="js/main.js"></script>
</body>
</html>