Author: Tim Foden
Date: 02:51:39 05/07/03
Go up one level in this thread
On May 07, 2003 at 04:57:03, Magoo wrote:
>On May 07, 2003 at 03:56:33, Tim Foden wrote:
>
>>On May 06, 2003 at 19:24:23, Magoo wrote:
>>
>>>After making alot of functions to macros and alot of other stuff, my program is
>>>much faster!!
>>>Perft 5 (without evaluating nodes) gives:
>>>Depth:5, Nodes:5072212, Time:63 sec, Nps:80511, Value:0
>>>
>>>But!! I know other programs (i been looking at mscp and faile) do this
>>>at least 6 times faster, (that is perft 5 < 10sec).
>>>I've looked at the source for the programs i compare with, especially faile does
>>>alot of stuff in the move_generator, mine is smaller, maybe a few more if
>>>statments.
>>>Now, if i only could figure out why it is so slow, it shouldn't be!!
>>>
>>>Flat profile:
>>>
>>>Each sample counts as 0.01 seconds.
>>> % cumulative self self total
>>> time seconds seconds calls s/call s/call name
>>> 66.51 42.12 42.12 5087588 0.00 0.00 move_generator
>>
>>> 3.65 56.68 2.31 5087587 0.00 0.00 undo_move
>>> 3.21 58.71 2.03 5087587 0.00 0.00 do_move
>>
>>Does your move generate generate all moves in a position in one go, or do you
>>only generate one move at a time?
>>
>>If you are generating all moves in one go, then it looks like you are calling
>>your movegen in the leaf nodes. You really should have much fewer calls to your
>>movegen than to your make/unmake move routines.
>>
>>Cheers, Tim.
>
>Yes, i do call move_generator in the leaf nodes, i have no better way to check
>if a move is legal... i look at the moves generated and look for "YxK", that is
>a move where the king is captured, then i just return -INFINITY and decrease the
>node count..
As Uri said, it is quicker to have an explicit test for this. It is much faster
to have an explicit test whether the king is in check, than it is to generate
all moves, and then test each one to see if it is valid.
Here is the eqivalent perft code from Green Light:
void BruteForce( int ply, int depth, bool dumpTree )
{
if( depth <= 0 )
return;
int nextDepth = depth - 1;
int nextPly = ply + 1;
static CMoveListBase moveListBase(5120, 100);
CMoveList moves(moveListBase, ply);
CBoard::GetAttackingMoves( moves );
int nMoves = moves.GetSize();
for( int i = 0; i < nMoves; i++ )
if( moves[i].GetTaken() == wKing )
return;
CBoard::GetNonCaptureMoves( moves );
nMoves = moves.GetSize();
for( i = 0; i < nMoves; i++ )
{
CMove move = moves[i];
CBoard::MakeMove( move );
/* if( dumpTree )
{
Print( "%2d %3d %s\n", ply, i, move.GetString() );
}*/
if( nextDepth )
{
INT64 n = s_nBruteForceNodes;
BruteForce( nextPly, nextDepth, dumpTree );
if( dumpTree && ply == 0 )
{
Print( "%s - %I64d\n", (const char*)move.GetString(),
s_nBruteForceNodes - n );
}
}
else if( !CBoard::IsInCheck(!CBoard::m_wtm) )
s_nBruteForceNodes++;
CBoard::UnMakeMove();
}
}
You can see a number of differences between this an your current code:
1. The test for a leaf node is done before any moves are generated. (In fact
this test is not actually required (see 3 below), but it is there for safety)
2. I only generate captures before testing if we are in a legal position. (It
may be quicker to test using the IsInCheck call here, but it may not.) As the
majority of positions are valid, and we know we are going to use the moves we
generate in this node anyway, this may not be such a big performance loss. But
I will test it and see :)
3. Leaf nodes are detected before a recursive call is made, and IsInCheck is
used to test if it is a valid node.
As Green Light is a rotated bitboard program the IsInCheck call is relatively
simple (I'm sure it can be improved (see Sune Fisher's perft example code), but
that's life) :-)
Here is the IsInCheck code from Green Light:
/*--------------------------------------------------------------------------*/
bool IsInCheck( bool kingIsWhite )
{
if( kingIsWhite )
{
Square pos = m_kingPos[white];
return (m_pawnAttacks[2][1][pos] & m_pawnBoard[0]) ||
(m_knightAttacks[pos] & m_knightBoard[0]) ||
(GenBishopMovesBitmap(pos) &
(m_bishopBoard[0] | m_queenBoard[0])) ||
(GenRookMovesBitmap(pos) &
(m_rookBoard[0] | m_queenBoard[0])) ||
(m_kingAttacks[pos] & m_kingBoard[0]);
}
else
{
Square pos = m_kingPos[black];
return (m_pawnAttacks[2][0][pos] & m_pawnBoard[1]) ||
(m_knightAttacks[pos] & m_knightBoard[1]) ||
(GenBishopMovesBitmap(pos) &
(m_bishopBoard[1] | m_queenBoard[1])) ||
(GenRookMovesBitmap(pos) &
(m_rookBoard[1] | m_queenBoard[1])) ||
(m_kingAttacks[pos] & m_kingBoard[1]);
}
}
Cheers, Tim.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.