Tic-Tac-Toe - Part 2

Favourite 14 favourites
Tutorial written by blackhornetOriginally published on 17th, June 2012 - 14 revisions

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).

Comments

0
Kain The Supreme 2,902 rep

Hi,
Beautifull tutorial...
but there is a little bug....
I have tried the on line version that U made... and if I Click over the already assigned "O" It turn from "O" to a "X" and I can win in a easy way!

I fallow your tutorial and re-create leaving the debug visible... and the AI set the position of his move with a delay of one move.

This bug is present only on the AI version, without the AI all works correctly.

In to simple word
The game start
I choose the upper left corner
100
000
000

the Ai choose the midle point

100
020
000

But in the real state the array is
100
000
000
I try to upload an image to show
http://imageshack.us/photo/my-images/818/errorrmp.jpg/

Sunday, December 09, 2012 at 4:53:37 PM
0
Kain The Supreme 2,902 rep

I forgot to said that I was forced to edit this line

from this
"rotatable": true
to this
"rotatable": false

on the edittime.js of your plugin to works on C2!

Sunday, December 09, 2012 at 4:57:05 PM
0
blackhornet 138.1k rep

I've added an addendum with the bug fixes. Thanks @Kain_The_Supreme!

Thursday, December 13, 2012 at 4:12:47 AM
0
Kain The Supreme 2,902 rep

@blackhornet Thanks to You for this bug fix and to help other people to learn C2!!

Thursday, December 13, 2012 at 2:41:59 PM
0
blackhornet 138.1k rep

@Kain_The_Supreme found yet another bug. This was bigger, so I've had to rewrite chunks of page 1. The fix wasn't that hard, but it really mucked up my tutorial. Hopefully this isn't too complicated to follow anymore.

Friday, December 21, 2012 at 5:10:01 AM
0
Kain The Supreme 2,902 rep

Thanks Blackhornet once Again to fix, correct and to share with us °_°

Monday, December 31, 2012 at 1:53:13 PM
0
Kain The Supreme 2,902 rep

U got a msg!
^^'''

Monday, December 31, 2012 at 3:35:36 PM
0
blackhornet 138.1k rep

Yet another bug fixed, introduced with the previous fix. Added totalMoves counter on line 124 of the plugin to make sure the special-case logic is only performed after the very first move. Thanks again to @Kain_The_Supreme.

Sunday, January 20, 2013 at 11:33:00 PM
0
Kain The Supreme 2,902 rep

@blackhornet Was an Honor, good tuts and plugin!

Monday, January 21, 2013 at 2:21:24 PM
0
AbelaNET 14.8k rep

Thanks for sharing

Friday, March 25, 2016 at 9:33:45 PM

Leave a comment

Everyone is welcome to leave their thoughts! Register a new account or login.