Tic-Tac-Toe - Part 2

Index

Attached Files

The following files have been attached to this tutorial:

.zip

bht-tictactoe-ai-1p2.zip

Download now 138 KB
.capx

tictactoe-part2.capx

Download now 883 KB

Stats

2,512 visits, 6,933 views

Translations

This tutorial hasn't been translated.

Tools

The Plugin

I won’t go into the details of making a plugin, this is covered well in the SDK documentation, so I’ll skip to the runtime functions.

The algorithm I chose I found online. It is not the typical minimax algorithm generally chosen. There are many ways of dealing with tic-tac-toe, mainly because it is so simple and only has 8 combinations that can actually win. You can take various shortcuts to making an automated player. The one I chose calculates weights on a move.

The first thing it does is figure out, given the current play, which subset of the winners array applies. The moment you play a location, you can eliminate any of the winners that don’t apply, so you only have to deal with a smaller set of possible plays. You do this for both X and O. Then you calculate weight values against this subset of winner combinations to see which is the best move.

To do this we create yet another array of weight values, where we test each of the winners against each possible move and add a weight value to that element. A move that gets us a future winner adds 1 to the element. A move that actually gives us a win gets a higher value. I’ve chosen to add 10 for a win for the current player, and a 5 for the opponent.

What the 5 does is give a higher weight to a move that will stop the opponent from winning, as, just like before, we use the same code for the current player and the opponent, since, the higher the weight for the opponents next move, the more you want to block that move. The 10 however enforces that we give a much higher weight to winning than to blocking (a mistake I initially made the first time round).

WillWin()

What we’re doing here is checking if a specific move, made against our current play array will win (if played). First we default to not winning (line 25), then we get the new player-value, based on whether this is X or O (line 26), we copy the current array so we can add our new move (line 27), and add our new move (line 29).

We copy the three winning-line values, for easy reference (line 31-33), and do a similar test to our GUI/event code to check if they are all the same and the current player (line 34). If so, we want to return a result = true (line 36). And we return the result (line 38).

BuildPossibleWinnerLines()

Start by copying the winners array, as we will remove any that we don’t need (line 47). Lines 48-52 just figure out the opponent’s value. Because we are removing elements, we want to start at the end, so we can loop from the end to the beginning and remove items from bottom to top. This is easier than top to bottom as you would be messing up your loop counter value. So, for each of the winners, assume no-removal (line 56), grab the current line (line 57), for each of the 3 indices in the winning line (line 58), get the index on the board (line 60), see if the value stored there is the opponent (line 61), if so, we remove this winner-line as we can’t win if the opponent is already on this line (line 61), and stop checking this line as we already have a remove flagged (line 64). After our inner loop, we see if we have a remove flagged (line 67), and remove that element from our winner subset (line 69). Finally, return our new (possibly smaller) winner array.

CalcWeight()

For each of the subset of winners (line 81), get the winner line (line 83), for each element in this array, get the position/index. Check if the board has a piece or not (line 88). If not, then we can move here, so, see if we can win by playing this position (line 90). If so, then add a weight to this play-board location of, 10 for O, or 5 for X (line 92). That is, if an O will win, then we give this a much higher weight, otherwise what we are doing is blocking X from winning, so give a smaller weight, but higher than just one. If this is not a winning move, then we just add one to this play-board location (line 96).

  • 0 Comments

  • Order by
Want to leave a comment? Login or Register an account!