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
La solution
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
abcdefghi
dans la cellule
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
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.