<p><div><div><div><div data-width="100" data-show-faces="false" data-send="true" data-layout="button_count" data-height="21" data-href="https://www.r-bloggers.com/tic-tac-toe-war-games-the-intelligent-minimax-algorithm/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://r.prevos.net/tic-tac-toe-war-games/"> The Devil is in the Data</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p><img alt="Tic Tac Toe War Games" src="https://i0.wp.com/movie-roulette.com/posters_new/wargames.jpg?resize=300%2C413" data-recalc-dims="1">In a <a target="_blank" rel="nofollow" href="http://r.prevos.net/tic-tac-toe-simulation/">previous post</a>, I shared how to build a randomised Tic Tac Toe simulation. The computer plays against itself playing at random positions. In this post, I will share how to teach the computer to play the game strategically.</p>
<p>I love the 1983 classic movie <a target="_blank" rel="nofollow" href="http://www.imdb.com/title/tt0086567/">War Games</a>. In this film, a computer plays Tic Tac Toe against itself to learn that it cannot win the game to prevent a nuclear war.</p>
<p>Back in those days, I devoured the wonderful book <em>Writing Strategy Games on your Atari</em> by John White which contains an algorithm to play Tic Tac Toe War Games. This is my attempt to relive the eighties using R.</p>
<p>You can find the code on my <a target="_blank" rel="nofollow" href="https://github.com/pprevos/TicTacToe">GitHub page</a>.</p>
<h2>Drawing the Board</h2>
<p>A <a target="_blank" rel="nofollow" href="http://r.prevos.net/tic-tac-toe-simulation/">previous post</a> describes the function that draws the Tic Tac Toe board. For completeness, the code is replicated below. The game board is a vector of length nine consisting of either -1 (X), 0 (empty field) or 1 (O). The vector indices correspond with locations on the game board:</p>
<p>1 2 3<br>
4 5 6<br>
7 8 9</p>
<pre>
draw.board &lt;- function(board) { # Draw the board
    xo &lt;- c(&quot;X&quot;, &quot; &quot;, &quot;O&quot;) # Symbols
    par(mar = rep(0,4))
    plot.new()
    plot.window(xlim = c(0,30), ylim = c(0,30))
    abline(h = c(10, 20), col=&quot;darkgrey&quot;, lwd = 4)
    abline(v = c(10, 20), col=&quot;darkgrey&quot;, lwd = 4)
    pieces &lt;- xo[board + 2]
    text(rep(c(5, 15, 25), 3), c(rep(25, 3), rep(15,3), rep(5, 3)), pieces, cex = 6)
    # Identify location of any three in a row
    square &lt;- t(matrix(board, nrow = 3))
    hor &lt;- abs(rowSums(square))
    if (any(hor == 3)) 
      hor &lt;- (4 - which(hor == 3)) * 10 - 5 
    else 
      hor &lt;- 0
    ver &lt;- abs(colSums(square))
    if (any(ver == 3)) 
      ver &lt;- which(ver == 3) * 10 - 5 
    else
      ver &lt;- 0
    diag1 &lt;- sum(diag(square))
    diag2 &lt;- sum(diag(t(apply(square, 2, rev)))) # Draw winning lines if (hor > 0) lines(c(0, 30), rep(hor, 2), lwd=10, col=&quot;red&quot;)
    if (ver > 0) lines(rep(ver, 2), c(0, 30), lwd=10, col=&quot;red&quot;)
    if (abs(diag1) == 3) lines(c(2, 28), c(28, 2), lwd=10, col=&quot;red&quot;)
    if (abs(diag2) == 3) lines(c(2, 28), c(2, 28), lwd=10, col=&quot;red&quot;)
}
</pre>
<h2>Human Players</h2>
<p>This second code snippet lets a human player move by clicking anywhere on the graphic display using the <a target="_blank" rel="nofollow" href="https://stat.ethz.ch/R-manual/R-devel/library/graphics/html/locator.html">locator</a> function. The click location is converted to a number to denote the position on the board. The entered field is only accepted if it has not yet been used (the <em>empty</em> variable contains the available fields).</p>
<pre>
# Human player enters a move
move.human &lt;- function(game) {
    text(4, 0, &quot;Click on screen to move&quot;, col = &quot;grey&quot;, cex=.7)
    empty &lt;- which(game == 0)
    move &lt;- 0
    while (!move %in% empty) {
        coords &lt;- locator(n = 1) # add lines
        coords$x &lt;- floor(abs(coords$x) / 10) + 1
        coords$y &lt;- floor(abs(coords$y) / 10) + 1
        move &lt;- coords$x + 3 * (3 - coords$y)
    }
    return (move)
}
</pre>
<h2></h2>
<h2>Evaluate the Game</h2>
<p>This code snippet defines the <em>eval.game</em> function which assesses the current board and assigns a score. Zero means no outcome, -6 means that the <em>X</em> player has won and +6 implies that the <em>O</em> player has won.</p>
<pre>
# Evaluate board position
eval.game &lt;- function(game, player) {
    # Determine game score
    square &lt;- t(matrix(game, nrow = 3))
    hor &lt;- rowSums(square)
    ver &lt;- colSums(square)
    diag1 &lt;- sum(diag(square))
    diag2 &lt;- sum(diag(t(apply(square, 2, rev))))
    eval &lt;- c(hor, ver, diag1, diag2)
    # Determine best score
    minimax &lt;- ifelse(player == -1, &quot;min&quot;, &quot;max&quot;)
    best.score &lt;- do.call(minimax, list(eval))
    if (abs(best.score) == 3) best.score &lt;- best.score * 2
    return (best.score)
}
</pre>
<h2>Computer Moves</h2>
<p>The computer uses a modified <a target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Minimax">Minimax Algorithm</a> to determine its next move. This article from the <a target="_blank" rel="nofollow" href="http://neverstopbuilding.com/minimax">Never Stop Building</a> blog and the video below explain this method in great detail.</p>
<p><iframe width="450" allowfullscreen="true" src="https://www.youtube.com/embed/6kFKnB6JtcY?version=3&rel=1&%23038;fs=1&%23038;autohide=2&%23038;showsearch=0&%23038;showinfo=1&%23038;iv_load_policy=1&%23038;wmode=transparent" type="text/html"></iframe></p>
<p>The next function determines the computer’s move. I have not used a brute-force minimax algorithm to save running time. I struggled building a fully recursive minimax function. Perhaps somebody can help me with this. This code looks only two steps deep and contains a strategic rule to maximise the score.</p>
<p>The first line stores the value of the players move, the second remainder of the matrix holds the evaluations of all the opponents moves. The code adds a randomised variable, based on the strategic value of a field. The centre has the highest value because it is part of four winning lines. Corners have three winning lines and the rest only two winning lines. This means that the computer will, all things being equal, favour the centre over the corners and favour the other fields least. The randomised variables in the code ensure that the computer does not always pick the same field in a similar situation.</p>
<pre>
# Determine computer move
move.computer &lt;- function(game, player) {
    empty &lt;- which(game == 0)
    eval &lt;- matrix(nrow = 10, ncol = 9, data = 0)
    for (i in empty) {
        game.tmp &lt;- game
        game.tmp[i] &lt;- player
        eval[1, i] &lt;- eval.game(game.tmp, player)
        empty.tmp &lt;- which(game.tmp ==0)
        for (j in empty.tmp) {
            game.tmp1 &lt;- game.tmp
            game.tmp1[j] &lt;- -player
            eval[(j + 1), i] &lt;- eval.game(game.tmp1, -player)
        }
    }
    if (!any(abs(eval[1,]) == 6)) { # When winning, play move
        # Analyse opponent move
        minimax &lt;- ifelse(player == -1, &quot;max&quot;, &quot;min&quot;) # Minimax
        best.opponent &lt;- apply(eval[-1,], 1, minimax)
        eval[1,] &lt;- eval[1,] * -player * best.opponent
    }
    # Add randomisation and strategic values
    board &lt;- c(3, 2, 3, 2, 4, 2, 3, 2, 3) # Strategic values
    board &lt;- sapply(board, function(x) runif(1, 0.1 * x, (0.1 * x) + 0.1)) # Randomise
    eval[1, empty] &lt;- eval[1, empty] + player * board[empty] # Randomise moves
    # Pick best game
    minimax &lt;- ifelse(player == -1, &quot;which.min&quot;, &quot;which.max&quot;) # Minimax
    move &lt;- do.call(minimax, list(eval[1,])) # Select best move
    return(move)
}
</pre>
<p>This last code snippet enables computers and humans play each other or themselves. The <em>players</em> vector contains the identity of the two players so that a human can play a computer or vice versa. The human player moves by clicking on the screen.</p>
<p>The loop keeps running until the board is full or a winner has been identified. A <a target="_blank" rel="nofollow" href="http://r.prevos.net/tic-tac-toe-simulation/">previous Tic Tac Toe post</a> explains the <em>draw.board</em> function.</p>
<pre>
# Main game engine
tic.tac.toe &lt;- function(player1 = &quot;human&quot;, player2 = &quot;computer&quot;) {
    game &lt;- rep(0, 9) # Empty board
    winner &lt;- FALSE # Define winner
    player &lt;- 1 # First player
    players &lt;- c(player1, player2)
    draw.board(game)
    while (0 %in% game &amp; !winner) { # Keep playing until win or full board
        if (players[(player + 3) %% 3] == &quot;human&quot;) # Human player
            move &lt;- move.human(game)
        else # Computer player
            move &lt;- move.computer(game, player)
        game[move] &lt;- player # Change board
        draw.board(game)
        winner &lt;- max(eval.game(game, 1), abs(eval.game(game, -1))) == 6 # Winner, winner, chicken dinner?
        player &lt;- -player # Change player
    }
}
</pre>
<p>You can play the computer by running all functions and then entering <em>tic.tac.toe()</em>.</p>
<p>I am pretty certain this simplified minimax algorithm is unbeatable—why don’t you try to win and let me know when you do.</p>
<h2>Tic Tac Toe War Games</h2>
<p>Now that this problem is solved, I can finally recreate the epic scene from the WarGames movie. The Tic Tac Toe War Games code uses the functions explained above and the <a target="_blank" rel="nofollow" href="https://cran.r-project.org/web/packages/animation/index.html">animation package</a>. Unfortunately, there are not many opportunities to create sound in R.</p>
<p><a target="_blank" rel="nofollow" href="http://r.prevos.net/?attachment_id=562"><img data-image-description="" data-orig-file="https://i2.wp.com/r.prevos.net/wp-content/uploads/sites/11/2017/04/wargames.gif?fit=600%2C600" data-orig-size="600,600" data-image-title="wargames" class="wp-image-562" data-comments-opened="1" data-recalc-dims="1" data-attachment-id="562" data-permalink="http://r.prevos.net/tic-tac-toe-war-games/wargames/" alt="" data-medium-file="https://i2.wp.com/r.prevos.net/wp-content/uploads/sites/11/2017/04/wargames.gif?fit=300%2C300" data-large-file="https://i2.wp.com/r.prevos.net/wp-content/uploads/sites/11/2017/04/wargames.gif?fit=584%2C584" data-image-meta="{&quot;aperture&quot;:&quot;0&quot;,&quot;credit&quot;:&quot;&quot;,&quot;camera&quot;:&quot;&quot;,&quot;caption&quot;:&quot;&quot;,&quot;created_timestamp&quot;:&quot;0&quot;,&quot;copyright&quot;:&quot;&quot;,&quot;focal_length&quot;:&quot;0&quot;,&quot;iso&quot;:&quot;0&quot;,&quot;shutter_speed&quot;:&quot;0&quot;,&quot;title&quot;:&quot;&quot;,&quot;orientation&quot;:&quot;0&quot;}" src="https://i2.wp.com/r.prevos.net/wp-content/uploads/sites/11/2017/04/wargames.gif?resize=584%2C584"></a></p>
<p><iframe width="450" allowfullscreen="true" src="https://www.youtube.com/embed/F7qOV8xonfY?version=3&rel=1&%23038;fs=1&%23038;autohide=2&%23038;showsearch=0&%23038;showinfo=1&%23038;iv_load_policy=1&%23038;wmode=transparent" type="text/html"></iframe></p>
<pre>
# WAR GAMES TIC TAC TOE
source(&quot;Tic Tac Toe/Tic Tac Toe.R&quot;)

# Draw the game board
draw.board.wargames &lt;- function(game) {
    xo &lt;- c(&quot;X&quot;, &quot; &quot;, &quot;O&quot;) # Symbols
    par(mar = rep(1,4), bg = &quot;#050811&quot;)
    plot.new()
    plot.window(xlim = c(0,30), ylim = c(0,30))
    abline(h = c(10, 20), col = &quot;#588fca&quot;, lwd = 20)
    abline(v = c(10, 20), col = &quot;#588fca&quot;, lwd = 20)
    text(rep(c(5, 15, 25), 3), c(rep(25, 3), rep(15,3), rep(5, 3)), xo[game + 2], cex = 20, col = &quot;#588fca&quot;)
    text(1,0,&quot;r.prevos.net&quot;, col = &quot;#588fca&quot;, cex=2)
    # Identify location of any three in a row
    square &lt;- t(matrix(game, nrow = 3))
    hor &lt;- abs(rowSums(square))
    if (any(hor == 3)) 
        hor &lt;- (4 - which(hor == 3)) * 10 - 5 
    else 
        hor &lt;- 0
    ver &lt;- abs(colSums(square))
    if (any(ver == 3)) 
        ver &lt;- which(ver == 3) * 10 - 5 
    else
        ver &lt;- 0
    diag1 &lt;- sum(diag(square))
    diag2 &lt;- sum(diag(t(apply(square, 2, rev)))) # Draw winning lines if (all(hor > 0)) for (i in hor) lines(c(0, 30), rep(i, 2), lwd = 10, col=&quot;#588fca&quot;)
    if (all(ver > 0)) for (i in ver) lines(rep(i, 2), c(0, 30), lwd = 10, col=&quot;#588fca&quot;)
    if (abs(diag1) == 3) lines(c(2, 28), c(28, 2), lwd = 10, col = &quot;#588fca&quot;)
    if (abs(diag2) == 3) lines(c(2, 28), c(2, 28), lwd = 10, col = &quot;#588fca&quot;)
}

library(animation)
player &lt;- -1
games &lt;- 100
saveGIF ({
    for (i in 1:games) {
        game &lt;- rep(0, 9) # Empty board
        winner &lt;- 0 # Define winner
        #draw.board.wargames(game)
        while (0 %in% game &amp; !winner) { # Keep playing until win or full board
            empty &lt;- which(game == 0)
            move &lt;- move.computer(game, player)
            game[move] &lt;- player
            if (i &lt;= 12) draw.board.wargames(game)
            winner &lt;- max(eval.game(game, 1), abs(eval.game(game, -1))) == 6
            player &lt;- -player } if (i > 12) draw.board.wargames(game)
    }
},
interval = c(unlist(lapply(seq(1, 0,-.2), function (x) rep(x, 9))), rep(0,9*94)), 
movie.name = &quot;wargames.gif&quot;, ani.width = 1024, ani.height = 1024)
</pre>
<p>The post <a target="_blank" rel="nofollow" href="http://r.prevos.net/tic-tac-toe-war-games/">Tic Tac Toe War Games: The Intelligent Minimax Algorithm</a> appeared first on <a target="_blank" rel="nofollow" href="http://r.prevos.net/">The Devil is in the Data</a>.</p>
<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="http://r.prevos.net/tic-tac-toe-war-games/"> The Devil is in the Data</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a title="The R Project for Statistical Computing" rel="nofollow" href="https://www.r-project.org/">R</a> news and <a title="R tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/tutorial">tutorials</a> on topics such as: <a title="Data science" rel="nofollow" href="https://www.r-bloggers.com/search/data%20science">Data science</a>, <a title="Big Data" rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data">Big Data, <a title="R jobs" rel="nofollow" href="https://www.r-users.com/">R jobs</a>, visualization (<a title="ggplot and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2">ggplot2</a>, <a title="Boxplots using lattice and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/boxplot">Boxplots</a>, <a title="Maps and gis" rel="nofollow" href="https://www.r-bloggers.com/search/map">maps</a>, <a title="Animation in R" rel="nofollow" href="https://www.r-bloggers.com/search/animation">animation</a>), programming (<a title="RStudio IDE for R" rel="nofollow" href="https://www.r-bloggers.com/search/RStudio">RStudio</a>, <a title="Sweave and literate programming" rel="nofollow" href="https://www.r-bloggers.com/search/sweave">Sweave</a>, <a title="LaTeX in R" rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX">LaTeX</a>, <a title="SQL and databases" rel="nofollow" href="https://www.r-bloggers.com/search/SQL">SQL</a>, <a title="Eclipse IDE for R" rel="nofollow" href="https://www.r-bloggers.com/search/eclipse">Eclipse</a>, <a title="git and github, Version Control System" rel="nofollow" href="https://www.r-bloggers.com/search/git">git</a>, <a title="Large data in R using Hadoop" rel="nofollow" href="https://www.r-bloggers.com/search/hadoop">hadoop</a>, <a title="Web Scraping of google, facebook, yahoo, twitter and more using R" rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping">Web Scraping</a>) statistics (<a title="Regressions and ANOVA analysis tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/regression">regression</a>, <a title="principal component analysis tutorial" rel="nofollow" href="https://www.r-bloggers.com/search/PCA">PCA</a>, <a title="Time series" rel="nofollow" href="https://www.r-bloggers.com/search/time+series">time series</a>, <a title="finance trading" rel="nofollow" href="https://www.r-bloggers.com/search/trading">trading</a>) and more...
<img height="1" alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/4RPcMQEDztA"></a></div>