Author: John Boyd
Date: 17:00:55 05/03/03
Go up one level in this thread
On May 03, 2003 at 05:42:04, Geoff wrote:
>Hi Ross
>
>Thanks for this excellent reply it was just what I was looking for !!
No problemo!
>
>>TSCP is a good place to start.
>Yep agreed, it was the only one I could vaguely understand at the start :-)
Ditto.
>
>>Maybe calculate mobility in your move generator? It won't be accurate though >you generate pseudo-legal moves only.
>Not quite sure how this could be done, as the move has to be made first before
>calculating mobility for both sides.
Well, for example, I think Movei counts legal moves for the side to move and
compares with the previous ply's mobility count (rather than calculate both
sides every ply). Uri says it works for him and I believe him.
>
>>I found killers to be effective but it depends a lot on your move ordering.
>>I don't allow captures in my killer slots. And my killers get ordered between
>>winning captures (eg PxQ PxR) and losing or equal captures (eg QxP QxQ).
>>
>>So, in the move ordering I try
>>
>>1. PV move
>>2. bestmove from hash table
>>3. Winning Captures (PxQ,PxN etc) in mvv/lva order
>>4. Killer 1,2,3 (remember these are never captures)
>>5. Losing/equal captures (QxP QxQ etc) in mvv/lva order
>>6. All other non-captures are ordered by history scores
>>
>>Its probably not optimal but its better than nothing.
>
>That is interesting, I think I need to concentrate on this area. I have tested
>my killer move mod, I took out the PV and the history sorting and retested the 2
>killer moves only ordering. For the start position it reduced the nodes searched
>to 93% of that with no move ordering. That was enough to make me think my code
>was working as I meant it, but a small enough improvement to make me think I
>have not understood something properly ?
You can create your own hardcoded mvv/lva table with hardcoded values like this
const int mvvlva[7][7] = {
{0, 0, 0, 0, 0, 0, 0},
{0,1000009,1000035,1000036,1000039,1000049,1000059}, // Px
{0,1000008,1000026,1000028,1000038,1000048,1000058}, // Nx
{0,1000007,1000025,1000027,1000037,1000047,1000057}, // Bx
{0,1000006,1000016,1000024,1000034,1000046,1000056}, // Rx
{0,1000005,1000015,1000023,1000033,1000045,1000055}, // Qx
{0,1000004,1000014,1000022,1000032,1000044,1000054} // Kx
};
Now index the table with the moving piece and captured piece eg
g->score = mvvlva[from_piece][to_piece];
Obviously the piece values are P..Q (1..6) Empty squares are 0 in my engine.
For killer moves I made a modification to create a 'scoring gap' between the
scores of the winning captures and the losing/even captures (not shown above).
For example, QxP gets only 400005 points. I assign the 3 killer moves a score of
500500, 500250 and 500000 respectively so they sort into the 'gap'. (Remember I
don't allow captures in my killer slots.)
This gave me a reduction in tree size but I don't recall how much. About 10% I
think.
Here's a rough benchmark... on a P3-450 my engine (TRACE) searches TSCP's bench
position to 6 ply in 4.8 seconds and visits 750,000 nodes. NPS are about
160,000.
Its not that good but it gives you an idea of what to expect with these mods.
Also, TRACE extends more than standard TSCP.
>>I'm a beginner too and I was amazed how easy it is to implement nullmove.
>>Just remember to clear the ep square and then restore it immediately after the
>>null search. With TSCP I had to modify the makemove and takeback functions.
>>Some debugging may be required but its really worth the trouble. Huge speedups.
>Null moving makes my brain hurt, think I will leave this one till I get a bit
>more experienced in chess programming !!
When you're ready... but believe me, its easy... look at Bruce Moreland's
programming topics site. He gives excellent example code. Also, Faile 1.4.4 uses
nullmove and is similar internally to TSCP.
>>1. In TSCP you can write a dedicated root_search() function to handle ply 1.
>>Then you can resort the root moves based on their actual scores after each
>>iteration. This worked well for me.
>Sorry, I don't think I follow what you meant by this mod.
Okay, in TSCP the think() routine has an iteration loop which progressively
calls search() with increasing depths. The idea is to shift the depth iteration
loop into a dedicated function called root_search().
The root_search() basically has this pseudocode code...
alpha=-CHECKMATE
beta=CHECKMATE
generate_move_list
for depth = 1 to maxdepth
sort_moves_by_score
for i = 1 to movecount
make_move i
score = -search(-beta,-alpha,depth-1)
take_back
assign_score
if score > alpha
update pv
output_pv
endif
endfor
endfor
Sorry about lack of indenting but you should get the picture. Notice the
movelist gets resorted after each iteration. On the first iteration it is sorted
as per the move generator scoring... on subsequent depths it is sorted by the
value returned form the search...
You can easily add aspiration windows and re-searches to this basic structure.
Hope that helps.
>>2. If you are using TSCP's attack() function, rewrite it. Instead of looking for
>>pieces which attack a certain square, work outward from the square and look for
>>a potential attacker. Its heaps faster.
>
>Oh yes thats a good idea, for some reason it hadn't occured to me yet. It
>probably would have done eventually. lol
>
>>
>>3. TSCP also benefits from keeping track of the two king's squares. The
>>in_check() function scans the whole board looking for the relevant king's square
>>before calling the attack()function. I created two global variables wksq and
>>bksq and update them in makemove() and takeback() whenever the kings move.
>
>Yes, I have already done this same mod, I just forgot to mention it, agreed it
>did give a marked improvement
>
>>4. TSCP can benefit from using piece lists so it doesn't have to loop 64 times
>>in gen(), gen_caps() and eval(). It means makemove() and takeback() become a
>>little messy but its a good speedup.
>
>Thats another one I hadn't thought of yet !
>
>>5. Converting TSCP to an 0x88 board representation is also worthwhile.
>
>I recall seeing a write up of this somewhere, the TSCP 'mailbox' move gen code
>looked quite efficient so I thought it wouldn't really benefit from an 0x88
>system.
Its not a big speedup, but 0x88 has other advantages... easy tests for offboard
moves but mainly the ability to detect ray attacks based on the difference
between the from and to squares. Bruce Moreland explains it better than I ever
could on his web-site.
>>That should keep you busy for a while... :-)
>Yes, that is very true !!!
>
>>Just adding hashtables and nullmove to TSCP (plus the above tweaks) will make
>>TSCP search its built-in benchmark to 6 ply at least 25x faster.
>
>Strewth, that is an amazing figure, what would you guess the individual speedups
>were for each of those mods ?
I haven't kept track of each individual speedup, so vaguely....
Fixing attack() function will give about a 2x speedup.
Piecetables give another 50% at least. Even better in endgames.
Hashtables is about 2x in middlegame, and much much more in the endgame.
Nullmove is 4 to 8 times faster. Its a turbo-charger.
Aspiration search can give you another 20%. But be aware that all search
algorithms based on re-searching rely heavily on hash tables for their
efficiency.
Another suggestion is run a profiler on your engine and look for the hotspots.
Have fun!
Ross
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.