Using a tree data structure in VBA

Question

I am getting more familiar with VBA and I am attempting to do a machine learning program for Tic Tac Toe. I don't want to just hard code the possibilities to win.

The best I have come up with for a machine learning program is to have a tree structure with all the possible moves that can be made, and then have the computer cut branches of the tree whenever it loses with that branch.

For example with the following way to denote where people have played, and the order the letters are written as the order the game has progressed

a|b|c
-----
d|e|f
-----
g|h|i

abdgfce - means the computer wins, a was played first, b second, d third....

I would like to have a data tree that looks like:

Level 0: a (Computer always starts with a)

Level 1: All the letters except a, as it has already been played

Level 2: For each letter in Level 0, all the letters except for the one right before it and a

And so on for all the levels of the tree until their are no more possible moves.

I tried looking for ways to implement this structure in VBA but the Microsoft website was of no help and the forums only speak of binary or sorting trees. Would somebody point me in the right direction or give me some pointers as to what I should try? What is a better way to solve this problem if this solution is not feasible?

Thank you,

Karim

Answer 1

There are "only" 362,880 way to fill the nine places in a tic-tac-toe table. The complete set can be generated in column A by placing:

ABCDEFGHI

in cell B1 and running GetString():

Dim ll As Long
Dim CurrentRow As Long

Sub GetString()
    Dim InString As String
    InString = Sheets("Sheet1").Range("B1")
    ActiveSheet.Columns(1).Clear
    CurrentRow = 1
    Application.ScreenUpdating = False
        Call GetPermutation("", InString)
    Application.ScreenUpdating = True
End Sub

Sub GetPermutation(x As String, y As String)
    '   The source of this algorithm is unknown
    Dim i As Long, j As Long
    j = Len(y)
    If j < 2 Then
        Cells(CurrentRow, 1) = x & y
        CurrentRow = CurrentRow + 1
    Else
        For i = 1 To j
            Call GetPermutation(x + Mid(y, i, 1), _
            Left(y, i - 1) + Right(y, j - i))
        Next
    End If
End Sub

Of course, the majority of games will end before all nine places are filled. If the computer loses, that item is removed, etc.

EDIT#1:

Wayne G. Dunn suggested that the number of variations may be reduced. The Computer (player#1) has nine possible places it place its X. Player#2 then has eight possible places to place her O. etc.

This yields 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 or 9 factorial.

However, the game can end before all nine places are filled. Thus many of the 362880 variation can be discarded............I just don't know how many.