-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathbuilding-an-unbeatable-tic-tac-toe-ai.html
151 lines (132 loc) · 14.2 KB
/
building-an-unbeatable-tic-tac-toe-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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<title>Building An Unbeatable Tic Tac Toe AI</title>
<link rel="stylesheet" href="/theme/css/main.css" />
</head>
<body id="index" class="home">
<header id="banner" class="body">
<h1><a href="/">Rob's Blog </a></h1>
<nav><ul>
<li class="active"><a href="/category/flatiron.html">Flatiron</a></li>
<li><a href="/category/general.html">General</a></li>
<li><a href="/category/iot.html">IOT</a></li>
<li><a href="/category/python.html">Python</a></li>
</ul></nav>
</header><!-- /#banner -->
<section id="content" class="body">
<article>
<header>
<h1 class="entry-title">
<a href="/building-an-unbeatable-tic-tac-toe-ai.html" rel="bookmark"
title="Permalink to Building An Unbeatable Tic Tac Toe AI">Building An Unbeatable Tic Tac Toe AI</a></h1>
</header>
<div class="entry-content">
<footer class="post-info">
<abbr class="published" title="2018-02-09T07:51:00+00:00">
Published: Fri 09 February 2018
</abbr>
<address class="vcard author">
By <a class="url fn" href="/author/robert-hughes.html">Robert Hughes</a>
</address>
<p>In <a href="/category/flatiron.html">Flatiron</a>.</p>
</footer><!-- /.post-info --> <p>The first major challenge that I faced with the coding boot camp was building an unbeatable Tic-Tac-Toe AI. I have managed to create an algorithm to solve this problem, with only one move being hard coded.</p>
<p>The overarching logic of my program is this the move method, found below.</p>
<div class="highlight"><pre><span></span> <span class="k">def</span> <span class="nf">move</span><span class="p">(</span><span class="n">board</span><span class="p">)</span>
<span class="vi">@board</span> <span class="o">=</span> <span class="n">board</span>
<span class="k">if</span> <span class="n">o_cells</span><span class="o">.</span><span class="n">empty?</span> <span class="o">&&</span> <span class="n">empty_cells</span><span class="o">.</span><span class="n">include?</span><span class="p">(</span><span class="mi">5</span><span class="p">)</span>
<span class="k">return</span> <span class="s2">"5"</span>
<span class="k">end</span>
<span class="c1"># Only include empty cells on the array feeding in to the freq table</span>
<span class="n">valid_selection</span> <span class="o">=</span> <span class="n">weighted_selection</span><span class="o">.</span><span class="n">flatten</span><span class="o">.</span><span class="n">select</span> <span class="k">do</span> <span class="o">|</span><span class="n">ws</span><span class="o">|</span>
<span class="n">empty_cells</span><span class="o">.</span><span class="n">include?</span><span class="p">(</span><span class="n">ws</span><span class="p">)</span>
<span class="k">end</span>
<span class="n">freq_table</span> <span class="o">=</span> <span class="n">valid_selection</span><span class="o">.</span><span class="n">flatten</span><span class="o">.</span><span class="n">inject</span><span class="p">(</span><span class="no">Hash</span><span class="o">.</span><span class="n">new</span><span class="p">(</span><span class="mi">0</span><span class="p">))</span> <span class="k">do</span> <span class="o">|</span><span class="n">k</span><span class="p">,</span> <span class="n">v</span><span class="o">|</span>
<span class="n">k</span><span class="o">[</span><span class="n">v</span><span class="o">]</span> <span class="o">+=</span> <span class="mi">1</span>
<span class="n">k</span>
<span class="k">end</span>
<span class="n">choice</span> <span class="o">=</span> <span class="n">valid_selection</span><span class="o">.</span><span class="n">flatten</span><span class="o">.</span><span class="n">max_by</span> <span class="p">{</span> <span class="o">|</span><span class="n">v</span><span class="o">|</span> <span class="n">freq_table</span><span class="o">[</span><span class="n">v</span><span class="o">]</span> <span class="p">}</span>
<span class="n">choice</span><span class="o">.</span><span class="n">to_s</span>
<span class="k">end</span>
</pre></div>
<p>As the move method is the entry point, it starts by storing the board in the class. I would have preferred to have this in the initialise method, but the rspec's provided also requested for this method to take on the board. It may have even overcomplicated the set up of the computer player, but it would have saved reassignment every move.</p>
<p>The if statement short circuits the method to return the centre cell if "O" has not made a move. I can not see an algorithmic way to make sure that the central cell is chosen first on a second step without needlessly overcomplicating the program. As this is a simple enough rule, and it doesn't turn in to many if.. else statements, I am happy with this solution.</p>
<p>The next part of this method takes the weighted selection, flattens it, and selects all of the empty cells. The weighted selection is discussed further on in detail. I build a frequency table from the weighted range of winning cells and return the highest frequency response. The frequency table makes sure that the free cell with the most combinations for wins is selected. The answer is then returned as a string to satisfy the test case for this method, and also to provide consistency with a human users response.</p>
<div class="highlight"><pre><span></span> <span class="k">def</span> <span class="nf">empty_cells</span>
<span class="n">result</span> <span class="o">=</span> <span class="o">[]</span>
<span class="vi">@board</span><span class="o">.</span><span class="n">cells</span><span class="o">.</span><span class="n">each_with_index</span> <span class="p">{</span> <span class="o">|</span><span class="n">c</span><span class="p">,</span> <span class="n">i</span><span class="o">|</span> <span class="n">result</span> <span class="o"><<</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span> <span class="k">if</span> <span class="n">c</span> <span class="o">==</span> <span class="s2">" "</span> <span class="p">}</span>
<span class="n">result</span>
<span class="k">end</span>
<span class="k">def</span> <span class="nf">x_cells</span>
<span class="n">result</span> <span class="o">=</span> <span class="o">[]</span>
<span class="vi">@board</span><span class="o">.</span><span class="n">cells</span><span class="o">.</span><span class="n">each_with_index</span> <span class="p">{</span> <span class="o">|</span><span class="n">c</span><span class="p">,</span> <span class="n">i</span><span class="o">|</span> <span class="n">result</span> <span class="o"><<</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span> <span class="k">if</span> <span class="n">c</span> <span class="o">==</span> <span class="s2">"X"</span> <span class="p">}</span>
<span class="n">result</span>
<span class="k">end</span>
<span class="k">def</span> <span class="nf">o_cells</span>
<span class="n">result</span> <span class="o">=</span> <span class="o">[]</span>
<span class="vi">@board</span><span class="o">.</span><span class="n">cells</span><span class="o">.</span><span class="n">each_with_index</span> <span class="p">{</span> <span class="o">|</span><span class="n">c</span><span class="p">,</span> <span class="n">i</span><span class="o">|</span> <span class="n">result</span> <span class="o"><<</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span> <span class="k">if</span> <span class="n">c</span> <span class="o">==</span> <span class="s2">"O"</span> <span class="p">}</span>
<span class="n">result</span>
<span class="k">end</span>
</pre></div>
<p>The cells methods return an array of cell numbers occupied by their respective tokens, or lack thereof. It had occurred to me, and I had forgotten until now, that I could refactor the above into something such as the below:</p>
<div class="highlight"><pre><span></span> <span class="k">def</span> <span class="nf">cells</span><span class="p">(</span><span class="n">token</span><span class="p">)</span>
<span class="vi">@board</span><span class="o">.</span><span class="n">cells</span><span class="o">.</span><span class="n">select</span> <span class="p">{</span> <span class="o">|</span><span class="n">c</span><span class="o">|</span> <span class="n">c</span> <span class="o">==</span> <span class="s2">"O"</span> <span class="p">}</span><span class="o">.</span><span class="n">each_with_index</span><span class="o">.</span><span class="n">map</span> <span class="p">{</span> <span class="o">|</span><span class="n">c</span><span class="p">,</span> <span class="n">i</span><span class="o">|</span> <span class="n">c</span> <span class="o">+</span> <span class="mi">1</span> <span class="p">}</span>
<span class="k">end</span>
</pre></div>
<p>It could still be worth splitting the above into two lines to break up the logic.</p>
<p>The opponent_weightings method sorts through the wins and takes -3 for each cell occupied by "X". The current players token would need checking if an option were available for the Human to play as "O".</p>
<div class="highlight"><pre><span></span> <span class="k">def</span> <span class="nf">opponent_weightings</span>
<span class="n">result</span> <span class="o">=</span> <span class="nb">Array</span><span class="o">.</span><span class="n">new</span><span class="p">(</span><span class="mi">8</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span>
<span class="no">WIN_COMBINATIONS</span><span class="o">.</span><span class="n">each_with_index</span> <span class="k">do</span> <span class="o">|</span><span class="n">win</span><span class="p">,</span> <span class="n">win_no</span><span class="o">|</span>
<span class="n">remaining</span> <span class="o">=</span> <span class="n">win</span> <span class="o">-</span> <span class="p">(</span><span class="n">x_cells</span> <span class="o">+</span> <span class="n">o_cells</span><span class="p">)</span>
<span class="k">if</span> <span class="n">remaining</span><span class="o">.</span><span class="n">length</span> <span class="o">></span> <span class="mi">0</span>
<span class="n">win</span><span class="o">.</span><span class="n">each</span> <span class="p">{</span> <span class="o">|</span><span class="n">w</span><span class="o">|</span> <span class="n">result</span><span class="o">[</span><span class="n">win_no</span><span class="o">]</span> <span class="o">-=</span> <span class="mi">3</span> <span class="k">if</span> <span class="n">x_cells</span><span class="o">.</span><span class="n">include?</span><span class="p">(</span><span class="n">w</span><span class="p">)</span> <span class="p">}</span>
<span class="k">end</span>
<span class="k">end</span>
<span class="n">result</span>
<span class="k">end</span>
</pre></div>
<p>The weighted selection sorts through the opponent weightings and only returns those with the lowest score, assuming there is a spare cell.</p>
<div class="highlight"><pre><span></span> <span class="k">def</span> <span class="nf">weighted_selection</span>
<span class="n">lowest</span> <span class="o">=</span> <span class="mi">0</span>
<span class="n">selection</span> <span class="o">=</span> <span class="o">[]</span>
<span class="n">opponent_weightings</span><span class="o">.</span><span class="n">each_with_index</span> <span class="k">do</span> <span class="o">|</span><span class="n">weight</span><span class="p">,</span> <span class="n">i</span><span class="o">|</span>
<span class="k">if</span> <span class="n">weight</span> <span class="o"><</span> <span class="n">lowest</span>
<span class="n">selection</span> <span class="o">=</span> <span class="o">[</span><span class="n">i</span><span class="o">]</span>
<span class="n">lowest</span> <span class="o">=</span> <span class="n">weight</span>
<span class="k">elsif</span> <span class="n">weight</span> <span class="o">==</span> <span class="n">lowest</span>
<span class="n">selection</span> <span class="o"><<</span> <span class="n">i</span>
<span class="k">end</span>
<span class="k">end</span>
<span class="n">selection</span><span class="o">.</span><span class="n">map</span> <span class="p">{</span> <span class="o">|</span><span class="n">win</span><span class="o">|</span> <span class="no">WIN_COMBINATIONS</span><span class="o">[</span><span class="n">win</span><span class="o">]</span> <span class="p">}</span>
<span class="k">end</span>
</pre></div>
</div><!-- /.entry-content -->
</article>
</section>
<section id="extras" class="body">
<div class="blogroll">
<h2>links</h2>
<ul>
<li><a href="http://getpelican.com/">Pelican</a></li>
<li><a href="http://python.org/">Python.org</a></li>
<li><a href="http://jinja.pocoo.org/">Jinja2</a></li>
</ul>
</div><!-- /.blogroll -->
<div class="social">
<h2>social</h2>
<ul>
<li><a href="https://github.com/safuya/">GitHub</a></li>
<li><a href="https://www.linkedin.com/in/robert-hughes-safuya/">LinkedIn</a></li>
</ul>
</div><!-- /.social -->
</section><!-- /#extras -->
<footer id="contentinfo" class="body">
<address id="about" class="vcard body">
Proudly powered by <a href="http://getpelican.com/">Pelican</a>, which takes great advantage of <a href="http://python.org">Python</a>.
</address><!-- /#about -->
<p>The theme is by <a href="http://coding.smashingmagazine.com/2009/08/04/designing-a-html-5-layout-from-scratch/">Smashing Magazine</a>, thanks!</p>
</footer><!-- /#contentinfo -->
</body>
</html>