Tik-Tak-Toe

[czardas]

It seems that sometimes it doesn't realize it has lost. There are only three possible first turns. Either a corner, an edge or the centre. The response should be according to one of those three possibilities. Although there are nine squares, using rotation reduces the complexity. So if there is only one response to each of the three possibilities then there will only be three possible results after two turns. If you think about it like that, you should be able to simplify the strategy and get it to always win or draw.

Nice GUI BTW.

Edited August 29, 2010 by czardas

[CodyBarrett]

hmm. in every minimax article ive read i havent heard that before. interesting. im trying to implement a recursive function (not this code)to read each move (brute force) and return the first win OR if no wins, then a draw.

I haven't gotten one to work yet though so far ive been trying to implement it so it will always read it, and not by turns.

Are you saying i should make it by turns?

Func Turn1 ()

Func Turn2 ()

Func TurnN ()

Func Turn9 ()

???

[czardas]

I haven't looked into it that deeply. It's just the way I would tackle the problem. Perhaps there will be too many permutations for the idea to be practical. I'm not sure. Of course you don't have to litterally rotate the array. Let's see.

After 2 turns there are 3 possible arrangements and 7 possible responses.

After 4 turns there will be 21 possible outcomes, but some arrangements will transpose by rotation or mirroring.

If I find time later, I might run the idea to it's full conclusion. There's probably a simple mathematical method to figure it out quickly. It still seems that it could be a valid approach.

This is presuming the human goes first. If the computer takes the first turn then it will be slightly different.

Edited August 30, 2010 by czardas

[CodyBarrett]

hmm well ive got the grid valuing and all that.. isn't minimax finding the best and highest value for that player?

3|2|3

2|4|2

3|2|3

thats how i have the values set up right now.

[czardas]

I haven't tested all variations, but I had a look at one scenario yesterday. If the first player starts in a corner, then the second player draws by playing in the centre. I think all other continuations lose by force. If your response is not forced, then the strategy should be to always play the most aggressive move (setting the most problems for your opponent).

It seems that there are not so many lines of play: particularly because many responces are forced. I had a look at the geometric transformation possibilities. After the first player plays in the corner and the second player plays in the centre, there are only four possible continuations. Also; the same positions will occur from different move orders: so the number of possible positions is extremely limited.

Of course all this has been worked out before, but it helps to develop a strategy when you try and solve it yourself. I would generate some automatic responses to the first few turns, and brute force the win if the opponent makes a mistake. I haven't looked into the minimax solution yet.

Here's a summary of the analysis I have so far: (The only defence to the corner attack! )

expandcollapse popup

If the 1st player [O] plays in the corner, then the 2nd player [X] must respond in the centre.

O| | 
 |X| 
 | | 

---------------------------------------------------------------------

The following two continuations lead to a forced draw.

O|O|  Forced draw
 |X| 
 | | 

O| |O Forced draw
 |X| 
 | | 

---------------------------------------------------------------------

If the first player continues in the opposite corner, then the 2nd player must follow up on the side.

O|X|  Forced draw
 |X| 
 | |O

---------------------------------------------------------------------

After the following continuation, the second player optimizes winning chances by playing in the opposite corner to the opponent.

O| | 
 |X|O
 | | 

Now there are three continuations:

O|O|  Forced Draw
 |X|O
 | |X

O| |O Forced Draw
 |X|O
 | |X

O| |  2nd player [X] wins.
O|X|O
 | |X

Other first move responces are analysed below.

If the 2nd player makes any other responce, the 1st player can reach one of the following winning positions:

1st player [O] wins in all cases.

O|X| 
 |O| 
 | | 

O|X| 
 | | 
O| | 

O| |X
 | | 
O| | 

O| | 
 | |X
O| | 

O| | 
 |O|X
 | |

Edited August 31, 2010 by czardas

[Terbinator]

if first == 'computer'://If its the computer's turn first in the game
        move = chooseRandomMoveFromList(board, [1, 3, 7, 9])\\Choose a random corner move.
        if move!= None://If you can move there
            return move//Do it!

        if isSpaceFree(board, 5)://If you can go in the middle
            return 5//Do it!

        return chooseRandomMoveFromList(board, [2, 4, 6, 8])//Otherwise go a random spot not in the middle or on the corners

    else://If player starts
        if isSpaceFree(board, 5)://If you can go in the middle
            return 5//Do it!
        if board[5] == computerLetter://If computer has gone in the middle
            move = chooseRandomMoveFromList(board, [2, 4, 6, 8])
            if move != None:
                return move
            return chooseRandomMoveFromList(board, [1, 3, 7, 9])
        else:
            move = chooseRandomMoveFromList(board, [1, 3, 7, 9])
        if move!= None:
            return move
        
        return chooseRandomMoveFromList(board, [2, 4, 6, 8])

This is some code I made in python for an unbeatable tic tac toe ai. Hope you can work it out . Doesn't always win but it never loses.

[enaiman]

It is not a problem to make one to never lose, I admit it takes a bit of work and a bit of tunning after that but it is possible. Also, to make one to win at the first opportunity that's not too difficult either (not difficult to make the AI take a spot to make 3 in a row instead of taking something random).

The way I did mine was to assign values to the status of each cell, 0 = unoccupied, 1 = player, 5 = AI

What follows is a simple math thing: calculate the value of all 8 possible lines (8 remaining are identical), if it is AI turn, check for a line with a value of 2 (2x1 = 2 player squares) and take the 3rd one. If there is none - look for a line with the value of 10 (2x5 AI squares) and take the 3rd to win. If none of these is possible, look for a line with the value 5 and take another square there.

If the player knows how to play nobody will win, it will be an infinite string of draws.

All you need to do at the begining is to make the AI check the central square first: if empty - to play there, if occupied to take a corner - after that it's easy.

@CodyBarett - sorry mate - haven't seen your PM till today.

[czardas]

To have a game with different levels, it's necessary to develop different playing strategies. The hardest level always goes for the win. The lowest level strategy plays to lose. Intermediate levels miss chances of winning or go intentionally for the draw. To make an engine which plays a variety of responses, it is necessary to analyse all lines of play and build a move order tree.

I consider it to be a good ploy to create a database (or an array) of unique positions, and an algorithm to generate the 2, 4, or 8 possible geometric transformations (depending on the symmetry of the position). Then according to the level set, the engine chooses from a variety of possible continuations. By using stored positions it is possible to eliminate much of the move order tree due to transpositions (when different lines of play reach the same position). Although that doesn't avoid the need to analyse all lines of play for the purpose of building the engine.

Level 1 Computer tries to lose

Level 2 Computer allows you to win

Level 3 Computer plays for a draw

Level 4 Computer plays to win

---

If none of these is possible, look for a line with the value 5 and take another square there.

This particular strategy will sometimes lose:

O| |  2nd player [X] loses
 |O| 
 |X|X

Adding values is an excellent idea, but the search would have to be 4 (or maybe more) plies deep and search for zugzwang type situations.

Edited September 2, 2010 by czardas

[enaiman]

@czardas

This particular strategy will sometimes lose:

Not really:

AI priorities are:

1. try to win (if there are 2 spots in a row already taken by AI, it will play the 3rd regardless what the player is doing)

2. if not 1. then block player to win (play 3rd spot in that row)

3. if not 1. and not 2 then play in a line where there is a spot taken by AI

Well I totally agree that is difficult to make an AI to play by levels; been thinking about that. What was my idea: have only one algorythm - the best - and different levels can be achieved by doing a random roll every turn.

Easy level: roll a random integer between 20 and 30. If the result is a prime number (23 or 29) (20% chances for AI to win) then do the best move Else move at a random spot (80% chances for AI to make a mistake)

Medium level: random 20-30 and do the best move if the number divides by 2 (50% chances for AI to make a mistake)

Hard level: no random rolls, AI will play at its best

I am sure better random ranges and criterias can be found (I just made this up). I agree, this is not the best way to go about making such an AI, but it is the simplest.

[czardas]

@czardas

Not really:

AI priorities are:

1. try to win (if there are 2 spots in a row already taken by AI, it will play the 3rd regardless what the player is doing)

2. if not 1. then block player to win (play 3rd spot in that row)

3. if not 1. and not 2 then play in a line where there is a spot taken by AI

Well I totally agree that is difficult to make an AI to play by levels; been thinking about that. What was my idea: have only one algorythm - the best - and different levels can be achieved by doing a random roll every turn.

Easy level: roll a random integer between 20 and 30. If the result is a prime number (23 or 29) (20% chances for AI to win) then do the best move Else move at a random spot (80% chances for AI to make a mistake)

Medium level: random 20-30 and do the best move if the number divides by 2 (50% chances for AI to make a mistake)

Hard level: no random rolls, AI will play at its best

I am sure better random ranges and criterias can be found (I just made this up). I agree, this is not the best way to go about making such an AI, but it is the simplest.

Hmm, maybe I'm misunderstanding something about the last step. Suppose human starts in the centre and AI follows up in the corner. If human then plays in the opposite corner, we end up with three occupied spots along the diagonal. There are now two lines where there is a spot taken by AI, and two spots available on each line. Which one does the AI choose?

O| | 
 |O| 
 | |X

I do like simple code, however I have to admit that I find it an interesting challenge to investigate this in some detail. The idea that there may be so many ways to draw, or lose, and to be able to control how the engine behaves as a player. Planning a losing strategy for the lowest level will require a completely different approach. I can just imagine a situation where the engine is trying to lose to someone who doesn't take advantage of the fact. Is it ever possible to force your opponent to win? I have no idea!

Suicide Noughts and Crosses - what a concept!

Edited September 3, 2010 by czardas

[enaiman]

@czardas

That was an interesting situation and it is a particular one because I have provided a separate case for it. I admit I'm too lazy/busy atm to go over my code so what I did was to try my script.

It will always play like this:

0| |x
 |0|
 | |x

or

0| |
 |0|
x| |x

So it fill force a draw in this case. You can see for yourself how my script is behaving (the link is in my sig).

Not the prettiest/cleanest script you've seen

I can just imagine a situation where the engine is trying to lose to someone who doesn't take advantage of the fact. Is it ever possible to force your opponent to win?

what a twisted mind you have

Guess it is possible to "force the opponent to win" by limiting his options. Not sure at this point and it will be interresting to investigate then we'll have an opposite game called "try not to win", similar play rules but different play style wow

Edited September 3, 2010 by enaiman

[czardas]

@enaiman

Now it makes more sense. Nice program by the way. I looked at it this morning. It never loses.

I also don't have too much time to spend on this right now, but analyzing tic-tac-toe is a good exercise. The play to lose strategy could turn out to be a little bit tricky. I think 'suicide tic-tac-toe' would be a nice engine feature to have. Firstly I intend to map out all available move orders and categorize the resulting positions into several types. Though I will have to think how to do that and it will probably take me a bit of time. The list will look something like this:

Forced Wins with best play

Forced Draws with best play

Automatic Wins regardless of continuation

Automatic Draws regardless of continuation

Number of possible continuations (strongest to weakest)

I have made a bit of a start already. I created a tool to eliminate duplicate positions and their geometric equivalents. Once this is done it should be easy to analyze the few remaining unique situations that can occur during a game. As soon as I have some results worth mentioning, I'll post them here.

Edited September 3, 2010 by czardas

[CodyBarrett]

hmm i've been looking into minimax and its algorithm for making a game tree and picking the best possible starting off play and the best next move until it eventually wins, or if no win case scenario it loses. i understand how the theory works tanks to some fairly in-depth articles and diagrams on the internet. but i have troubles implementing a recursive function based on this theory.

but instead of minimax you guys are suggesting a strategy with 2 in a row go for it.. and blocking if its 2 in a row for the human or only 1 on each line. im not sure which would be best to do...?

minimax VS built in strategy

[czardas]

Immediate blocking is obviously forced. However I am not convinced that it is always advisable to go for a single winning line. Instead you should try to create a situation where you have two or more winning lines on the next turn. Then your opponent will not be able to defend all of the threats. The tricky part is when the continuation is not forced and there are no clear victories.

Analysis Update

There is no need to analyse forced continuations. Nor is it necessary to analyse any deeper than six turns. With more than six turns, continuations are either forced or the game is an automatic draw. After seven turns there are five unique situations where a draw is unavoidable. You can mirror the positions, flip them or rotate them to create new shapes. It clearly makes no difference to the outcome of the game. Place an x on either of the two empty spots, and the game will end as a draw.

Drawn regardless of continuation.
x to play next

o|x|o
x| |o
 |o|x

o|x|o
o|x|
x|o|

o|x|o
o| |
x|o|x

o|x|o
 |o|
x|o|x

o|x|
x|o|o
 |o|x

As a point of interest: there are also two positions which are automatically drawn after six turns.

Drawn regardless of continuation.

o|x|o
 | |
x|o|x

o|x| 
x| |o
 |o|x

These are some of the positions that the AI should avoid if it's purpose is to try and win the game. I'm slowly getting my head around this. Soon I'll have it nailed, and then you can decide whether a complete analysis of tic-tac-toe will assist you.

Edited September 5, 2010 by czardas

[enaiman]

@czardas

I can see you are doing a "serious" job about this game and I respect that. I am looking forward to see your progress.

The script I made didn't have such a strong algorythm and analisys behind; I simply thought to make ascript which will win (if possible) or draw (if forced) but NEVER lose

It was easy for me to do it because of the small postion numbers and the fact that so many combinations would be simmetrical. All this left not so many positions to take care of.

It was also easy to make another script Paper/Scissor/Rock. I haven't tested it too much but it was working fine; I ve considered that anything above 33% random chance to win is a sign of a successful AI.

But these two were simple games; any other game, more complicated and I'm out

[czardas]

I have to admit that this is a tougher project than I at first thought. I have analysed 90 percent of all possible positions, and whittled down the number of variants to just 70 important positions. This number only includes positions where good moves win, or bad moves lose by force. These 70 positions can be stored as 'book' variations and accessed easily and quickly for evaluation. One thing I have learned is that not all draws are equal. Some drawn positions have more chances for the opponent to make a mistake. We can add weight values to these positions by subtracting the number of losing lines from the number of winning lines.

After some consideration (and with needing a rest from looking at so many tic tac toe grids), I decided to try and build a playing engine which analyses the position from an AI perspective. I thought perhaps this would be more in keeping with what CodyBarrett is looking for. Although my analysis of positions has helped me to come up with a strategy for the engine, there is nothing here that hasn't already been done before. I also looked into minimax (just a bit). It seems to be based on positional blocking strategy to avoid losing. I didn't look into it any deeper than that.

There is some good information in this wiki article: http://en.wikipedia.org/wiki/Tic-tac-toe Scroll down to the heading where it says Strategy. Further up the page it also says:

It is straightforward to write a computer program to play tic-tac-toe perfectly.

Well for some people maybe! I personally found it quite a demanding challenge. And my program started turning into a monster script, which I found difficult to control. I will most probably rewrite parts of it at some stage. Any suggestions for improvement are most welcome. The comments in the code are mainly for me to follow the thread.

TTTEngine.au3

expandcollapse popup

#include <Array.au3>

; #FUNCTION# ====================================================================================================================
; Name...........: _ScanGrid
; Description ...: Returns a hash table containing information about occupied rows, columns and diagonals.
; Syntax.........: _ScanGrid(ByRef $asHashT, $asGrid)
; Parameters ....: $asGrid - A two dimensional array representing the current grid pouition.
; Return values .: Returns the hash table as a two dimensional array.
; Author ........: Czardas
; Modified.......: -
; Remarks .......: -
; Related .......: -
; Link ..........: -
; Example .......: Yes
; ===============================================================================================================================

Func _ScanGrid(ByRef $asHashT, $asGrid)
    For $i = 0 To 2 ; Clear old values.
        For $j = 0 To 2
            $asHashT[$i][$j] = ""
        Next
    Next
    For $i = 0 To 2
        For $j = 0 To 2
            $asHashT[0][$i] &= $asGrid[$i][$j] ; Rows
            $asHashT[1][$i] &= $asGrid[$j][$i] ; Columns
        Next
        $asHashT[2][0] &= $asGrid[$i][$i] ; Top left to bottom right
        $asHashT[2][1] &= $asGrid[$i][2 - $i] ; Top right to bottom left
    Next
EndFunc

; #FUNCTION# ====================================================================================================================
; Name...........: _TesrForWin
; Description ...: Searches for an instant win along rows, columns or diagonals.
; Syntax.........: _TesrForWin(ByRef $aiCoord, $asGrid, $asHashT, $sPlyr, ByRef $bRtn)
; Parameters ....: $asGrid - The current grid pouition.
                 ; $asHashT - Hash table.
                 ; $sPlyr - The player threatening to win in the current position.
; Return values .: $aiCoord - Success: returns an array of the winning coordinates.
                 ; $bRtn - A winning move exists (Returns True or False).
; Author ........: Czardas
; Modified.......: -
; Remarks .......: -
; Related .......: -
; Link ..........: -
; Example .......: Yes
; ===============================================================================================================================

Func _TesrForWin(ByRef $aiCoord, $asGrid, $asHashT, $sPlyr, ByRef $bRtn)
    $bRtn = False
    For $d = 0 To 1 ; Test for an immediate win along the diagonals.
        If $asHashT[2][$d] = $sPlyr & $sPlyr Then
            For $i = 0 To 2
                $j = $i + $d*(2 - 2*$i)
                If $asGrid[$i][$j] = "" Then
                    $aiCoord[0] = $i
                    $aiCoord[1] = $j
                    $bRtn = True
                    ExitLoop
                EndIf
            Next
        EndIf
    Next
    For $e = 0 To 1 ; Test for an immediate win along the rows and columns.
        For $c = 0 To 2
            If $asHashT[$e][$c] = $sPlyr & $sPlyr Then
                For $i = 0 To 2
                    If $e = 0 And $asGrid[$c][$i] = "" Then
                        $aiCoord[0] = $c
                        $aiCoord[1] = $i
                        $bRtn = True
                        ExitLoop
                    ElseIf $e = 1 And $asGrid[$i][$c] = "" Then
                        $aiCoord[0] = $i
                        $aiCoord[1] = $c
                        $bRtn = True
                        ExitLoop
                    EndIf
                Next
            EndIf
        Next
    Next
EndFunc

; #FUNCTION# ====================================================================================================================
; Name...........: _TestForFork
; Description ...: Searches for a fork threat.
; Syntax.........: _TestForFork(ByRef $aiCoord, $asGrid, $asHashT, $sPlyr, ByRef $bRtn)
; Parameters ....: $asGrid - The current grid pouition.
                 ; $asHashT - Hash table.
                 ; $sPlyr - The player threatening a fork in the current position.
; Return values .: $aiCoord - Success: returns an array of the fork coordinates.
                 ; $bRtn - A fork threat exists (Returns True or False).
; Author ........: Czardas
; Modified.......: -
; Remarks .......: -
; Related .......: -
; Link ..........: -
; Example .......: Yes
; ===============================================================================================================================

Func _TestForFork(ByRef $aiCoord, $asGrid, $asHashT, $sPlyr, ByRef $bRtn)
    $bRtn = False
    For $d = 0 To 1
        If $asHashT[2][$d] = $sPlyr Then
            If $d = 0 And $asHashT[2][1] = $sPlyr Then ; Test diagonals against each other.
                If $asGrid[1][1] = "" Then
                    $aiCoord[0] = 1
                    $aiCoord[1] = 1
                    $bRtn = True
                    ExitLoop
                EndIf
            EndIf
            For $c = 0 To 2
                If $asHashT[0][$c] = $sPlyr Then ; Test diagonals against rows.
                    For $i = 0 To 2
                        $j = $i + $d*(2 - 2*$i)
                        If $asGrid[$c][$i] <> $sPlyr And $c = $j Then
                            $aiCoord[0] = $j
                            $aiCoord[1] = $i
                            $bRtn = True
                            ExitLoop 2
                        EndIf
                    Next
                ElseIf $asHashT[1][$c] = $sPlyr Then ; Test diagonals against columns.
                    For $i = 0 To 2
                        $j = $i + $d*(2 - 2*$i)
                        If $asGrid[$i][$c] <> $sPlyr And $c = $j Then
                            $aiCoord[0] = $i
                            $aiCoord[1] = $j
                            $bRtn = True
                            ExitLoop 2
                        EndIf
                    Next
                EndIf
            Next
        EndIf
    Next
    If $bRtn = False Then
        For $c = 0 To 2
            If $asHashT[0][$c] = $sPlyr Then ; Test rows against columns.
                For $i = 0 To 2
                    If $asGrid[$c][$i] <> $sPlyr And $asHashT[1][$i] = $sPlyr Then
                        $aiCoord[0] = $c
                        $aiCoord[1] = $i
                        $bRtn = True
                    EndIf
                Next
            EndIf
        Next
    EndIf
EndFunc

; #FUNCTION# ====================================================================================================================
; Name...........: _ForcePlay
; Description ...: Searches for forced play continuations.
; Syntax.........: _ForcePlay(ByRef $aiCoord, $asGrid, $asHashT, $sPlyr, ByRef $bRtn)
; Parameters ....: $asGrid - The current grid pouition.
                 ; $asHashT - Hash table.
                 ; $sPlyr - The player who's turn it is to move.
; Return values .: $aiCoord - Success: returns an array of coordinates leading to forced play.
                 ; $bRtn -  Forced continuations exist. (Returns True or False).
; Author ........: Czardas
; Modified.......: -
; Remarks .......: This is only used when the engine finds no immediate wins or winning forks.
; Related .......: -
; Link ..........: -
; Example .......: Yes
; ===============================================================================================================================

Func _ForcePlay(ByRef $aiCoord, $asGrid, $asHashT, $sPlyr, ByRef $bRtn)
    $bRtn = False
    Local $iCount = 0, $bDuplication = False
    For $d = 0 To 1 ; Try to force play along the daiagonals
        If $asHashT[2][$d] = $sPlyr Then
            For $i = 0 To 2
                $j = $i + $d*(2 - 2*$i)
                If $asGrid[$i][$j] = "" Then
                    For $k = 0 To UBound($aiCoord) -1
                        If UBound($aiCoord) > 1 And $aiCoord[$k][0] = $i And $aiCoord[$k][1] = $j Then
                            $bDuplication = True
                        EndIf
                    Next
                    If $bDuplication = False Then
                        $iCount += 1
                        ReDim $aiCoord[$iCount +1][2]
                        $aiCoord[$iCount][0] = $i
                        $aiCoord[$iCount][1] = $j
                    Else
                        $bDuplication = False
                    EndIf
                EndIf
            Next
        EndIf
    Next
    For $e = 0 To 1 ; Try to force play along a row or column.
        For $c = 0 To 2
            If $asHashT[$e][$c] = $sPlyr Then
                For $i = 0 To 2
                    If $e = 0 And $asGrid[$c][$i] = "" Then
                        For $k = 0 To UBound($aiCoord) -1
                            If UBound($aiCoord) > 1 And $aiCoord[$k][0] = $c And $aiCoord[$k][1] = $i Then
                                $bDuplication = True
                            EndIf
                        Next
                        If $bDuplication = False Then
                            $iCount += 1
                            ReDim $aiCoord[$iCount +1][2]
                            $aiCoord[$iCount][0] = $c
                            $aiCoord[$iCount][1] = $i
                        Else
                            $bDuplication = False
                        EndIf
                    ElseIf $e = 1 And $asGrid[$i][$c] = "" Then
                        For $k = 0 To UBound($aiCoord) -1
                            If UBound($aiCoord) > 1 And $aiCoord[$k][0] = $i And $aiCoord[$k][1] = $c Then
                                $bDuplication = True
                            EndIf
                        Next
                        If $bDuplication = False Then
                            $iCount += 1
                            ReDim $aiCoord[$iCount +1][2]
                            $aiCoord[$iCount][0] = $i
                            $aiCoord[$iCount][1] = $c
                        Else
                            $bDuplication = False
                        EndIf
                    EndIf
                Next
            EndIf
        Next
    Next
    If UBound($aiCoord) > 1 Then $bRtn = True
EndFunc

; #FUNCTION# ====================================================================================================================
; Name...........: _BlockCounterPlay
; Description ...: Searches ways to block lines.
; Syntax.........: _BlockCounterPlay(ByRef $aiCoord, $asGrid, $asHashT, $sPlyr, ByRef $bRtn)
; Parameters ....: $asGrid - The current grid pouition.
                 ; $asHashT - Hash table.
                 ; $sPlyr - The player who's turn it is to move.
; Return values .: $aiCoord - Success: returns an array of coordinates where counterplay can be blocked.
                 ; $bRtn -  Lines of counterplay can be blocked. (Returns True or False).
; Author ........: Czardas
; Modified.......: -
; Remarks .......: This function is only used when the engine fails to find winning tactics.
; Related .......: -
; Link ..........: -
; Example .......: Yes
; ===============================================================================================================================

Func _BlockCounterPlay(ByRef $aiCoord, $asGrid, $asHashT, $sPlyr, ByRef $bRtn)
    $bRtn = False
    For $i = 0 To 2
        For $j = 0 To 2
            If $i = 2 And $j = 2 Then ExitLoop 2 ; This field is empty.
            If StringInStr($asHashT[$i][$j], $sPlyr) = 0 Then ; Lines can be blocked.
                $bRtn = True
                ExitLoop 2
            EndIf
        Next
    Next
    If $bRtn = True Then
        Local $asTempGrid[3][3], $iCount, $iBlocks = 1
        For $r = 0 To 2
            For $c = 0 To 2
                $asTempGrid = $asGrid
                $iCount = 0
                If $asGrid[$r][$c] = "" Then
                    $asTempGrid[$r][$c] = $sPlyr
                    Local $asTempHT[3][3]
                    _ScanGrid($asTempHT, $asTempGrid) ; To test each new position for lines available to the opponent.
                    For $i = 0 To 2
                        For $j = 0 To 2
                            If $i = 2 And $j = 2 Then
                                If $iCount > 0 Then
                                    $aiCoord[$iBlocks][0] = $r
                                    $aiCoord[$iBlocks][1] = $c
                                    $aiCoord[$iBlocks][2] = $iCount
                                    $iBlocks += 1
                                EndIf
                                ExitLoop 2
                            EndIf
                            If StringInStr($asTempHT[$i][$j], $sPlyr) = 0 Then
                                $iCount += 1
                            EndIf
                        Next
                    Next
                EndIf
            Next
        Next
        $aiCoord[0][0] = $iBlocks - 1
        ReDim $aiCoord[$iBlocks][3]
        _ArraySort($aiCoord, 0, 1, 0, 2) ; The most effective blocks will be tested first.
    EndIf
EndFunc

; #FUNCTION# ====================================================================================================================
; Name...........: _RunTTTEngine
; Description ...: Runs the engine and searches for any winning line.
; Syntax.........: _RunTTTEngine(ByRef $asTTT_Grid, $sAI_Engine, ByRef $b_GameOver, ByRef $v_Result)
; Parameters ....: $asTTT_Grid - The Tic-Tac-Toe grid in which the game takes place.
                 ; $sAI_Engine - Engine ID (either equals o or x).
; Return values .: $asTTT_Grid - Success: returns the new position after the computer has made a move.
                 ; $b_GameOver - The game has ended (Returns True or False).
                 ; $v_Result - Returns the winning player (either o or x), or -1 in the case of a draw.
; Author ........: Czardas
; Modified.......: -
; Remarks .......: -
; Related .......: -
; Link ..........: -
; Example .......: Yes
; Notes .........: This current engine version only searches forced lines up to 6 plies.
; ===============================================================================================================================

Func _RunTTTEngine(ByRef $asTTT_Grid, $sAI_Engine, ByRef $b_GameOver, ByRef $v_Result)
    Local $as_HashTable[3][3], $i_Move = 1
    _ScanGrid($as_HashTable, $asTTT_Grid)
    For $c = 0 To 2
        $i_Move += StringLen($as_HashTable[0][$c]) ; Get move number.
    Next
    _IsFinished($as_HashTable, $v_Result, $b_GameOver) ; Test if the game has ended.
    If $b_GameOver = False Then
        Local $ai_Coordinates[2], $b_Return
        _TesrForWin($ai_Coordinates, $asTTT_Grid, $as_HashTable, $sAI_Engine, $b_Return) ; Test for an instant win.
        If $b_Return = False Then
            Local $s_Opponent
            If $sAI_Engine = "o" Then
                $s_Opponent = "x"
            Else
                $s_Opponent = "o"
            EndIf
            _TesrForWin($ai_Coordinates, $asTTT_Grid, $as_HashTable, $s_Opponent, $b_Return) ; Test for forced blocks.
            If $b_Return = False Then
                _TestForFork($ai_Coordinates, $asTTT_Grid, $as_HashTable, $sAI_Engine, $b_Return) ; Test for a winning fork.
                If $b_Return = False Then ; Try forcing play before testing for threats
                    Local $as_TempGrid[3][3], $as_TempHT[3][3], $ai_Drawn[10 -$i_Move][2], $i_DrawResults = 0, $b_ContinueAnalysis = True
                    If $i_Move > 3 And $i_Move < 7 Then
                        Local $ai_Forced[1][2]
                        _ForcePlay($ai_Forced, $asTTT_Grid, $as_HashTable, $sAI_Engine, $b_Return)
                        If $b_Return = True Then
                            For $a = 1 To UBound($ai_Forced) -1
                                $as_TempGrid = $asTTT_Grid
                                _UpdateTempGrid($as_TempGrid, $ai_Forced[$a][0], $ai_Forced[$a][1], $as_TempHT, $sAI_Engine) ; Force Play - Move 4 (or 5)
                                _TesrForWin($ai_Coordinates, $as_TempGrid, $as_TempHT, $sAI_Engine, $b_Return)
                                _UpdateTempGrid($as_TempGrid, $ai_Coordinates[0], $ai_Coordinates[1], $as_TempHT, $s_Opponent) ; Forced Response - Move 5 (or 6)
                                _TesrForWin($ai_Coordinates, $as_TempGrid, $as_TempHT, $s_Opponent, $b_Return)
                                If $b_Return = True Then ; Forced play continues => Forced move must be a fork to win.
                                    Local $iY_Coord = $ai_Coordinates[0], $iX_Coord = $ai_Coordinates[1]
                                    _TestForFork($ai_Coordinates, $as_TempGrid, $as_TempHT, $sAI_Engine, $b_Return)
                                    _UpdateTempGrid($as_TempGrid, $ai_Coordinates[0], $ai_Coordinates[1], $as_TempHT, $sAI_Engine)  ; Forced Defence - Move 6 (or 7)
                                    If $b_Return = True And $ai_Coordinates[0] = $iY_Coord And $ai_Coordinates[1] = $iX_Coord Then ; Fork coordinates == Forced Coordinates.
                                        _TesrForWin($ai_Coordinates, $as_TempGrid, $as_TempHT, $s_Opponent, $b_Return)
                                        If $b_Return = False Then ; Forced play strategy wins!
                                            $asTTT_Grid[$ai_Forced[$a][0]][$ai_Forced[$a][1]] = $sAI_Engine ; Select this continuation.
                                            $b_ContinueAnalysis = False
                                            ExitLoop
                                        EndIf
                                    Else ; You can't win from now on.
                                        _TesrForWin($ai_Coordinates, $as_TempGrid, $as_TempHT, $s_Opponent, $b_Return)
                                        If $b_Return = False Then
                                            _TestForFork($ai_Coordinates, $as_TempGrid, $as_TempHT, $s_Opponent, $b_Return)
                                            If $b_Return = False Then
                                                $i_DrawResults += 1
                                                _ListDrawnLine($ai_Drawn, $ai_Forced[$a][0], $ai_Forced[$a][1], $i_DrawResults)
                                            EndIf
                                        EndIf
                                    EndIf
                                Else ; Move 6 is not forced and niether player has an immediate win.
                                    _TestForFork($ai_Coordinates, $as_TempGrid, $as_TempHT, $sAI_Engine, $b_Return)
                                    If $b_Return = True Then ; The engine will win next move.
                                        $asTTT_Grid[$ai_Forced[$a][0]][$ai_Forced[$a][1]] = $sAI_Engine ; Select this continuation.
                                        $b_ContinueAnalysis = False
                                        ExitLoop
                                    Else ; The engine can't win from now on.
                                        If $i_Move > 4 Then
                                            $i_DrawResults += 1
                                            _ListDrawnLine($ai_Drawn, $ai_Forced[$a][0], $ai_Forced[$a][1], $i_DrawResults)
                                        Else ; The opponent may still have a fork.
                                            Local $ai_Options[4][2], $as_TestGrid[3][3]
                                            _ReturnOptions($ai_Options, $as_TempGrid)
                                            For $b = 0 To 3
                                                $as_TestGrid = $as_TempGrid
                                                _UpdateTempGrid($as_TestGrid, $ai_Options[$b][0], $ai_Options[$b][1], $as_TempHT, $sAI_Engine)
                                                _TestForFork($ai_Coordinates, $as_TestGrid, $as_TempHT, $s_Opponent, $b_Return)
                                                If $b_Return = False Then ; A draw can be forced in at least one variation.
                                                    $i_DrawResults += 1
                                                    _ListDrawnLine($ai_Drawn, $ai_Forced[$a][0], $ai_Forced[$a][1], $i_DrawResults)
                                                    ExitLoop
                                                EndIf
                                            Next
                                        EndIf
                                    EndIf
                                EndIf
                            Next
                        EndIf
                    EndIf
                    If $b_ContinueAnalysis = True Then
                        Local $ai_Blocks[11 - $i_Move][3]
                        _BlockCounterPlay($ai_Blocks, $asTTT_Grid, $as_HashTable, $sAI_Engine, $b_Return)
                        If $b_Return = True Then
                            _TestForFork($ai_Coordinates, $asTTT_Grid, $as_HashTable, $s_Opponent, $b_Return) ; Test for a fork threat.
                            If $b_Return = True Then ; The fork threat needs to be parried.
                                If $i_DrawResults > 0 Then
                                    $asTTT_Grid[$ai_Drawn[1][0]][$ai_Drawn[1][1]] = $sAI_Engine ; Force Play.
                                    $b_ContinueAnalysis = False
                                Else
                                    For $a = 1 To $ai_Blocks[0][0]
                                        $as_TempGrid = $asTTT_Grid
                                        _UpdateTempGrid($as_TempGrid, $ai_Blocks[$a][0], $ai_Blocks[$a][1], $as_TempHT, $sAI_Engine)
                                        _TestForFork($ai_Coordinates, $as_TempGrid, $as_TempHT, $s_Opponent, $b_Return)
                                        If $b_Return = False Then
                                            $asTTT_Grid[$ai_Blocks[$a][0]][$ai_Blocks[$a][1]] = $sAI_Engine; Select this continuation.
                                            $b_ContinueAnalysis = False
                                            ExitLoop
                                        EndIf
                                    Next
                                EndIf
                                If $b_ContinueAnalysis = True Then ; The position was already lost to begin with.
                                    $asTTT_Grid[$ai_Blocks[1][0]][$ai_Blocks[1][1]] = $sAI_Engine ; The engine has blocked as many lines as possible.
                                EndIf
                            Else ; Block as many lines as possible.
                                If $ai_Blocks[0][0] > 0 Then
                                    $asTTT_Grid[$ai_Blocks[1][0]][$ai_Blocks[1][1]] = $sAI_Engine
                                Else ; There are no threats or winning tactics.
                                    Local $ai_Options[10 -$i_Move][2]
                                    _ReturnOptions($ai_Options, $asTTT_Grid)
                                    $asTTT_Grid[$ai_Options[0][0]][$ai_Options[0][1]] = $sAI_Engine ; Take the first available option.
                                EndIf
                            EndIf
                        Else ; You have already blocked all threats and there are no more chances to force a win.
                            Local $ai_Options[10 -$i_Move][2]
                            _ReturnOptions($ai_Options, $asTTT_Grid)
                            $asTTT_Grid[$ai_Options[0][0]][$ai_Options[0][1]] = $sAI_Engine ; Take the first available option.
                        EndIf
                    EndIf
                Else
                    $asTTT_Grid[$ai_Coordinates[0]][$ai_Coordinates[1]] = $sAI_Engine ; Wins next move.
                EndIf
            Else ; You must parry the immediate threat.
                $asTTT_Grid[$ai_Coordinates[0]][$ai_Coordinates[1]] = $sAI_Engine ; The engine has blocked the opponent.
            EndIf
        Else
            $asTTT_Grid[$ai_Coordinates[0]][$ai_Coordinates[1]] = $sAI_Engine ; => Wins immediately
            $b_GameOver = True
            $v_Result = $sAI_Engine
        EndIf
    EndIf
    If $i_Move = 9 Then
        $b_GameOver = True
    EndIf
EndFunc

; #FUNCTION# ====================================================================================================================
; Name...........: _UpdateTempGrid
; Description ...: Updates a temporary playing grid used to test variations.
; Syntax.........: _UpdateTempGrid(ByRef $asGrid, $iRow, $iCol, ByRef $asHashT, $sPlyr)
; Parameters ....: $asGrid - The original grid pouition.
                 ; $iRow - The row of the selected grid coordinates.
                 ; $iCol - The column of the selected grid coordinates.
                 ; $sPlyr - The player who's turn it is to move.
; Return values .: $asGrid - Success: returns the new position for analysis.
                 ; $asHashT - Success: returns the hash table associated with the new position.
; Author ........: Czardas
; Modified.......: -
; Remarks .......: -
; Related .......: -
; Link ..........: -
; Example .......: Yes
; ===============================================================================================================================

Func _UpdateTempGrid(ByRef $asGrid, $iRow, $iCol, ByRef $asHashT, $sPlyr)
    $asGrid[$iRow][$iCol] = $sPlyr
    _ScanGrid($asHashT, $asGrid)
EndFunc

; #FUNCTION# ====================================================================================================================
; Name...........: _ReturnOptions
; Description ...: Returns all possible continuation coordinates.
; Syntax.........: _ReturnOptions(ByRef $aiCoord, $asGrid)
; Parameters ....: $asGrid - The grid pouition.
; Return values .: $aiCoord - Success: returns an array of all possible continuation coordinates.
; Author ........: Czardas
; Modified.......: -
; Remarks .......: -
; Related .......: -
; Link ..........: -
; Example .......: Yes
; ===============================================================================================================================

Func _ReturnOptions(ByRef $aiCoord, $asGrid)
    Local $iCount = 0
    For $i = 0 To 2
        For $j = 0 To 2
            If $asGrid[$i][$j] = "" Then
                $aiCoord[$iCount][0] = $i
                $aiCoord[$iCount][1] = $j
                $iCount += 1
            EndIf
        Next
    Next
EndFunc

; #FUNCTION# ====================================================================================================================
; Name...........: _ListDrawnLine
; Description ...: Logs drawn variations encountered during the analysis.
; Syntax.........: _ListDrawnLine(ByRef $aiCoord, $iRow, $iCol, $iDraws)
; Parameters ....: $iDraws - The number of drawn lines encountered.
                 ; $iRow - The row of the drawn coordinates.
                 ; $iCol - The column of the drawn coordinates.
; Return values .: $aiCoord - Success: updates the array of drawn variations.
; Author ........: Czardas
; Modified.......: -
; Remarks .......: -
; Related .......: -
; Link ..........: -
; Example .......: Yes
; ===============================================================================================================================

Func _ListDrawnLine(ByRef $aiCoord, $iRow, $iCol, $iDraws)
    $aiCoord[$iDraws][0] = $iRow
    $aiCoord[$iDraws][1] = $iCol
EndFunc

; #FUNCTION# ====================================================================================================================
; Name...........: _IsFinished
; Description ...: Tests if the game is at an end.
; Syntax.........: _IsFinished($asHashT, ByRef $sPlyr, ByRef $bRtn)
; Parameters ....: $asHashT - The hash table representing the game grid.
; Return values .: $bRtn - The game has ended (Returns True or False).
                 ; $sPlyr - Returns the winning player (either o or x), or -1 in the case of a draw.
; Author ........: Czardas
; Modified.......: -
; Remarks .......: -
; Related .......: -
; Link ..........: -
; Example .......: Yes
; ===============================================================================================================================

Func _IsFinished($asHashT, ByRef $sPlyr, ByRef $bRtn)
    $bRtn = True
    $sPlyr = -1
    For $c = 0 To 2
        If StringLen($asHashT[0][$c]) < 3 Then
            $bRtn = False
            ExitLoop
        EndIf
    Next
    For $d = 0 To 1 ; Test diagonals
        If $asHashT[2][$d] = "xxx" Then
            $sPlyr = "x"
            $bRtn = True
            ExitLoop
        ElseIf $asHashT[2][$d] = "ooo" Then
            $sPlyr = "o"
            $bRtn = True
            ExitLoop
        EndIf
    Next
    If $sPlyr = -1 Then
        For $e = 0 To 1 ; Test rows and columns.
            For $c = 0 To 2
                If $asHashT[$e][$c] = "xxx" Then
                    $sPlyr = "x"
                    $bRtn = True
                    ExitLoop 2
                ElseIf $asHashT[$e][$c] = "ooo" Then
                    $sPlyr = "o"
                    $bRtn = True
                    ExitLoop 2
                EndIf
            Next
        Next
    EndIf
EndFunc

Example

#include 'TTTEngine.au3'

Local $sComputer = "x", $vWinner = -1, $bGameOver = False
Local $aStic_tac_toe[3][3] = [["","",""],["","",""],["","",""]] ; This array may only contain x's or o's. Don't use spaces or the engine won't work.

_RunTTTEngine($aStic_tac_toe, $sComputer, $bGameOver, $vWinner)

If $bGameOver = False Then
    $sMessage = "What's your next move?"
Else
    If $vWinner = -1 Then
        $sMessage = "The game is a draw!"
    Else
        $sMessage = "The winner is: "& $vWinner
    EndIf
EndIf

_ArrayDisplay($aStic_tac_toe, $sMessage)

I can't guarantee that the code is bug free, though it seems to be working and I haven't been able to beat it. If anyone finds a bug, please let me know. I will publish the results of the position analysis shortly.

Edited September 18, 2010 by czardas

[enaiman]

@czardas

Impressive work well done.

I had a look at your code (just at the functions and descriptions) and it is extremely well written.

You have several functions which can be IMO shortened, even combined into an unique function.

ScanGrid, TestForWin, TestForFork

If you assign values to fields: 0 for unoccupied, 1 for player, 5 for computer, you can easily check the status of each line/column/diagonal by computing the sum of the values: 2 = 2-in-a-row for player, 10 = 2-in-a-row for computer, 6= 1 player, 1 computer ... not many situations possible. This value can tell AI where to play next: "10" = play the 3rd and win, 2 = play the 3rd to block ... and so on. Here is where a deep analisys comes handy.

To come back to my idea, by making a single function to do this check, you can see right there if there is a win/lose situation and this function needs to be done every AI turn.

I'm only offering my suggestion

[czardas]

Thanks for your approval and suggestions.

Yes I did think of combining those functions, but seeing as I am sometimes only interested in either the win or the fork, for one player or the other, it seems that the engine would be doing unecessary analysis if I were to combine them into one function. Though there are probably ways around that. I do agree that there must be several ways of simplifying at least part of the code, and most likely several ways improve the algorithm too. However, I am happy with the string comparison approach I have chosen. Perhaps because it is easier for me to envisage. If I were to use number codes then perhaps it would simplify some of the script, I'm not entirely sure. I haven't really given it enough thought.

I do know that I prefer to keep empty array elements as empty strings, rather than giving them a value of zero. This is partly because of the string notation system I am using to store positions in the analysis I am doing. Searching for strings is faster than searching through individual elements of an array. Numbers within the strings represent the value of a continuation from the position. Winning continuation = 1 (Draw = 0 ...Not included in the actual notation) and losing continuation = -1. The string notation can be easily turned into an array using stringSplit. For example the following grid has a value of -2. Although the computer won't select a losing line, a himan player might.

Notation        Map Reference
|x|,||x,o||     1||-1,-1|-1|,|-1|1

Grid            Continuations
 |x|            W| |L
 | |x           L|L|
o| |             |L|W

I have already written some functions to expand and manipulate these expressions, and I am happy so far. Perhaps I'll change the notation, but I want to store the information in as compressed form as possible. There are 70 such positions to store.

Edited September 18, 2010 by czardas

[enaiman]

I can see an advatage of using numbers over strings:

strings: 0xx, x0x, xx0 (3 different strings) will have same numerical value "7"

It's OK, I believe the string approach works better with your script because you took that script one step further

I'll be watchin' ya

[czardas]

I'll have some more soon.

Edit

Another example where the engine plays against itself.

#include 'TTTEngine.au3'

Local $asPlayers[2] = ["o","x"], $vWinner = -1, $bGameOver, $a = 0, $b = -1
Local $aSGrid[3][3] = [["","",""],["","",""],["","",""]]

For $i = 0 To 7
    _RunTTTEngine($aSGrid, $asPlayers[$a], $bGameOver, $vWinner)
    _ArrayDisplay($aSGrid, "Resume play")
    $b *= -1
    $a += $b
Next
_RunTTTEngine($aSGrid, $asPlayers[$a], $bGameOver, $vWinner)
_ArrayDisplay($aSGrid, "And the winner is: " & $vWinner)

Of course it's always the same draw at the end.

I think I might try and build an engine for Fox and Hounds next. You would expect this kind of thing to be not too difficult. We'll see!

Update

Whilst running tests I have discovered a bug in the above engine. This bug has now been fixed. The function _RunTTTEngine could still probably do with a few tweaks.

Edited September 16, 2010 by czardas