Speed and Board Storing Choices

[BrettVsop]

As already proposed, I would add a node counter and print number of nodes, elapsed time and nodes per second at the end of the search. This may help to understand your search better. For a 4-ply search from the initial position without quiescence search, even 10000 nodes would be very much but I expect your engine does not need more than 0.5 seconds for 10000 nodes, even with an object-oriented approach which is IMO far from being the root cause of your problems. (Less than 0.1 seconds would be normal, though.) If you need much more nodes, something is wrong.

This sounds very good. Basically you are suggesting a counter variable inside my AlphaBeta loop. Count the number of times it loops? Then divide the time it took to run by that counter?

[BrettVsop]

Ok I updated CMoveList to use an array instead of a vector. I also made all CMoveList objects globals so that they will not be recreated every run and it is running much faster.

I am now running a four ply search in five to ten seconds. I updated the code to count the nodes as well.

34060 nodes in
2546 miliseconds

[YvesLejeail]

It seems to do well though, I see early cutoffs. I am looking into the Quiescence ordering as well.

Also try to skip loosing captures in the Quiescence; if you have no hashtables, you should use history tables or killer moves to help for move ordering
Yves

[BrettVsop]

It seems to do well though, I see early cutoffs. I am looking into the Quiescence ordering as well.

Also try to skip loosing captures in the Quiescence; if you have no hashtables, you should use history tables or killer moves to help for move ordering
Yves

Before I make it more complicated I would like to make sure that what I have written is written well. Do I need to use Quiescence, hashtables, history tables, or killer moves to make any significant improvements to speed?

It still seems really slow and I would like to fix that first.

[Ilari Pihlajisto]

Before I make it more complicated I would like to make sure that what I have written is written well. Do I need to use Quiescence, hashtables, history tables, or killer moves to make any significant improvements to speed?

No, those things just reduce branching and make your search more accurate, which you should not worry about at this point. 34060 nodes in 2546 milliseconds is horribly slow. I second Dann's suggestion to use a profiler.

[Dann Corbit]

Before I make it more complicated I would like to make sure that what I have written is written well. Do I need to use Quiescence, hashtables, history tables, or killer moves to make any significant improvements to speed?

No, those things just reduce branching and make your search more accurate, which you should not worry about at this point. 34060 nodes in 2546 milliseconds is horribly slow. I second Dann's suggestion to use a profiler.

gprof is free and works well enough (I seem to recall he is using gcc anyway).
The Intel and MS VC++ 2005 profilers are much better but both are commercial products.

[Onno Garms]

gprof is free and works well enough (I seem to recall he is using gcc anyway).

valgrind is better and also free. But it is available for Linux only.

[Teemu Pudas]

Before I make it more complicated I would like to make sure that what I have written is written well. Do I need to use Quiescence, hashtables, history tables, or killer moves to make any significant improvements to speed?

No, those things just reduce branching and make your search more accurate, which you should not worry about at this point. 34060 nodes in 2546 milliseconds is horribly slow. I second Dann's suggestion to use a profiler.

gprof is free and works well enough (I seem to recall he is using gcc anyway).
The Intel and MS VC++ 2005 profilers are much better but both are commercial products.

However, the VS beta 2008 profiler (only in Team Suite) is free for the next four months. It's a 3.2 GB download, though.

[Sven Schüle]

Before I make it more complicated I would like to make sure that what I have written is written well. Do I need to use Quiescence, hashtables, history tables, or killer moves to make any significant improvements to speed?

No, those things just reduce branching and make your search more accurate, which you should not worry about at this point. 34060 nodes in 2546 milliseconds is horribly slow. I second Dann's suggestion to use a profiler.

Obviously different opinions exist about what to worry about first.

13400 nps without QS, assuming current hardware, is quite slow, right.

But: 34060 nodes for a 4-ply search from the initial position means that the search has a branching factor of about 12, considering the fixed number of 20 legal first moves of white. This will never allow reasonable play. Between 160 (bf=2) and 2500 (bf=5) nodes might be an "acceptable" range.

So I think you should improve move ordering (several simple ways have been mentioned) and also implement QS (to avoid some obvious blunders), and then I would be interested in your new results. Profiling could result in a speedup by a constant factor which is independent from search depth, so its benefit might become smaller when searching deeper.

QS will also raise nps (has already been mentioned), so your numbers can't be compared directly to nps of "real" engines at the moment.

Sven

[BrettVsop]

I am using Visual Studios 6

Is there any free compilers for VS6? Where can I get that VS beta 2008 profiler?

[Dann Corbit]

I am using Visual Studios 6

Is there any free compilers for VS6? Where can I get that VS beta 2008 profiler?

VS 6 has a profiler called prof.exe (but it only works with C and not C++).

[mageofmaple]

After looking at your code, I think that your problem is that your evaluation function is spending way too much time generating all moves for both players to evaluate the mobility.

Generally, the most expensive part of a chess program (computationally speaking) is the move generation. The second most expensive part, unless you take a very light-weight approach, which is becoming more common, is the evaluation. You have compounded the problem by making your evaluation function invoke a full move generation for not just one, but for both players. I think test #1 is to comment that bit out, and see what your total time and nodes per second is. I'll bet you see a big improvement in nodes/second. Of course, you'll have a lot more nodes because you've erased important logic, but there's a lot of other things that should be put in before a super-heavy expensive evaluation like you have.

Mobility is important, but that is not one of the first things to add, IMHO, particularly because it is dificult to do without taking up too much CPU time. In fact, unless you use bitboards, I don't even know if it is worthwhile at all.

[Teemu Pudas]

Where can I get that VS beta 2008 profiler?

Here.

[Ilari Pihlajisto]

Generally, the most expensive part of a chess program (computationally speaking) is the move generation.

I disagree. I think the evaluation should be by far the heaviest part. Here's how my program (Sloppy) spends its time according to gprof:

Code: Select all

eval        40.2%
gen_moves   22.6%
see         8.0%


The rest is for search, makemove/undomove, input, output, etc. This is with a somewhat fast eval and a legal move generator.

[Fritz Grau]

Before I make it more complicated I would like to make sure that what I have written is written well. Do I need to use Quiescence, hashtables, history tables, or killer moves to make any significant improvements to speed?

1. Quiescence search
The typical evaluation function is very unreliable without Q-search: For example, moving the own queen out in the middle of the field is nearly certain to win at least a pawn at odd search depths (because the search stops before the recapture), but does not generally improve the evaluation at even search depths.

No move ordering technique can help much as long the evaluation is too "noisy", so I believe Q-search is the first thing that needs to be implemented.

2. Hash tables
Very useful for two reasons:
a. Move ordering outside Q-search (you can store killer moves)
b. Avoiding transposed positions (asymptotically good, but not crucial at low search depths, because the first transpositions occur at 4 ply search)

The only problem with hash tables is that one can make many mistakes in their implementation, and debugging becomes much harder, so it might be useful to wait with their implementation until you are happier with the results of your search.

[BrettVsop]

Current Code with Move Generator Evaluate

nodes 498139
time 43078
average 11.5


Without Move Generation Evaluate

node count 165033
time 10500
average 15.7

As you can see the node count for the commented out Move Generation Evaluate has alot less nodes. So this means for some reason Alpha Beta works better on this evaluate. The problem, of course, is that the moves kinda suck a little. Maybe I can replace it with something else that isn't as expensive?

[Sven Schüle]

Current Code with Move Generator Evaluate

nodes 498139
time 43078
average 11.5


Without Move Generation Evaluate

node count 165033
time 10500
average 15.7

As you can see the node count for the commented out Move Generation Evaluate has alot less nodes. So this means for some reason Alpha Beta works better on this evaluate. The problem, of course, is that the moves kinda suck a little. Maybe I can replace it with something else that isn't as expensive?

I guess these figures are now from a 5-ply search from initial position, and still without QS, am I right?

Leaving out your mobility term seems not to give the nps speedup one might have expected at a first glance (15700 vs 11500 = +37%), so this was probably not the major performance bottleneck. On the other hand, as you stated, the pure material-only based search results in even worse play. So I would leave mobility in, although it is quite expensive.

Reduced number of nodes with material-only eval is not unexpected for me. A possible explanation would be that now there is a higher probability that many nodes get an identical evaluation, so the number of early cutoffs increases because many moves get refuted simply due to not winning material.

Nevertheless the branching factor seems to be quite high.

Examples for adding cheap evaluation terms are a piece-square table and the distance of each piece to the enemy king. Detecting whether the king is protected well by own pawns is also quite simple, and if he is not, you might penalize a king on e1/e8 when both castle rights are lost. Possessing the pair of bishops, or a Rook or Queen on 7th rank are cheap terms, too. All these should have different weights depending on game phase (opening/endgame).

A more detailled analysis of king safety, pawn structure and especially passed pawns might become necessary to become competitive somehow, but evaluating these terms is a bit more expensive.

Btw another question, how do you implement the legality check within your move generator? Do you make/unmake each single move and determine whether the king is left in (or put into) check, or do you restrict legality tests to king moves, moves when being in check, and moves of pinned pieces?

Sven

[BrettVsop]

I am not using any bitboards, so I do not know which pieces are pinned. That is really interesting, the idea of only checking certain moves for check. But to fully answer your question, I make moves, check legality, then unmake moves.

Also still no QS.

I am now doing a depth of 5. Removing the move counter allowed me add one more ply. Even though it took a while, I kept it at 5 when checking the move count as well.

I tried running the code a little differently. I removed the legality test and searched for all moves instead of legal moves. The results were much better.

Legal Moves, depth 5
node count 165033
time 9938

All Moves Depth 7
node count 1107606
time 12281

During middle and end game this should be fine because capturing the king will result in huge material inbalance. The only problem with this approach is stalemate. Most of the problems associated with that will be at during the endgame. I may leave it this way until it gets to the endgame.

[Fritz Grau]

You have obviously found the bottleneck. As you say "The only problem with this approach is stalemate.", I assume that you consider a position won if the enemy king can be captured? But then you could just return a special evaluation "illegal" to inform the parent node, and the parent node would be able to check if all moves are illegal, so the position is stalemate.

Another question: If removing Making/UnMaking from the move generator speeds your engine up by a factor of 5, this process is obviously much slower than the rest of your engine, and you might get additional speedup by reducing its cost (because moves still need to be made before branching).

Probably a lot of time in making moves is spent to allocate/copy memory. So it would be worthwhile to reduce (1) the number of memory allocations (2) the size of the structure. You said that you store the game history in the move list. If you store it as a linked list (better style, but many allocations) you could gain much by changing it into an array. If the history is not crucial for your search (e.g. for detecting repetition draws), it would be a great advantage to extract it from that structure.

[BrettVsop]

You have obviously found the bottleneck. As you say "The only problem with this approach is stalemate.", I assume that you consider a position won if the enemy king can be captured? But then you could just return a special evaluation "illegal" to inform the parent node, and the parent node would be able to check if all moves are illegal, so the position is stalemate.

That is interesting. I think that is what I am going to do.

Another question: If removing Making/UnMaking from the move generator speeds your engine up by a factor of 5, this process is obviously much slower than the rest of your engine, and you might get additional speedup by reducing its cost (because moves still need to be made before branching).

I am confused about what you are talking about. How can I determine if removing making and unmaking speeds my engine by 5? I kind of need that code for the alpha beta to work at all. I tried removing it before by using a copy of the board to make the move, but I think you can guess how slow that was

Probably a lot of time in making moves is spent to allocate/copy memory. So it would be worthwhile to reduce (1) the number of memory allocations (2) the size of the structure. You said that you store the game history in the move list. If you store it as a linked list (better style, but many allocations) you could gain much by changing it into an array. If the history is not crucial for your search (e.g. for detecting repetition draws), it would be a great advantage to extract it from that structure.

I use an array to store move history. Here it is

Code: Select all

struct SUndoMove
{
   int iStartSquare;
   int iEndSquare;

   int iCapturedPiece;
   bool bPromotion;

   int iCastleFlags[2];
   int iEnPassantSquare;
};