ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

broken?
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Sven Schüle



Joined: 15 May 2008
Posts: 2240
Location: Berlin, Germany
PostPost subject: Re: broken?    Posted: Sun Jul 08, 2012 11:25 pm Reply to topic Reply with quote
Hi Folkert,

please check out the code below (resp. pseudocode for my tiny addition "SearchControl"). It's negamax, and I put in a regular legality + mate dectection + timeout handling + check extension code using mostly your method names. I also added a very simple iterative deepening in findBestMove() which returns the best move (not the best score). Would be interesting to see how that works.

Code:
int alphaBeta(final Scene scene, final PlayerColor side, int depth, int height, final IO io, int alpha, int beta, final SearchControl control)
{
   // keep track of the number of processed nodes
   nodeCount.addAndGet(1);

   if (control.isTimeOut(Statics.getTimestamp())) {
      // note: should not happen at root
      control.abortSearch();
      io.progressCallback("Abort search due to time limit");
      return +INFINITY;
   }

   final PlayerColor otherSide = Statics.opponentColor(side);
   bool isInCheck = scene.isKingUnderAttack(side, otherSide);
   if (isInCheck) {
      depth++;
   }
   if (depth <= 0) {
      return getShannonValue(scene, side); // score
   }

   scene.validateMoves(side); // should only generate moves for "side" and possibly order them appropriately;
                              // if also legality is tested for each move then the other legality testing code
                              // can be removed from the loop body, and mate/stalemate detection can be moved
                              // to the line below this comment

   final List<Move> moves = scene.getMoveList(side);
   int movesListSize = moves.size();
   totalNMoves.addAndGet(movesListSize);
   totalNodes.addAndGet(1);
   int nLegalMoves = 0;
   for(int index=0; index<movesListSize; index++) {

      // "do a move", 'afterMove' is the "situation" after 'currentMove' was executed
      Scene sceneAfterMove = null;
      final Move currentMove = moves.get(index);
      try {
         sceneAfterMove = currentMove.getScene();
         if (sceneAfterMove == null) {
            sceneAfterMove = scene.Move(currentMove);
         } else {
            currentMove.setScene(null); // help GC, link is not required
         }
      }
      catch(Exception e) {
         System.out.println(" side: " + side + " alpha " + alpha + " beta " + beta);
         System.out.println(" " + (depth + 1) + " " + currentMove);
         Statics.displayBoard(afterMove.getBoard());
         System.out.println("" + e);
         e.printStackTrace();
         System.exit(1);
      }

      if (sceneAfterMove.isKingUnderAttack(side, otherSide)) {
         // illegal move
         continue;
      }
      nLegalMoves++;

      final int score = -alphaBeta(sceneAfterMove, otherSide, depth - 1, height + 1, -beta, -alpha);
      sceneAfterMove.shrink();

      if (control.wasSearchAborted()) {
         return +INFINITY; // will be ignored by parent who negates the score and never finds -INFINITY
                           // to be better than his best move so far
      }

      if (score >= beta) {
         return beta;
      }
      if (score > alpha) {
         alpha = score;
         if (height == 0) {
            control.setBestMove(currentMove);
         }
      }
   }
   if (nLegalMoves == 0) {
      if (isInCheck) {
         // mated
         return -(INFINITY - height);
      } else {
         // stalemate
         return 0;
      }
   }

   return alpha;
}

Move findBestMove(final Scene scene, final PlayerColor side, final double finishBefore, int depth, final IO io)
{
   SearchControl control = new SearchControl(finishBefore);
   for (int d = 1; d <= depth && !control.isSearchAborted(); d++) {
      int bestValue = alphaBeta(scene, side, d, 0, io, -INFINITY, +INFINITY, control);
   }
   return control.bestMove();
}

public class SearchControl ...
// abstraction for timeout checking, aborting search, and best root move
// provides methods:
// SearchControl(finishBefore) => sets abort flag to false and best root move to null, stores "finishBefore"
// abortSearch()               => sets abort flag to true
// wasSearchAborted()          => queries abort flag
// bestMove()                  => returns best root move
// setBestMove(move)           => stores new best root move
// isTimeOut(timeStamp) => returns true if (finishBefore > 0 && finishBefore <= timeStamp)


Sven
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Subject Author Date/Time
broken? Folkert van Heusden Sun Jul 08, 2012 5:01 pm
      Re: broken? Tim Kosse Sun Jul 08, 2012 5:43 pm
            Re: broken? Folkert van Heusden Sun Jul 08, 2012 6:13 pm
      Re: broken? Zong Li Sun Jul 08, 2012 5:47 pm
            Re: broken? Folkert van Heusden Sun Jul 08, 2012 6:15 pm
                  Re: broken? Zong Li Sun Jul 08, 2012 6:37 pm
                        Re: broken? Folkert van Heusden Sun Jul 08, 2012 6:53 pm
                              Re: broken? Tim Kosse Sun Jul 08, 2012 7:04 pm
                                    Re: broken? Folkert van Heusden Sun Jul 08, 2012 7:35 pm
                                          Re: broken? Sven Schüle Sun Jul 08, 2012 9:15 pm
                                                Re: broken? Balint Pfliegel Sun Jul 08, 2012 9:56 pm
                                                      Re: broken? Zong Li Sun Jul 08, 2012 11:31 pm
                                                Re: broken? Sven Schüle Sun Jul 08, 2012 11:25 pm
                              Re: broken? Zong Li Sun Jul 08, 2012 7:35 pm
      Re: broken? Sven Schüle Sun Jul 08, 2012 6:01 pm
            Re: broken? Folkert van Heusden Sun Jul 08, 2012 6:25 pm
      Re: broken? Aart Bik Sun Jul 08, 2012 10:22 pm
            Re: broken? Balint Pfliegel Sun Jul 08, 2012 10:40 pm
                  Re: broken? Adam Hair Mon Jul 09, 2012 12:22 am
                  Re: broken? Aart Bik Mon Jul 09, 2012 12:37 am
                        Re: broken? Aart Bik Mon Jul 09, 2012 12:57 am
                        Re: broken? Balint Pfliegel Mon Jul 09, 2012 5:47 am
      Re: broken? Aart Bik Mon Jul 09, 2012 4:45 pm
            Re: broken? Folkert van Heusden Mon Jul 09, 2012 6:35 pm
                  Re: broken? Zong Li Mon Jul 09, 2012 6:49 pm
                        Re: broken? Folkert van Heusden Mon Jul 09, 2012 7:17 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads