Author: Dann Corbit
Date: 18:03:02 02/21/06
Go up one level in this thread
On February 21, 2006 at 21:00:26, Dann Corbit wrote:
>On February 21, 2006 at 20:16:33, Sean Mintz wrote:
>
>>I have been working on the basic underpinnings of an 0x88 program. By today it
>>had gotten to the point where it was working well enough that I could tinker and
>>make some comparisons.
>>
>>The initial version's move generator is, in terms of its code, very long.
>>
>>1. Generate castling moves
>>2. Generate en passant moves
>>3. Big switch statement, seperated by each type of piece. Pawn is seperated
>>further into white and black and each of those is split into normal or promotion
>>moves.
>>
>>The attack function in this program ( used to determine whether the king is in
>>check ) is very similar to the move generator. It sort of generates the moves
>>backwards to determine whether the square is being attacked.
>>
>>The code for this version is fairly lengthy, but runs quite fast.
>>
>>Today I tried rewriting the move generator and the attack function to be shorter
>>and to take advantage of some of the talked about "tricks" of 0x88 (
>>specifically in the attack function ).
>>
>>The move generator now looks like this:
>>
>>1. Generate castling moves
>>2. Generate en passant moves
>>3. Smaller switch statement. Do pawn moves, but then do all other moves together
>>( has an array to determine whether a piece is a slider or not, and a
>>multidimensional array that says which directions a piece can go )
>>
>>The attack function is similar to that of Gerbil, but I do pawns seperately ( as
>>opposed to having another multidimensional array to handle the pawns ).
>>
>>On to the tests:
>>
>>First I perft to a depth of 6. This takes reasonably long.
>>
>>After that I do 3 repetitive tests.
>>
>>First I generate all 20 moves for the initial position 2.5 million times.
>>Then I make and unmake each of those 20 moves 2.5 million times.
>>Then I run the attack function on the white AND black king 2.5 million times (
>>so the attack function runs 5 million times ).
>>
>>On to the results:
>>
>>Version One
>>
>>Calculating Perft to depth 6 ... 119060324
>>Took 19.44 seconds
>>Performing Move Generator Test ... Took 0.922000 seconds
>>Performing Move Make Test ... Took 2.243000 seconds
>>Performing Attack Test ... Took 0.320000 seconds
>>
>>Version Two
>>
>>Calculating Perft to depth 6 ... 119060324
>>Took 24.48 seconds
>>Performing Move Generator Test ... Took 1.932000 seconds
>>Performing Move Make Test ... Took 2.214000 seconds
>>Performing Attack Test ... Took 0.410000 seconds
>>
>>I was personally surprised to see the second version running so much slower.
>>
>>Sean Mintz
>
>I am not surprised it is slower.
>
>A switch statement can be programmed relatively efficiently when all the jump
>labels are known before hand. So changing:
>/*******************************************/
>switch (foo)
>{
>case a:
>break;
>case b:
>break;
>case c:
>break;
>case d:
>break;
>case e:
>break;
>case F:
>break;
>default:
>}
>/*******************************************/
>
>into:
>
>/*******************************************/
>if (a)
>{
>}
>else if(b)
>{
>}
>else {
> switch (foo)
> {
> case c:
> break;
> case d:
> break;
> case e:
> break;
> case F:
> break;
> default:
> }
>}
>/*******************************************/
>
>is going to be a lot slower. Since castling and e.p. are quite rare compared to
>all other moves, I guess also that branch misprediction will be the norm. Even
>if that is not the case, you have changed one test and branch into three of
>them.
>
>I also think that the generic switch is a better idea from a clarity standpoint.
>
>Your exercise is a good example of the principle:
>1. Profile your code and find out where it is slow.
>2. Try some thing to speed it up and benchmark them.
>
>Since you have a negative result, you know that your attempt was not a solution.
>
>I suggest that if you profile down to the line level, then you may find more
>information about where your time is going. You may be able to precompute
>things and speed up in that way.
>
>If you post your code, I guess that some of the regulars here can help you to
>accelerate it.
>
>It used to be a good idea to put the most frequent things towards the top of the
>switch, but today's compilers with PGO render such tweaks as a complete waste of
>time. They will reorganize things much better than our guesses.
BTW, 19 seconds for perft 6 is not bad. It's not a world record, but plenty
fast enough for a very good chess program.
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.