Jump to content

  • Log In with Google      Sign In   
  • Create Account

Need help with alpha-beta and Transposition Table (yeah..again i know)


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
No replies to this topic

#1 patishi   Members   -  Reputation: 212

Like
0Likes
Like

Posted 11 June 2013 - 05:00 PM

Hi everybody.  I am sorry if this is the 1000 time that this question is asked here.. but i am sorry, i am trying for nearly three weeks to implement my transposition table into the alpha beta function in a connect 4 application ,and no luck!      I programming in JAVA by the way 
Until i though that i finally got the whole bounds thing (lower,upper) i am realized that i didn't.    I know that becasue when testing my engine with the hashtable and without the hashtable ,the moves are slightly different.        
 

Below is my alpha beta implementation (actually i have two of them,this is the more JAVA like implementation,and the other is the one present in Wikipedia)  without thte transposition table and  with the hashtable.   please,can you tell me what's wrong with this code and correct me??  
I am really bummed by this,i want to get on with the engine dev'  but i can't until i finish with the TT. 

This is the alpha beta without the TT ,it works fine:   
 

public Best chooseMove(boolean side,int alpha,int beta,int depth){
   Best myBest = new Best();
   Best reply;
   if(Board.checkGameOver(newBoard)||depth==0){
        Best fakeBest = new Best();
        fakeBest.setScore(returnPositionScore(newBoard));
        return fakeBest;
   }
   if(side){
            myBest.setScore(alpha);
   }
    else{
          myBest.setScore(beta);
   }
 
   ArrayList<Integer>availableMoves = searchAvailableMoves(newBoard);
   for(Integer move:availableMoves){
        makeMove(move);
        reply = chooseMove(!side,alpha,beta,depth-1);
        unmakeMove(move);
     
    if(side&&reply.getScore()>myBest.getScore()){
          myBest.setMove(move);
         myBest.setScore(reply.getScore());
         alpha = reply.getScore();
    }
   
    else if(!side&&reply.getScore()<myBest.getScore()){
             myBest.setMove(move);
             myBest.setScore(reply.getScore());
             beta = reply.getScore();
    }
   
    if(alpha>=beta){
          return myBest;
   }
 }
   return myBest;
 
}
 
 
And this is how i tried to implement the TT into the function: 

public Best chooseMove(boolean side,int alpha,int beta,int depth){
          int originalAlpha = alpha;
          int originalBeta = beta;
          Best myBest = new Best();
          Best reply;
       
        TranspositionTable.Entry entry = table.find(newBoard);
         if(entry!=null&&entry.getDepth()>=depth){
              if(entry.getValueType()==Entry.ValueType.EXACT_VALUE){
                     Best fakeBest = new Best();
                    fakeBest.setScore(entry.getValue());
                    return fakeBest;
             }
             
            if(entry.getValueType()==Entry.ValueType.LOWERBOUND){
                 alpha = Math.max(alpha, entry.getValue());
            }
 
            else if(entry.getValueType()==Entry.ValueType.UPPERBOUND){
                  beta = Math.min(beta, entry.getValue());
            }
 
             if(alpha>=beta){
                 Best fakeBest = new Best();
                fakeBest.setScore(entry.getValue());
               return fakeBest;
           }
      }
 
            if(Board.checkGameOver(newBoard)||depth==0){
                 int value = returnPositionScore(newBoard);
                 if(value<=originalAlpha){
                        table.insert(newBoard, myBest.getScore(), depth, Entry.ValueType.UPPERBOUND);
 
                }
 
                else if(value>=originalBeta){
                       table.insert(newBoard, myBest.getScore(), depth, Entry.ValueType.LOWERBOUND);
 
                }
 
                else{
                       table.insert(newBoard, myBest.getScore(), depth, Entry.ValueType.EXACT_VALUE);
 
               }
                  Best fakeBest = new Best();
                  fakeBest.setScore(value);
                  return fakeBest;
         }
 
            if(side){
                     myBest.setScore(alpha);
           }
   
            else{
                 myBest.setScore(beta);
            }
             ArrayList<Integer>availableMoves = searchAvailableMoves(newBoard);
 
          for(Integer move:availableMoves){
              makeMove(move);
              reply = chooseMove(!side,alpha,beta,depth-1);
              unmakeMove(move);
 
            if(side&&reply.getScore()>myBest.getScore()){
                myBest.setMove(move);
                myBest.setScore(reply.getScore());
                alpha = reply.getScore();
           }
 
           else if(!side&&reply.getScore()<myBest.getScore()){
                    myBest.setMove(move);
                    myBest.setScore(reply.getScore());
                     beta = reply.getScore();
           }
 
           if(alpha>=beta){
                 break;
          }
}
 
        if(myBest.getScore()<=originalAlpha){
               table.insert(newBoard, myBest.getScore(), depth, Entry.ValueType.UPPERBOUND);
        } 
       
        else if(myBest.getScore()>=originalBeta){
                    table.insert(newBoard, myBest.getScore(), depth, Entry.ValueType.LOWERBOUND);
         }
 
        else{
             table.insert(newBoard, myBest.getScore(), depth, Entry.ValueType.EXACT_VALUE);
        }
        return myBest;
}

Edited by patishi, 11 June 2013 - 06:04 PM.


Sponsor:



Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS