Usando una estructura de datos de árbol en VBA

Question

Me estoy familiarizando con VBA y estoy intentando hacer un programa de aprendizaje automático para TIC TAC TOE. No quiero simplemente un código duro las posibilidades de ganar.

Lo mejor que he creado para un programa de aprendizaje de máquinas es tener una estructura de árbol con todos los movimientos posibles que se pueden hacer, y luego hacer que la computadora corte las ramas del árbol siempre que pierda con esa sucursal.

Por ejemplo, con la siguiente manera de denotar donde las personas han jugado, y la orden las letras se escriben como el orden que el juego ha progresado

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

abdgfce - significa que la computadora gana, se jugó primero, b segundo, d tercer ...

Me gustaría tener un árbol de datos que se vea:

Nivel 0: A (la computadora siempre comienza con A)

Nivel 1: Todas las letras excepto A, como ya se ha jugado

Nivel 2: Para cada letra en el nivel 0, todas las letras, excepto el derecho antes de él y un

y así sucesivamente para todos los niveles del árbol hasta que no sean más movimientos posibles.

Intenté buscar formas de implementar esta estructura en VBA, pero el sitio web de Microsoft no tenía ayuda y los foros solo hablan de árboles binarios o de clasificación. ¿Alguien me apuntará en la dirección correcta o me daría algunos punteros sobre qué debería intentarlo? ¿Cuál es una mejor manera de resolver este problema si esta solución no es factible?

Gracias,

karim

Answer 1

Hay "solo" 362,880 manera de llenar los nueve lugares en una mesa Tic-Tac-Toe.El conjunto completo se puede generar en la columna a colocando:

abcdefghi

en la celda B1 y corriendo 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

Por supuesto, la mayoría de los juegos terminarán antes de que se llenen los nueve lugares.Si la computadora pierde, ese artículo se elimina, etc.

Editar # 1:

Wayne G. Dunn sugirió que se puede reducir el número de variaciones.La computadora (Jugador # 1) tiene nueve lugares posibles, colocan su x. el jugador # 2 luego tiene ocho lugares posibles para colocarla o. etc.

Esto produce 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 o 9 factorial.

Sin embargo, el juego puede terminar antes de que se llenen los nueve lugares.Por lo tanto, muchas de las 362880 variaciones se pueden descartar ............ Simplemente no sé cuántos.