Tik-Tak-Toe

[czardas]

Here are the results as promised. There are 70 unique situations where a player can either win or lose the game (not including immediate wins). These grids can be rotated and mirrored to produce 477 grid orientations. To view all 477 grids run the following code in SciTE Editor.

expandcollapse popup

#include <Array.au3>
#include <String.au3>

Local $av_BookLines[70][2] = _
[["x||,||,||","|L|L,L|D|L,L|L|L"],["|x|,||,||","D||D,L|D|L,L|D|L"],["||,|x|,||","D|L|D,L||L,D|L|D"],["o|x|,||,||","||D,W|W|D,W|D|D"], _
["o||x,||,||","|L|,W|D|D,W|D|W"],["o||,||x,||","|L|W,D|W|,W|D|D"],["o||,||,||x","|L|W,L|D|D,W|D|"],["x|o|,||,||","||L,D|D|L,D|L|D"], _
["|o|,x||,||","W||L,|W|D,D|L|D"],["|o|,|x|,||","D||D,D||D,D|L|D"],["|o|,||,x||","W||L,L|D|L,|L|D"],["|x|,|o|,||","W||W,W||W,W|D|W"], _
["x|o|x,||,||","||,L|D|L,L|L|L"],["x|o|,||x,||","||L,L|D|,L|L|L"],["x|o|,||,|x|","||L,L|L|L,D||D"],["x|x|o,||,||","||,L|D|W,L|D|W"], _
["x||o,||x,||","|L|,D|D|,L|L|L"],["x||o,||,|x|","|L|,L|L|L,L||D"],["x||,|o|x,||","|D|D,L||,L|D|D"],["x||,|o|,||x","|D|L,D||D,L|D|"], _
["x||,||o,|x|","|L|L,L|D|,L||L"],["x||,|x|,||o","|L|D,L||L,D|L|"],["x||,||x,||o","|L|L,D|D|,D|L|"],["o|x|,x||,||","||L,|D|D,L|D|L"], _
["o|x|,||x,||","||L,L|D|,W|D|L"],["|x|,o||x,||","L||D,|L|,L|L|D"],["|x|,x|o|,||","D||D,||L,D|L|L"],["|x|,|o|,|x|","W||W,W||W,W||W"], _
["|x|,||x,o||","W||L,L|L|,|L|W"],["|x|,|x|,|o|","D||D,L||L,D||D"],["o|x|o,x||,||","||,|W|D,L|D|W"],["o|x|o,||,x||","||,L|D|D,|D|W"], _
["o|x|,o||,x||","||L,|W|L,|D|L"],["o|x|,|o|,||x","||D,W||D,W|D|"],["o|x|x,||o,||","||,W|W|,W|W|L"],["o|x|,x||o,||","||D,|D|,D|D|W"], _
["o|x|,||o,x||","||D,L|W|,|D|W"],["o|x|,||o,||x","||L,W|D|,D|D|"],["o|x|x,||,|o|","||,W|D|W,W||W"],["o|x|,|x|,|o|","||D,D||D,W||D"], _
["o|x|,||x,|o|","||D,D|D|,W||W"],["o|o|x,||,|x|","||,L|L|L,D||D"],["o||x,||o,|x|","|L|,W|W|,D||L"],["o||x,||o,||x","|L|,W|D|,D|D|"], _
["o||,|x|o,||x","|D|D,L||,D|D|"],["x|o|x,o||,||","||,|W|L,L|L|D"],["x|o|,o||x,||","||D,|D|,L|D|D"],["x|o|,|o|,|x|","||L,D||D,D||D"], _
["x|o|,||o,|x|","||L,D|D|,D||D"],["|o|,x|o|,|x|","W||W,||L,D||D"],["|o|,x|x|o,||","D||W,||,D|L|D"],["|o|,x||o,|x|","D||W,|L|,D||D"], _
["x|o|x,o||,|x|","||,|D|L,L||D"],["x|o|x,x||,o||","||,|D|D,|W|D"],["x|o|x,||,o|x|","||,L|D|D,||D"],["x|o|,x||,o|x|","||L,|D|D,||D"], _
["x|o|o,||x,|x|","||,L|L|,L||L"],["x|o|,o||x,|x|","||L,|L|,L||D"],["x|o|,|o|x,|x|","||L,L||,D||D"],["x|o|,||x,o|x|","||L,L|D|,||D"], _
["x|o|,||x,|x|o","||L,D|D|,D||"],["x|x|o,||x,|o|","||,D|D|,W||D"],["x|x|o,||x,||o","||,D|D|,W|D|"],["x||o,||x,|x|o","|L|,D|D|,L||"], _
["|x|,o|x|x,|o|","D||D,||,W||D"],["|x|,o|o|x,|x|","W||D,||,W||D"],["o|x|o,x||,x|o|","||,|D|D,||W"],["o|x|x,x||o,|o|","||,|D|,D||W"], _
["o|x|x,||o,|o|x","||,W|D|,D||"],["o|x|,x|x|o,|o|","||D,||,D||W"]]


Local $s_StringNotation, $as_Grid[3][3], $as_GeometricVariants[8], $av_Book[560][2], $iCount = 0, $i_Count = 0

For $i = 0 To 69
    $s_StringNotation = $av_BookLines[$i][0]
    _GridTransformation($as_GeometricVariants, $s_StringNotation)
    For $j = 0 To UBound($as_GeometricVariants) -1
        $av_Book[$i_Count][0] = $as_GeometricVariants[$j]
        $i_Count += 1
    Next
    $s_StringNotation = $av_BookLines[$i][1]
    _GridTransformation($as_GeometricVariants, $s_StringNotation)
    For $j = 0 To UBound($as_GeometricVariants) -1
        $av_Book[$iCount][1] = $as_GeometricVariants[$j]
        $iCount += 1
    Next
Next

For $i = 559 To 1 Step - 1
    For $j = $i - 1 To 0 Step -1
        If $av_Book[$i][0] = $av_Book[$j][0] And $av_Book[$i][1] = $av_Book[$j][1] Then
            _ArrayDelete($av_Book, $j)
            $i -= 1
        EndIf
    Next
Next
;_ArrayDisplay($av_Book)

ConsoleWrite(@CRLF & "Tic-tac-toe Analysis Results - 477 continuations with 'o' to play next:" & @CRLF & @CRLF)
Local $as_TTTGrid[3][3], $as_TTTResults[3][3], $GrdRow, $RsltRow
For $i = 0 To 476
    $s_StringNotation = $av_Book[$i][0]
    _StringNotationToArray($as_TTTGrid, $s_StringNotation)
    $s_StringNotation = $av_Book[$i][1]
    _StringNotationToArray($as_TTTResults, $s_StringNotation)
    ConsoleWrite(" Variant: " & $i + 1 & @CRLF & @CRLF)
    For $a = 0 To 2
        $GrdRow = ""
        $RsltRow = ""
        For $b = 0 To 2
            If $as_TTTGrid[$a][$b] = "" Then $as_TTTGrid[$a][$b] = " "
            If $as_TTTResults[$a][$b] = "" Then $as_TTTResults[$a][$b] = " "
            $GrdRow &= $as_TTTGrid[$a][$b] & "|"
            $RsltRow &= $as_TTTResults[$a][$b] & "|"
        Next
        ConsoleWrite(" " & StringLeft($GrdRow, 5) & @TAB & StringLeft($RsltRow, 5) & @CRLF)
    Next
    ConsoleWrite(@CRLF)
Next
ConsoleWrite("The following variants have been excluded from the results:"& @CRLF)
ConsoleWrite("=> Immediate wins"& @CRLF)
ConsoleWrite("=> Forced Blocks"& @CRLF)
ConsoleWrite("=> Variants where there are no forced wins or losing continuations."& @CRLF)

Func _GridTransformation(ByRef $as_GeometricVariants, $s_StringNotation)
    $as_GeometricVariants[0] = $s_StringNotation
    $as_GeometricVariants[1] = _StringReverse($s_StringNotation) ; Grid fields should only contain one character, or reversing will effect the grid's contents.
    _InvertGrid($s_StringNotation)
    $as_GeometricVariants[2] = $s_StringNotation
    $as_GeometricVariants[3] = _StringReverse($s_StringNotation)
    _StringNotationToArray($as_Grid, $s_StringNotation)
    _TransformGeometry($as_Grid)
    _ArrayToStringNotation($as_Grid, $s_StringNotation)
    $as_GeometricVariants[4] = $s_StringNotation
    $as_GeometricVariants[5] = _StringReverse($s_StringNotation)
    _InvertGrid($s_StringNotation)
    $as_GeometricVariants[6] = $s_StringNotation
    $as_GeometricVariants[7] = _StringReverse($s_StringNotation)
EndFunc


Func _InvertGrid(ByRef $s_Notation)
    Local $as_Rows = StringSplit($s_Notation, ",", 2)
    _ArrayReverse($as_Rows)
    $s_Notation = _ArrayToString($as_Rows,",")
EndFunc

Func _StringNotationToArray(ByRef $as_Grd, $s_Notation)
    Local  $as_Elements, $as_Rows = StringSplit($s_Notation, ",", 2)
    For $i = 0 To 2
        $as_Elements = StringSplit($as_Rows[$i],"|",2)
        For $j = 0 To 2
            $as_Grd[$i][$j] = $as_Elements[$j]
        Next
    Next
EndFunc

Func _TransformGeometry(ByRef $as_Grd)
    Local $as_Tmp = $as_Grd
    For $i = 0 To 2
        For $j = 0 To 2
            $as_Grd[$i][$j] = $as_Tmp[$j][$i]
        Next
    Next
EndFunc

Func _ArrayToStringNotation(ByRef $as_Grd, ByRef $s_Notation)
    Local $as_Tmp[3]
    For $i = 0 To 2
        For $j = 0 To 1
            $as_Tmp[$i] &= $as_Grd[$i][$j] & "|"
        Next
        $as_Tmp[$i] &= $as_Grd[$i][$j]
    Next
    $s_Notation = _ArrayToString($as_Tmp,",")
EndFunc

Using such a map is a perhaps useful if you want to vary the play of an engine. If you just want the computer to win again and again with the same order of moves: then simply go for the first win you find. Though that's really pretty dull. There are ways to spice it up slightly.

I checked the analysis once and there were a few errors. Hopefully there are no more errors left.

Edit

Updated results. I only included results starting after two moves DOH! They were separated when I ran the engine against itself to check the variations. I have now included the first move.

Edited September 16, 2010 by czardas

[CodyBarrett]

Wow. o.o

[czardas]

I know some of the stuff I have posted can be improved. Doing this has been a good learning experience for me and I hope it gives you some ideas. There are probably plenty of other ways to do this too.

[CodyBarrett]

NEW VERSION!

i hope its better than my previous ones, i haven't found a bug yet. what do you guys think?