Improve my chess engine (mainly nps and branching factor)

[mar]

English draughts is played on a chessboard with 3 rows of men each in the initial position. It's in 10x10 International draughts (4 rows of men each) where very large move lists can be a problem for engines with fixed move arrays. There exist positions with hundreds (~900) moves, which come about from equivalent capture sequences of 10+ pieces along different routes. You could of course eliminate them by comparing the locations of captured pieces but that also has a cost. I typically allocate stack for 16 moves and go to the heap if more moves are required.

Well.. 900+ moves, long capture sequences (a move that is composed of x captures...). I wrote a simple engine for a similar game (much simpler than draughts though), my solution to the problem was to simply have a very simple move structure (say from, to) and to treat all non-terminal positions [i.e. where you are forced to move] as 1-ply search extensions.
That way you only have a couple of moves per position to deal with and fixed move representation.

[adityapande]

Well... how do you expect to perform with stuff like this:

Code: Select all

Move *tmp = new Move(*move);

storing UCI move string in Move structure (ok only a static array but still),
indexing out of bounds (debug mode vector should catch it for you)
and who knows what else. Your engine is obviously original so thumbs up.

My suggestion is to fix bugs, simplify move and board structure, use negamax to get rid of separate min/max code,
generate moves on stack (you use depth-first search anyway, I see no point in holding the whole tree in a dynamic structure, you even dynamically allocate each move!)
maximum number of moves per position should be no more than 256 (there is an exact number that you can google, it's less than that, 218 IIRC).
Just be careful to avoid excessive stack usage (typically apps can use 1 meg/512 kb).

Thanks the idea worked but I didn't get much speedup because earlier because of memorization the move order was always good because of the iterative deepening and sorting the last iteration's evaluation.

Also I guess using STL vectors don't clean up completely on .clear(). Is it so? After moving the Move tree to the stack this memory leak issue was finally solved

Thank you everyone I have implemented hash_table as an array this time and will look forward to try to implement futility pruning, LMR, vectors->arrays, pseudo legal move_gen and see how much these help out

[adityapande]

Well... how do you expect to perform with stuff like this:

Code: Select all

Move *tmp = new Move(*move);

storing UCI move string in Move structure (ok only a static array but still),
indexing out of bounds (debug mode vector should catch it for you)
and who knows what else. Your engine is obviously original so thumbs up.

My suggestion is to fix bugs, simplify move and board structure, use negamax to get rid of separate min/max code,
generate moves on stack (you use depth-first search anyway, I see no point in holding the whole tree in a dynamic structure, you even dynamically allocate each move!)
maximum number of moves per position should be no more than 256 (there is an exact number that you can google, it's less than that, 218 IIRC).
Just be careful to avoid excessive stack usage (typically apps can use 1 meg/512 kb).

Thanks the idea worked but I didn't get much speedup because earlier because of memorization the move order was always good because of the iterative deepening and sorting the last iteration's evaluation.

Also I guess using STL vectors don't clean up completely on .clear(). Is it so? After moving the Move tree to the stack this memory leak issue was finally solved

Thank you everyone I have implemented hash_table as an array this time and will look forward to try to implement futility pruning, LMR, vectors->arrays, pseudo legal move_gen and see how much these help out

[mar]

Also I guess using STL vectors don't clean up completely on .clear(). Is it so? After moving the Move tree to the stack this memory leak issue was finally solved

That's correct. clear keeps current capacity, just sets size to zero (*and a bit more but that's not important if you store elementary/POD types).
If you want to physically free all memory used by vector, you have to either swap it with a temporary empty vector (pre-C++11 solution) or use a combination of clear() and shrink_to_fit().
Of course all memory is freeed automatically once vector itself is destroyed.
Having a fast clear() is not bad though, especially when you can reuse it later and avoid new memory allocation, it really depends on the situation.
I doubt the vector was the culprit of the leaks though.
Anyway, good luck with your engine.

[Rein Halbersma]

Well.. 900+ moves, long capture sequences (a move that is composed of x captures...). I wrote a simple engine for a similar game (much simpler than draughts though), my solution to the problem was to simply have a very simple move structure (say from, to) and to treat all non-terminal positions [i.e. where you are forced to move] as 1-ply search extensions.
That way you only have a couple of moves per position to deal with and fixed move representation.

Uniform representation is nice indeed. Perhaps I could do something like the Small Buffer Optimization where I keep up to 8 chars (one byte per captured piece) inside the Move struct, and use a union to change that to a pointer to dynamically allocated list of captured pieces when there are more than 8.

[adityapande]

But adding futility pruning/razoring and LMR will help a bit.

I added futility but it rather slows down the search slightly.
Only 1 in 200 does the cut off occur which is costing more loss than gain
Please help

I have implemented it as

Code: Select all

alphabeta(int alpha,int beta,bool maximizingPlayer)
....

int futile=DINF;
if(depth==2 && alpha<HINF && alpha>-HINF && beta<HINF && beta>-HINF && move->capture<'A' && !isCheck(turn()))
{
QUIET_CUT=0;//QS will now give the static eval of position
futile = alphabeta(move->children[i],0, alpha, beta, false) + 300;
QUIET_CUT=10;
 }

int result;
g2++;//for measuring the ratio of nodes giving cut off
if(futile<alpha){result = alpha;g1++;}
else
result = alphabeta(move->children[i],depth - 1, alpha, beta, false);
....

[ZirconiumX]

But adding futility pruning/razoring and LMR will help a bit.

I added futility but it rather slows down the search slightly.
Only 1 in 200 does the cut off occur which is costing more loss than gain
Please help

I have implemented it as

Code: Select all

alphabeta(int alpha,int beta,bool maximizingPlayer)
....

int futile=DINF;
if(depth==2 && alpha<HINF && alpha>-HINF && beta<HINF && beta>-HINF && move->capture<'A' && !isCheck(turn()))
{
QUIET_CUT=0;//QS will now give the static eval of position
futile = alphabeta(move->children[i],0, alpha, beta, false) + 300;
QUIET_CUT=10;
 }

int result;
g2++;//for measuring the ratio of nodes giving cut off
if(futile<alpha){result = alpha;g1++;}
else
result = alphabeta(move->children[i],depth - 1, alpha, beta, false);
....

Your code is pretty difficult to read. For instance, you call what seems to be QS to get the position score - you shouldn't need to. In addition, I think the !isCheck(turn()) is pointless - you want to see if the move is checking, not if the opponent is in check (if the opponent *is* in check, the position is illegal).

An improvement would be also doing it on depth 1 with a smaller margin. In addition, it would make sense to store the move as a local variable, instead of accessing it every time it is referenced.

Matthew:out

[adityapande]

But adding futility pruning/razoring and LMR will help a bit.

I added futility but it rather slows down the search slightly.
Only 1 in 200 does the cut off occur which is costing more loss than gain
Please help

I have implemented it as

Code: Select all

alphabeta(int alpha,int beta,bool maximizingPlayer)
....

int futile=DINF;
if(depth==2 && alpha<HINF && alpha>-HINF && beta<HINF && beta>-HINF && move->capture<'A' && !isCheck(turn()))
{
QUIET_CUT=0;//QS will now give the static eval of position
futile = alphabeta(move->children[i],0, alpha, beta, false) + 300;
QUIET_CUT=10;
 }

int result;
g2++;//for measuring the ratio of nodes giving cut off
if(futile<alpha){result = alpha;g1++;}
else
result = alphabeta(move->children[i],depth - 1, alpha, beta, false);
....

Your code is pretty difficult to read. For instance, you call what seems to be QS to get the position score - you shouldn't need to. In addition, I think the !isCheck(turn()) is pointless - you want to see if the move is checking, not if the opponent is in check (if the opponent *is* in check, the position is illegal).

An improvement would be also doing it on depth 1 with a smaller margin. In addition, it would make sense to store the move as a local variable, instead of accessing it every time it is referenced.

Matthew:out

The depth part is surely right
I forgot to add the part that it is being done for every child as seen at depth 2 => depth 1 basically
Also the check condition is mentioned as a prerequisite on chessprogramming wiki https://chessprogramming.wikispaces.com ... ty+pruning