Usando uma árvore de estrutura de dados em VBA

Question

Eu estou ficando mais familiarizado com o VBA e eu estou tentando fazer um programa de aprendizagem de máquina para Tic Tac Dedo do pé.Eu não quero só rígido código de possibilidades de ganhar.

O melhor que eu vim com uma máquina de aprendizagem do programa é ter uma estrutura de árvore com todos os movimentos possíveis que podem ser feitas e, em seguida, envie o computador para cortar galhos da árvore sempre que perde com esse ramo.

Por exemplo, com a seguinte forma para indicar onde as pessoas jogaram, e a ordem em que as letras são escritas como a ordem que o jogo tem progredido

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

abdgfce - significa que o computador vitórias, uma foi tocada primeiro, b, d terceiro....

Eu gostaria de ter uma árvore de dados que se parece com:

Nível 0:um (Computador sempre começa com uma)

Nível 1:Todas as letras, exceto um, como já foi jogado

Nível 2:Para cada letra no Nível 0, todas as letras, exceto a direita antes e um

E assim por diante para todos os níveis da árvore até que os seus não são mais movimentos possíveis.

Eu tentei olhar para formas para implementar esta estrutura em VBA, mas o site da Microsoft foi de nenhuma ajuda e fóruns apenas falar de binário ou de classificação de árvores.Será que alguém me aponte na direção certa ou me dar algumas dicas do que eu deveria tentar?O que é uma forma melhor de resolver esse problema se essa solução não é viável?

Obrigado,

Karim

Answer 1

Há "apenas" 362,880 caminho para o preenchimento de nove lugares em um tic-tac-toe tabela.O conjunto completo pode ser gerado na coluna Um colocando:

ABCDEFGHI

na célula B1 e execução 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

Claro, a maioria dos jogos vai acabar antes de todos os nove lugares são preenchidos.Se o computador perder, o item é removido, etc.

EDIÇÃO#1:

Wayne G.Dunn sugeriu que o número de variações pode ser reduzida.O Computador (o jogador#1) tem nove lugares possíveis é o seu lugar X. O jogador#2, em seguida, tem oito lugares possíveis para colocá-la O. etc.

Isso produz 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 ou 9 fatorial.

No entanto, pode terminar o jogo antes de todos os nove lugares são preenchidos.Assim, muitos dos 362880 variação pode ser descartado............Eu só não sei quantos.