[chess engine programming] minimax and alpha-beta. 3-4 plies. Normal?

This is a discussion on [chess engine programming] minimax and alpha-beta. 3-4 plies. Normal? within the C++ Programming forums, part of the General Programming Boards category; Hi, I have being writing a chess engine and has just began the AI part (finished move generation and implemented ...

  1. #1
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167

    [chess engine programming] minimax and alpha-beta. 3-4 plies. Normal?

    Hi,
    I have being writing a chess engine and has just began the AI part (finished move generation and implemented all the rules). What I have implemented so far is a simple minimax with alpha-beta prunning (random ordering). The evaluation function only takes material balance into account. Boards are implemented using bitboards (simple ray-through for sliding pieces, no rotated bitboards). Currently, on ~10 seconds per move, I get 5 plies at the beginning, 3-4 in middlegame and endgame (without opening book and endgame database). Does that seem normal? To me the numbers seem pretty low, but I have no prior experience in chess programming.

    Thank you very much

  2. #2
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,235
    Quote Originally Posted by cyberfish View Post
    Hi,
    I have being writing a chess engine and has just began the AI part (finished move generation and implemented all the rules). What I have implemented so far is a simple minimax with alpha-beta prunning (random ordering). The evaluation function only takes material balance into account. Boards are implemented using bitboards (simple ray-through for sliding pieces, no rotated bitboards). Currently, on ~10 seconds per move, I get 5 plies at the beginning, 3-4 in middlegame and endgame (without opening book and endgame database). Does that seem normal? To me the numbers seem pretty low, but I have no prior experience in chess programming.
    How good or bad that depth is depends on your game playing performance. If you're only looking to 5 ply but you're kicking butt, it doesn't really matter much.

    There's a complex interaction going on here. If your evaluation function is complex, then evaluating each move takes longer. But if the values are BETTER, this leads to better play, because you maximize the benefits of move ordering for alpha-beta, and you don't have to search as deep to get a reasonable estimate of the board evaluation. If your evaluation function is braindead, you should be able to search a few ply deeper -- if you're not, there's something wrong with logic elsewhere in the program.

    Even a poor evaluation function can perform well, if you are able to search deep enough.

    Can you give any more details about your evaluation function? Are you using a transposition table? Are you using incremental move ordering? Are you using iterative deepening?

  3. #3
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    Thank you for your reply.
    How good or bad that depth is depends on your game playing performance. If you're only looking to 5 ply but you're kicking butt, it doesn't really matter much.
    Doesn't seems like that is the case. I can beat it very easily and I have a rating of ~1000 on FICS =)
    If your evaluation function is braindead, you should be able to search a few ply deeper -- if you're not, there's something wrong with logic elsewhere in the program.
    That is what I thought, too, but I don't see what is wrong. The evaluation is braindead.

    Can you give any more details about your evaluation function? Are you using a transposition table? Are you using incremental move ordering? Are you using iterative deepening?
    I am using iterative deepening, but results from previous depths are discarded (for now). There is currently no transposition table, or incremental move order (except I search the captures first).

    here is my evaluation function -
    Code:
    int staticEvaluate(Board &board) {
    	
    	int result = 0;
    	
    	//BEGIN: material balance
    	
    	int sum = 0;
    	
    	for (int i = 0; i != 64; ++i) {
    		PieceType at_type = board.getType(i);
    		if (at_type != EMPTY) {
    			sum += BaseValues[at_type];
    		}
    	}
    	
    	result += sum;
    	
    	//END: material balance
    		
    	return result;
    	
    }
    Thank you

  4. #4
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    based on the result of gprof, it appears that my engine evaluates about 1.2 million moves per second. I guess I will just move on to implement other algorithms and optimizations.

  5. #5
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,235
    Quote Originally Posted by cyberfish View Post
    based on the result of gprof, it appears that my engine evaluates about 1.2 million moves per second. I guess I will just move on to implement other algorithms and optimizations.
    Move ordering, move ordering, move ordering! Start taking advantage of your iterative deepening. Usually this is implemented with a transposition table, but you can do it without one as well.

  6. #6
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    Move ordering, move ordering, move ordering! Start taking advantage of your iterative deepening. Usually this is implemented with a transposition table, but you can do it without one as well.
    Thank you for your suggestion =). I understand the importance of move ordering, but I just wanted to make sure that my basic implementations of minimax and alpha-beta are fine before I move on to things like transposition table. The depth it currently reaches scares me a bit though (3-4 plies in midgame with an extremely simple evaluation function).

    Thank you

  7. #7
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    about 1.2 million moves per second
    hmm I think I made a mistake in interpreting gprof result. My engine is actually only searching ~30000 positions per second. I guess something is seriously wrong...

  8. #8
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,235
    Quote Originally Posted by cyberfish View Post
    hmm I think I made a mistake in interpreting gprof result. My engine is actually only searching ~30000 positions per second. I guess something is seriously wrong...
    Can you post the function coverage profile -- not the entire thing, just the first level table?

  9. #9
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    Can you post the function coverage profile -- not the entire thing, just the first level table?
    Thank you for your help, it's much appreciated. I am not sure what is the function coverage profile. Is it the same as the "flat profile"? Here is the flat profile section:
    Code:
    Flat profile:
    
    Each sample counts as 0.01 seconds.
      %   cumulative   self              self     total           
     time   seconds   seconds    calls   s/call   s/call  name    
     42.55      1.29     1.29  7837472     0.00     0.00  Board::canCapture(unsigned long long)
     17.88      1.83     0.54   277323     0.00     0.00  Board::generateLazyMoves()
     16.72      2.33     0.51  7837494     0.00     0.00  Board::Board(Board&, Move)
     11.26      2.67     0.34       80     0.00     0.04  MiniMax(Board&, int, int, int, int&)
      4.64      2.81     0.14  1723099     0.00     0.00  std::vector<Move, std::allocator<Move> >::_M_insert_aux(__gnu_cxx::__normal_iterator<Move*, std::vector<Move, std::allocator<Move> > >, Move const&)
      3.31      2.91     0.10   277204     0.00     0.00  Board::validateMoves_rtnBoard(std::vector<Move, std::allocator<Move> >*)
      2.98      3.00     0.09  1672405     0.00     0.00  std::vector<Board, std::allocator<Board> >::_M_insert_aux(__gnu_cxx::__normal_iterator<Board*, std::vector<Board, std::allocator<Board> > >, Board const&)
      0.50      3.02     0.02    17786     0.00     0.00  Board::underAtk(unsigned long long)
      0.17      3.02     0.01                             Board::getTypeAsArray(int*) const
      0.00      3.02     0.00      131     0.00     0.00  beginsWith(char*, std::string&)
      0.00      3.02     0.00      119     0.00     0.00  Board::generateMoves()
      0.00      3.02     0.00      119     0.00     0.00  Board::validateMoves(std::vector<Move, std::allocator<Move> >*)
      0.00      3.02     0.00      117     0.00     0.00  Board::getGameState()
      0.00      3.02     0.00        8     0.00     0.00  std::vector<int, std::allocator<int> >::_M_insert_aux(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, int const&)
      0.00      3.02     0.00        2     0.00     0.00  checkClaimDraw(std::vector<Board, std::allocator<Board> >&, Move&, bool)
      0.00      3.02     0.00        1     0.00     0.00  global constructors keyed to kingAtk
      0.00      3.02     0.00        1     0.00     0.00  algeToMove(std::string, Board*, signed char)
      0.00      3.02     0.00        1     0.00     0.00  moveToAlge(Move)
      0.00      3.02     0.00        1     0.00     0.00  computeConst()
      0.00      3.02     0.00        1     0.00     3.02  findBestMove(Board, int&, unsigned long, int, bool)
      0.00      3.02     0.00        1     0.00     0.00  __static_initialization_and_destruction_0(int, int)
      0.00      3.02     0.00        1     0.00     0.00  char* std::string::_S_construct<char*>(char*, char*, std::allocator<char> const&, std::forward_iterator_tag)
    and in case it is of any use, here is the full output -
    http://cyberfish.wecheer.com/gprof_out.txt

    the Board::canCapture() function is a function used to determine whether the moving side can capture a particular piece. Currently, the only use of this function is in move validation (making moving into check or leaving the king in check impossible).

    the Board::generateLazyMoves() function generates all legal moves but does not check whether the moves will leave the king in check.

    the Board::Board(Board&, Move) constructor constructs a new board by copying an old board and applying a move.

    in the profiled run, I started a new game and set the engine to play black with a time control of 5 minutes per move, and I typed in the move "e2e4", and then quit.

    or, in xboard protocol:
    Code:
    xboard
    protover 2
    level 40 5 0
    new
    random
    usermove e2e4
    quit
    Thank you very much

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I'm a little surprised that your board constructor(copying) takes so much time - yes it's called 8 million times, and that's certainly a lot. Are you using a loop to copy the content of the board or something like memcpy()?

    --
    Mats

  11. #11
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    I'm a little surprised that your board constructor(copying) takes so much time - yes it's called 8 million times, and that's certainly a lot. Are you using a loop to copy the content of the board or something like memcpy()?
    thank you for your help. I am using memcpy to copy the board (~180 bytes). My wild guess would be because the constructor is full of branching (checking for castling, en passant, promotion, see if castling availability changed etc).

    [edit]
    Just had a look at the constructor code, it looks pretty ugly with all the if's. I will try rewriting it and see what happens.
    [/edit]
    Last edited by cyberfish; 08-17-2007 at 08:01 AM.

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Branches are bad for modern processors, so if you can make them go away (or make them more predictable) then that's a good thing.

    Copying 180 bytes * 8 million times = 1.4GB, so it will take a little bit of time... Of course, it's presumably not copying to a new location every time, so hopefully the processor cache will help some of the time at least - I take it you're not building and keeping 8 million boards, but rather creating one, checking the move and then destroying the board after evaluating the result of the move, yes?

    --
    Mats

  13. #13
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    Thank you for your reply.

    I am currently rewriting this constructor to minimize branches, but can you please explain what do you mean by "making them more predictable"?

    And I am destroying boards once they are done with. There are no more than 500 boards in memory at any time.

  14. #14
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Well, if branches are "predictable", in other words, the branch is taken in one direction every time (or nearly all the time) then the processor will be able to "predict" the correct path to take. Unpredictable would be something like this:

    Code:
    char str[] = "aAbDeEcDDeCaarE";
    
    int i, uc = 0, lc = 0;
    int len = strlen(str)
    for(i = 0; i < len; i++) 
    {
        if (isupper(str[i]) uc++; else lc++;
    }
    Since the upper/lower case letters are all scrambled in different order, the processor wouldn't be able to predict one from the other. If you sorted the string, it would have all the lower-case at one end and the upper case at the other, and thus prediction would work except for the first and the "split-point".

    Not sure if you can do anything about that, tho'.

    By the way, if the compiler is clever, it can do the above code without branches at all, and when I tested it, it was about 4x faster with branches eliminated compared to branches - I sent the suggestion to someone in the GCC group about 4 years back, and I has pleasantly surprised when I saw some of the suggested code when looking at the output of a gcc compiled code-snippet. I also think MS compilers do the same thing if it's feasible.

    --
    Mats

  15. #15
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    I see, thank you for the explanation, but I don't think I can do anything about that in my code =)

    by the way, I am using gcc 4.1.3 on Linux, so I guess I am benefited by your suggestion.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21