如何递归地展开游戏树

huangapple 未分类评论44阅读模式
英文:

How to expand recursively a game tree

问题

public void BuildTree(Stato State, int depth) { 
   if (depth < 0) {
       throw new IllegalArgumentException();
   }
   
   if (depth == 0) {
       State.Results = null;
   }
   
   if (depth > 0) {
       for (int i = 0; i < depth; i++) {
           State.GeneraSuccessore();
           
           System.out.println("SIZE: " + SizeOfTree(State));
           
           for (Stato S : State.Results) {
               S.GeneraSuccessore();
           }
       }
   }
   
   DecisionTree = State;
       
   PrintAlbero();
}
public class Stato {
    KnowledgeBase Actual;
    
    ArrayList<Carta> Table;
    ArrayList<Carta> Hand;
    
    ArrayList<Carta> Opponent;
    
    Gioco Game;
    
    Punteggio Score;
    
    boolean IsMax;
    
    String Label;
    
    double Gain;
    
    Stato Parent;
    
    ArrayList<Stato> Results;
    
    public Stato(String L, ArrayList<Carta> T, ArrayList<Carta> H, KnowledgeBase K, Punteggio S, boolean Q) {
        // Constructor content...
    }
    
    public void GeneraSuccessore() {
        // Method content...
    }
    
    public ArrayList<Carta> FT(ArrayList<Carta> T, Carta C, int Scelta) {
        // Method content...
    }
    
    public ArrayList<Carta> FH(ArrayList<Carta> H, Carta C) {
        // Method content...
    }
    
    public KnowledgeBase FKB(KnowledgeBase K, Carta C) {
        // Method content...
    }
    
    public Punteggio FS(Punteggio S, Carta C) {
        // Method content...
    }
    
    public void SetKB(KnowledgeBase KB) {
        // Method content...
    }
    
    public void SetTable(ArrayList<Carta> Tv) {
        // Method content...
    }
    
    public void SetHand(ArrayList<Carta> KnownHand) {
        // Method content...
    }
    
    public ArrayList<Stato> GetResults() {
        // Method content...
    }
    
    protected void SetParent(Stato Previous) {
        // Method content...
    }
    
    public Stato GetParent() {
        // Method content...
    }
    
    // Other methods...
}

The problem occurs when calling the BuildTree method, which seems to be too time and resource-consuming.

英文:

I'm implementing a card game in java, however i cannot expand efficiently the game tree in order for computer to execute MiniMax algorithm on it, here is the code:


public void BuildTree(Stato State,int depth)
    { 
       if(depth &lt; 0)
       {
           throw new IllegalArgumentException();
       }
       
       if(depth == 0)
       {
           State.Results = null;
       }
       
       if(depth &gt; 0)
       {
           for(int i=0; i&lt;depth; i++)
           {
               State.GeneraSuccessore();
               
               System.out.println(&quot;SIZE: &quot;+SizeOfTree(State));
               
               for(Stato S : State.Results)
               {
                   S.GeneraSuccessore();
               }
           }
       }
       
       DecisionTree = State;
           
       PrintAlbero();
    }

This is the structure of a State (Stato.java). Each State contains:

  • Cards in the hand of the CPU
  • Cards on the table
  • Current CPU score
  • A label
  • A KnowledgeBase in order to know stats about cards such as probability and gain for each move
  • A boolean indicating if its the turn of Computer (player MAX) or Player (player MIN)
public class Stato 
{   
    /*----CONFIGURAZIONE RELATIVA AD UNO STATO----*/
    KnowledgeBase Actual;
    
    ArrayList&lt;Carta&gt; Table;
    ArrayList&lt;Carta&gt; Hand;
    
    ArrayList&lt;Carta&gt; Opponent;
    
    Gioco Game;
    
    Punteggio Score;
    
    boolean IsMax;
    
    String Label;
    
    double Gain;
    
    /*----FINE CONFIGURAZIONE RELATIVA AD UNO STATO----*/
    
    /*----IMPLEMENTAZIONE DEI NODI PER L&#39;USO DELLA RICORSIONE----*/
    Stato Parent;
    
    ArrayList&lt;Stato&gt; Results;
    /*----FINE IMPLEMENTAZIONE DEI NODI PER L&#39;USO DELLA RICORSIONE----*/
    
    public Stato(String L,ArrayList&lt;Carta&gt; T,ArrayList&lt;Carta&gt; H,KnowledgeBase K,Punteggio S,boolean Q)
    {
        Actual = K;
        
        Table = T;
        
        Hand = H;
        
        Label = L;

        Score = S;
        
        IsMax = Q;
        
        Parent = null;
        
        Gain = 0;
        
        Results = new ArrayList();
    }  
    
    public void GeneraSuccessore()
    {
        boolean turn = !IsMax;

        if(!turn)//CASO MAX (TURNO CPU)
        {
            for(Carta C : Hand)
            {
                if(C.IsMarked() &amp;&amp; !Table.isEmpty())
                {                
                    for(int Sc = 1; Sc &lt;=C.Potenziale.size(); Sc++)
                    {
                       if(C.HasPotential(Sc))
                       {
                            Stato S1;
                            S1 = new Stato(Label+&quot;-&gt; &quot;+C.nome+&quot;/&quot;+Sc,FT(Table,C,Sc),FH(Hand,C),FKB(Actual,C),FS(Score,C),turn);
                            S1.Gain = C.ValoriPotenziale.get(Sc);
                            
                            Results.add(S1);
                       }
                    }
                }
                else
                {
                    Stato S1;
                    S1 = new Stato(Label+&quot;-&gt; &quot;+C.nome+&quot;/&quot;+0,FT(Table,C,1),FH(Hand,C),FKB(Actual,C),FS(Score,C),turn); 
                    S1.Gain = 0.0;
                    
                    
                    Results.add(S1);
                }
            }
        }
        else//CASO MIN (TURNO GIOCATORE)
        {
            GetOpponent();
            for(Carta C : Opponent)
            {
                if(C.IsMarked() &amp;&amp; !Table.isEmpty())
                {                
                    for(int Sc = 1; Sc &lt;=C.Potenziale.size(); Sc++)
                    {
                       if(C.HasPotential(Sc))
                       {
                           Stato S1;
                            S1 = new Stato(Label+&quot;-&gt; &quot;+C.nome+&quot;/&quot;+Sc,FT(Table,C,Sc),FH(Opponent,C),FKB(Actual,C),FS(Score,C),turn);
                            S1.Gain = C.ValoriPotenziale.get(Sc);
                            
                            Results.add(S1);

                       }

                    }
                }
                else
                {
                    Stato S1;
                    
                    S1 = new Stato(Label+&quot;-&gt; &quot;+C.nome+&quot;/&quot;+0,FT(Table,C,1),FH(Opponent,C),FKB(Actual,C),FS(Score,C),turn); 
                    S1.Gain = 0.0;
                    
                    Results.add(S1);
                }
            }
        }

    }
       
    public ArrayList&lt;Carta&gt; FT(ArrayList&lt;Carta&gt; T,Carta C,int Scelta)
    {
        if(C.HasPotential(Scelta))
        {
            ArrayList&lt;Carta&gt; TB = new ArrayList();
        
            TB.addAll(T);
        
            for(Carta C1 : C.Potenziale.get(Scelta))
            {
                TB.remove(C1);
            }
            
            return TB;
        }
        else
        {
            ArrayList&lt;Carta&gt; TB = new ArrayList();
            
            TB.addAll(T);
            TB.add(C);
            
            return TB;
        }
    }
        
    public ArrayList&lt;Carta&gt; FH(ArrayList&lt;Carta&gt; H,Carta C)
    {
        ArrayList&lt;Carta&gt; HND = new ArrayList();
        
        HND.addAll(H);
        
        HND.remove(C);

        return HND;
    }
    
    public KnowledgeBase FKB(KnowledgeBase K,Carta C)
    {
        KnowledgeBase KB1 = K;
        
        KB1.RimuoviCarta(C);
        
        return KB1;
    }
    
    public Punteggio FS(Punteggio S,Carta C)
    {
        Punteggio SCR = S;
        
        S.AddCard(C);
        
        return SCR;
    }
    

    public void SetKB(KnowledgeBase KB)
    {
        Actual = KB;
    }
    
    public void SetTable(ArrayList&lt;Carta&gt; Tv)
    {
        Table = Tv;
    }
    
    public void SetHand(ArrayList&lt;Carta&gt; KnownHand)
    {
        Hand = KnownHand;
    }
    
    public KnowledgeBase GetKB()
    {
        return Actual;
    }
    
    public ArrayList&lt;Carta&gt; GetTable()
    {
        return Table;
    }
    
    public ArrayList&lt;Carta&gt; GetHand()
    {
        return Hand;
    }
    
    public ArrayList&lt;Carta&gt; GetOpponent()
    {
        Opponent = Actual.GetMostValuableCards(Table,Score);
        return Opponent;
    }
    
    public Stato AddResult(Stato Res) 
    {
        Res.SetParent(this);
        this.Results.add(Res);
        return Res;
    }
 
    public void AddResultsList(ArrayList&lt;Stato&gt; ListOfStates) 
    {
        for(Stato Res : ListOfStates)
        {
            Res.SetParent(this);
        }
            
        Results.addAll(ListOfStates);
    }

    public ArrayList&lt;Stato&gt; GetResults()
    {
        return Results;
    }
 
    protected void SetParent(Stato Previous) 
    {
        this.Parent = Previous;
    }
 
    public Stato GetParent() 
    {
        return Parent;
    }
    
    public void SetLabel(String L)
    {
        Label = L;
    }
    
    public String GetLabel()
    {
        return Label;
    }
    
    public void SetPunteggio(Punteggio S)
    {
        Score = S;
    }
    
    public Punteggio GetPunteggio()
    {
        return Score;
    }
    
    public void ResetGain()
    {
        Gain = 0.0;
    }
    
    public void SetGain(Double D)
    {
        Gain = D;
    }
    
    public double GeiGain()
    {
        return Gain;
    }
    
    public void UpdateState(KnowledgeBase KB, ArrayList&lt;Carta&gt; Tb,ArrayList&lt;Carta&gt; Hnd)
    {
        Actual = KB;
        Table = Tb;
        Hand = Hnd;
    }
}

The problem is that when i call the BuildTree method, JVM stops working, i think its because this way of building a game tree is quite too time and resource-consuming.

How would you solve this?

huangapple
  • 本文由 发表于 2020年7月26日 01:06:36
  • 转载请务必保留本文链接:https://java.coder-hub.com/63091130.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定