Passende Listenstruktur gesucht

[Tabriel]

Abend oder besser Morgen!
Bin auf der Suche nach einer passenden Listenstruktur. Und zwar soll die erste Ebene(=Tiefe 0) aus 6 Elementen bestehen, welche jeweils einen Zahlenwert annehmen. Jedes von diesen Elementen soll wiederum auf 0-6 weitere Elemente zeigen(variabel, je nachdem wieviele Züge möglich sind) usw.
Jedes Element soll einen möglichen Spielzug darstellen, möchte damit den Minimax-Algorithmus für ein Spiel implementieren.
Kann mir wer helfen?

Danke schonma,

Grüße

 

[Herr K.]

Hallo,

was Du benötigst ist ein Baum. Da gibt es verschiedene Varianten, wie man die aufbauen kann. Hast Du eine bekannte, maximale Breite pro Knoten (in Deinem Fall 6), kannst Du z.B. eine Liste nehmen, die für jede Hierarchieebene einfach erweitert wird. Ein Baum der Tiefe 1 wird von einer Liste der Größe 6 repräsentiert, die Tiefe zwei wäre eine Liste mit 6 + 36 Elementen. Hier hättest Du den Vorteil eines Wahlfreien Zugriffs, dem ersten Knoten (Index == 0) sind die Elemente mit den Indizes 6 bis 11 untergeordnet, dem zweiten Knoten die mit den Indizes 12 bis 17 usw.
Die Berechnung sollte entsprechend einfach ausfallen und Du kannst auf jeden Knoten sehr effizient zugreifen. Nachteilig ist, dass Du eben den vollständigen Baum reservierst, auch wenn der entartet (einer oder wenige Äste werden sehr tief, die anderen bleiben flach).

Hier bietet es sich eher an den Baum über Verknüpfungen aufzubauen. Dazu definierst Du Dir einfach eine Klasse:

public class TreeNode {

  private final List<TreeNode> childNodes;
  private final TreeNode parent;
  private final int value;

  public TreeNode(int value) {
     this.parent = null;
     this.childNodes = new ArrayList<TreeNode>(6);
     this.value = value;
  }

  protected TreeNode(int value, TreeNode parent) {
     this.parent = parent;
     this.childNodes = new ArrayList<TreeNode>(6);
     this.value = value;
  }

  public TreeNode addNewChild(int value) {
    final TreeNode result = new TreeNode(value, this);
    this.childNodes.add(result);
    return result;
  }

  public TreeNode getChildByValue(int value) {
    for (final TreeNode child: this.childNodes) {
      if (child.getValue() == value) {
        return child;
      }
    }

    return null;
  }

  public int getValue() {
    return this.value;
  }
}

Mal ganz grob. Du könntest hier auch noch einen Getter für alle Kindknoten und zu jedem Kindknoten auch noch den Getter des Elternknoten vorsehen, auch sind hier im Moment beliebig viele Kindknoten möglich, die einfach hintereinander abgelegt werden.

Dein Baum ist einfach ein Wurzelknoten (der hat keinen Elternknoten), an den hängst Du dann jeweils Teilbäume an. So kannst Du dann auch den Baum traversieren, Du nimmst einfach den Wurzelknoten und greifst auf einen der Kindknoten zurück. Die Kindknoten repräsentieren dann wiederum einen Teilbaum, den Du analog traversieren kannst.

 

[Tabriel]

Super, ich danke dir für die schnelle Hilfe!

Grüße

 

[Tabriel]

Tag,
habe jetzt ein weiteres Problem. In der Methode play wird das Spiel simuliert bis zu einer bestimmten Tiefe,indem jede TreeNode einen Spielstand abspeichert, und ein veränderter Spielstand mit der simulate-Methode erzeugt wird, welcher dann an das Kind weitergereicht wird, und für dieses Kind auch wieder die play-Methode aufgerufen wird, sodass für dieses weitere 6 Kinder erzeugt werden etc.Dann wird der Zahlenwert bestimmt, welcher in der Methode auswerten ,je nachdem ob Minimierer/Maximierer dran ist,"hochgereicht" wird.
Hier einfach mal die beiden Methoden:

    public void play(TreeNode tr, int laufVar)
    {
        if(!(laufVar > difficulty))//Erstellen des Baumes + Simulieren bis in bestimmte Ebene
        {
            System.out.println("Play bei laufVar:" +laufVar);
            int turn;
            if(laufVar%2 != 0) //Bei ungerade sind es Züge von KI = Spieler2, von 0 zu 1, von 2 zu 3 etc.
                turn = 2;
            else
                turn = 1;
            for(int i = 0;i<6;i++)
            {
                System.out.println("Status an Stelle:" + i + " = " + hollows[i+7]);
                int[] tmp = simulate(i,tr.getStatus(),turn);
                if(tmp == null)
                    System.out.println("Füge kein Kind hinzu");
                if(tmp!= null)
                {
                    System.out.println("Füge Kind hinzu");
                    TreeNode child = tr.addNewChild(tmp,i);
                    play(child,(laufVar+1));
                }
            }
        }
        else//Weiterreichen der Werte nach oben
        {
            int[] status = tr.getStatus();
            int value = (status[13] - hollows[13]) - (status[6] - hollows[6]); //Kommen in die KI-Mulde(=Player 2) Steine hinzu bzw. verliert die SpielerKI welche wirkt sich das positiv aus und umgekehrt
            tr.setValue(value);//Abhandlung der untersten Ebene
            System.out.println("Beginne jetzt mit Auswertung");
            auswerten(tr.getParent(),(laufVar-1));
        }
        
    }
public void auswerten(TreeNode tr,int laufVar)//Kriegt immer parent übergeben
    {
        if(laufVar != 0)//Kinder suchen, vergleichen, und je nach Ebene(Spieler A/Spieler B) den kleinsten/größten Wert annehmen und eine Ebene raufgehen(durch tr.getParent())
        {
            System.out.println("Auswerten bei laufVar: "+laufVar);
            int max = -255;
            int min = 255;
            ArrayList<TreeNode> childNodes = tr.getChildNodes();
            for(int i = 0;i<6;i++)
            {
                TreeNode tmp = childNodes.get(i);
                if(tmp != null)//Der Zweig wurde nicht weitergegangen, da Zug nicht möglich
                {
                    if(laufVar%2 != 0)//Ebene vom Gegner da ungerade
                    {
                        if(tmp.getValue() < min)
                            tr.setValue(tmp.getValue());
                    }
                    else
                    {
                        if(tmp.getValue()>max)
                            tr.setValue(tmp.getValue());
                    }
                }
            }
            auswerten(tr.getParent(),--laufVar);
        }
        else//Ganz oben angekommen, ein letztes vergleichen und play-Methode vom Controller aufrufen
        {
            int max = -255;
            int index = 0;//Für Weitergabe des gewählten Zuges an Controller
            ArrayList<TreeNode> childNodes = tr.getChildNodes();
            for(int i = 0;i<6;i++)
            {
                TreeNode tmp = childNodes.get(i);
                if(tmp != null)
                {
                    if(tmp.getValue() > max)
                    {
                        tr.setValue(tmp.getValue());
                        index = i;
                    }
                }
            }
            ctrl.KIplay(index);
        }
    }

Problem ist, dass er eine IndexOutOfBound-Exception auswirft für die erstellte ArrayList childNodes. Scheinbar wird in der for-Schleife der play-Methode auf die Abarbeitung der weiteren play-Methode gewartet, zumindestens wird nur 1x der Satz "Füge Kind hinzu" ausgegeben pro Variablenwert, und nicht wie zu erwartet 6^Laufvariablen mal.
Kann ich das irgendwie umgehen, dass auf die Abarbeitung der play-Methode gewartet wird?

Grüße

 

[Tabriel]

Oh Entschuldigung, ich habe vergessen das Java-Tag zu schließen, hier der Code:

    public void play(TreeNode tr, int laufVar)
    {
        if(!(laufVar > difficulty))//Erstellen des Baumes + Simulieren bis in bestimmte Ebene
        {
            System.out.println("Play bei laufVar:" +laufVar);
            int turn;
            if(laufVar%2 != 0) //Bei ungerade sind es Züge von KI = Spieler2, von 0 zu 1, von 2 zu 3 etc.
                turn = 2;
            else
                turn = 1;
            for(int i = 0;i<6;i++)
            {
                System.out.println("Status an Stelle:" + i + " = " + hollows[i+7]);
                int[] tmp = simulate(i,tr.getStatus(),turn);
                if(tmp == null)
                    System.out.println("Füge kein Kind hinzu");
                if(tmp!= null)
                {
                    System.out.println("Füge Kind hinzu");
                    TreeNode child = tr.addNewChild(tmp,i);
                    play(child,(laufVar+1));
                }
            }
        }
        else//Weiterreichen der Werte nach oben
        {
            int[] status = tr.getStatus();
            int value = (status[13] - hollows[13]) - (status[6] - hollows[6]); //Kommen in die KI-Mulde(=Player 2) Steine hinzu bzw. verliert die SpielerKI welche wirkt sich das positiv aus und umgekehrt
            tr.setValue(value);//Abhandlung der untersten Ebene
            System.out.println("Beginne jetzt mit Auswertung");
            auswerten(tr.getParent(),(laufVar-1));
        }
        
    }
public void auswerten(TreeNode tr,int laufVar)//Kriegt immer parent übergeben
    {
        if(laufVar != 0)//Kinder suchen, vergleichen, und je nach Ebene(Spieler A/Spieler B) den kleinsten/größten Wert annehmen und eine Ebene raufgehen(durch tr.getParent())
        {
            System.out.println("Auswerten bei laufVar: "+laufVar);
            int max = -255;
            int min = 255;
            ArrayList<TreeNode> childNodes = tr.getChildNodes();
            for(int i = 0;i<6;i++)
            {
                TreeNode tmp = childNodes.get(i);
                if(tmp != null)//Der Zweig wurde nicht weitergegangen, da Zug nicht möglich
                {
                    if(laufVar%2 != 0)//Ebene vom Gegner da ungerade
                    {
                        if(tmp.getValue() < min)
                            tr.setValue(tmp.getValue());
                    }
                    else
                    {
                        if(tmp.getValue()>max)
                            tr.setValue(tmp.getValue());
                    }
                }
            }
            auswerten(tr.getParent(),--laufVar);
        }
        else//Ganz oben angekommen, ein letztes vergleichen und play-Methode vom Controller aufrufen
        {
            int max = -255;
            int index = 0;//Für Weitergabe des gewählten Zuges an Controller
            ArrayList<TreeNode> childNodes = tr.getChildNodes();
            for(int i = 0;i<6;i++)
            {
                TreeNode tmp = childNodes.get(i);
                if(tmp != null)
                {
                    if(tmp.getValue() > max)
                    {
                        tr.setValue(tmp.getValue());
                        index = i;
                    }
                }
            }
            ctrl.KIplay(index);
        }
    }

 

[Tabriel]

Ok,
ich habe jetz nach etwas Nachforschung probiert, den Teil in der for-Schleife in einen Thread zu packen, und die Methode auf synchronized gestellt. Kommt leider immernoch IndexOutOfBounds-Exception(Diesmal mehrere, wegen mehreren Threads). Kenne mich mit den Threads auch noch nicht so gut aus, ich habe jetz einfach synchronized vor die Methode geschrieben und die Abhandlung so verändert(der relevante Teil):

                if(tmp!= null)
                {
                    final int c = i;
                    final TreeNode g = tr;
                    final int a = laufVar;
                    new Thread(){
                        public void run()
                        {
                           System.out.println("Füge Kind hinzu");
                           TreeNode child = g.addNewChild(tmp,c);
                           play(child,(a+1)); 
                        }
                    }.start();
                    //statt:
                    //System.out.println("Füge Kind hinzu");
                    //TreeNode child = tr.addNewChild(tmp,i);
                    //play(child,(laufVar+1)); //Evt. hier nur einmal play aufrufen für eine ArrayList und diese übergeben nach der for-schleife
                }

Er gibt jetzt öfter "Füge Kind hinzu aus", aber teilweise kommt nach 3x schon der Auswerten-Teil, manchmal nach 6x, es ist alles etwas wirr durcheinander.

Grüße