Utilisation d'une structure de données d'arbres dans VBA

Question

Je suis plus familier avec VBA et je tente de faire un programme d'apprentissage de la machine pour TIC TAC Toe. Je ne veux pas juste que le code dure les possibilités de gagner.

Le meilleur que je suis arrivé pour un programme d'apprentissage de la machine est d'avoir une structure d'arborescence avec tous les mouvements possibles pouvant être réalisés, puis des branches coupées de l'ordinateur de l'arbre chaque fois que cela perd avec cette branche.

Par exemple, avec la manière suivante pour indiquer où les gens ont joué et la commande Les lettres sont écrites comme commande que le jeu a progressé

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

abdgfce - signifie que l'ordinateur gagne, A a été joué en premier, B de second, D troisième ....

Je voudrais avoir un arborescence de données qui ressemble à:

niveau 0: A (ordinateur commence toujours par a)

niveau 1: toutes les lettres sauf A, comme il a déjà été joué

NIVEAU 2: Pour chaque lettre du niveau 0, toutes les lettres sauf pour la seule avant de cela et d'un

et ainsi de suite pour tous les niveaux de l'arbre jusqu'à ce que leur ne soit plus de mouvements possibles.

J'ai essayé de chercher des moyens de mettre en œuvre cette structure dans VBA, mais le site Web de Microsoft n'était pas d'aide et les forums ne parlent que d'arbres binaires ou triateurs. Est-ce que quelqu'un me dirait dans la bonne direction ou donnez-moi des indications sur ce que je devrais essayer? Quel est un meilleur moyen de résoudre ce problème si cette solution n'est pas réalisable?

Merci,

karim

Answer 1

Il n'y a "seulement" 362 880 moyens de remplir les neuf endroits d'une table Tic-Tac-toe.L'ensemble complet peut être généré dans la colonne A en plaçant:

abcdefghi

dans la cellule b1 et exécuter 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

Bien sûr, la majorité des jeux se termineront avant que les neuf places soient remplies.Si l'ordinateur perd, cet élément est supprimé, etc.

edit # 1:

Wayne G. Dunn a suggéré que le nombre de variations puisse être réduit.L'ordinateur (joueur n ° 1) a neuf endroits possibles, il placent son x. joueur n ° 2 a ensuite huit endroits possibles pour la placer o. etc.

Ce rendement 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 ou 9 facteurs factoriels.

Cependant, le jeu peut se terminer avant que les neuf places soient remplies.Ainsi, beaucoup de variations 362880 peuvent être jetées ............ Je ne sais tout simplement pas combien.