Simple extensions?

[tpetzke]

Hi Mike,

I usually get only 600k - 700k nodes per second in midgame on my Core Duo 2.4 Ghz 1 CPU 32 bit. Compared to other engines this is rather slow but nps is not so important anyway.

I still think you are visiting to many nodes, what is the mode ordering scheme that you use. If you don't have one yet you will get a huge boost in performance if you implement one. Just ordering the captures upfront with a simple MVV/LVA scheme will be a significant gain.

In my case adding a SEE move ordering to the search reduced the tree size by about factor 100 (no other optimizations were implemented yet so this was the first one)

Thomas...

[mike_bike_kite]

I do an ID starting at depth 2 and working my way up until the time runs out. On each iteration I play the moves in the order of what scored highest from the previous iteration. I also only look at the first n moves (around 120 moves on the first iteration) and then reduce n by 1/2 on each iteration. The program adjusts n to try and have 4-10 moves to look at on the deepest search. Whether this actually improves things is anybodies guess though. I improved the logging a little bit so now on the 1st move with no random influenece and no opening book it shows (1mm would mean level 1 seach MinMax, 2ab would be level 2 seach with AlphaBata, 3ex would be level 3 search with alphabeta and Extensions):

Code: Select all

Level Nodes   Sec  Nps Score  d PV
 1mm     20   0.0   0k    71  1 Nf3
 1ab     20   0.0   0k    71  1 Nf3
 1ex     20   0.0   0k    71  1 Nf3
 2mm    420   0.0  28k     3  2 e4
 2ab    238   0.0   0k     3  2 e4
 2ex    238   0.0  14k     3  2 e4
 3mm   9322   0.3  29k    84  3 e4
 3ab   3691   0.1  29k    84  3 e4
 3ex   3691   0.1  33k    84  3 e4
 4mm   207k   7.2  28k    -6  4 Nf3
 4ab    41k   1.4  30k    -6  4 Nf3
 4ex    41k   1.4  30k    -6  4 Nf3

The above figures don't take into account any move ordering as this is implemented elsewhere. If I can integrate these parts then I'll show a 4th line at each level showing order alpha beta. I was surprised that alpha beta pruning could prune the tree by 80% at level 4- this just seemed a bit too good but it did come out with the same score and move so I guess it's working ok.

I have now implemented the extensions but I'm not sure it's playing better though. The extensions didn't really show above because the position is quiet at the start. The program did beat me this morning for the first time and I thought I'd cracked it but then it played terribly in the next game - oh well. I'm going to go through the logs in the bad game to work out what on earth it was thinking.

Code: Select all

if a take on an active square -> + 0.7 ply
if a check  -> + 0.8 ply
if any other take -> + 0.4 ply
if a pawn move to last 2 ranks -> + 0.7 ply

I'm also believe that high nps isn't the solution as a friends computer allows the program to run at 100k nps (mines on around 20k nps) and it doesn't seem to play any better against him (I think we're both around 1800). Obviously a jump to a million nps would give some improvement but increasing it by small factors isn't going to make a major difference.

I don't have a SEE function (or MVV or LVA) though I'm trying to get my head around these. I'm a little wary of adding new functions while things aren't playing right at the moment. One good thing though is the new opening books are playing well. I couldn't work out how to show the continuation of all the best moves so I just showed the move it would play.

Mike

[tpetzke]

Hi Mike,

if the only move ordering you do is in the root node from previous scores in IID then this is not enough.

First, you usually only get the move with the best score and prove that all others are worse, you don't have a order for the other moves from IID, so if the best move from the previous iteration proves bad at the higher depth, you have no order at all.

You visit at lot of nodes and move ordering is extremely important in the CUT and PV nodes. You want to get a cutoff with the 1st move you search.

Maybe you try the following

In your search if you have a move that fails high (score >= beta) than increase a global variable by the number of the move in the list and also count this cutoff. If the move was the first move, then increase a cutoff_with_1st_move counter.

If your search is done look what your % of cutoffs with the 1st move are and what the average position of the move was, that caused a cutoff.

A good score is a % of >90% of cutoffs with first move but you will probably need a hash table for move ordering assistance to get that high.

If you don't have MVV/LVA or SEE then just order captures at top of your list (captured queens first, then rooks ...). This should be fairly simple and give you a boost already.

Thomas...

[mike_bike_kite]

Thanks Thomas - I'll work on this next

Question - can you actually compare score for different lines of play if they have different depths? doesn't a line that includes an opponents capture on the last level (say Q*P) make all other scores without this capture look poor? and what happens if this P was backed up by another P just beyond the horizon so the following P*Q gets ignored? should I extend until the position goes quiet? what if it doesn't go quiet?

[hgm]

It is very important not to evaluate in a non-quiet position. Virtually every Chess program uses a Quiescence Search, and even a strict captures-only search is worth a few hundred Elo. with captures only it should always go quiet, eventually. It is very important to try the capture of the Most Valuable Victim first, though. Otherwise the search can explode.

[mike_bike_kite]

I'm a little confused then - I'd read that others were extending their search depending on what was going on ie extending by .7 ply if there's a take. This means the program will not extend after a certain depth even if the position is non quiet. I tried extending by 1 ply on every take but the program seemed to carry on searching forever - I assume my MVV stuff is wrong them.

I did try playing with the part that orders the moves. I used the value of the defending piece - the attacker piece. I also altered this score if either square was attacked by an enemy pawn and I also favoured moves to the centre.

The results were interesting (to me). This was from a position where there were plenty of exchanges possible:

Code: Select all

Level Nodes   Sec  Nps Score  d PV
1 min    41   0.0   0k   598  1 B*f6
1  ab    41   0.0   0k   598  1 B*f6
1 ext    41   0.0   2k   598  1 B*f6
1 s1     41   0.0   0k   598  1 B*f6
1 s2     41   0.0   0k   598  1 B*f6

2 min  1424   0.1  10k    87  2 B*f6
2  ab   282   0.0  17k    87  2 B*f6
2 ext  2837   0.1  22k   205  5 B*f6
2 s1    977   0.1  15k   205  6 B*f6
2 s2   1019   0.0  32k   205  6 B*f6

3 min   57k   2.6  22k   610  3 Bb5
3  ab  2578   0.1  23k   610  3 Bb5
3 ext   57k   2.5  22k   610  7 Bb5
3 s1    34k   1.5  23k   610  7 Bb5
3 s2    29k   1.3  22k   610  9 Bb5

4 min 1908k  82.4  23k   100  4 Bb5
4  ab   65k   3.6  18k   100  4 Bb5
4 ext 2682k 127.7  21k   214 10 B*f6
4 s1  1241k  51.5  24k   217 10 B*f6
4 s2   974k  43.2  22k   217 10 B*f6

The level shows to what depth the search is started off at and the codes mean the following:
min - min max
ab - alpha beta
ext - use extensions
se1 - use MVV based purely on value of pieces
se2 - use MVV plus whether squares attacked by pawns or central

The alphaBeta numbers show a massive improvement over MinMax - they look almost too good. The extensions massively increase the number of nodes needing to be searched but obviously they're looking further ahead. The standard MVV stuff half this number and adding the extra checks on pawn attacks and centre squares reduces it still further.

At the end of the day a 4 ply search using min max takes 80 seconds (on my computer with my rather slow program). Using the extensions and move ordering at every level allows me to search to a maximum of 10 ply (with extensions) and in half the time.

The problem is deciding whether it plays any better! My gut feeling is it does but I get a feeling I have to tune the depth of extensions so it does a broad search with extensions when required rather than looking at one move and searching endlessly through extensions. Perhaps I might put a cap on the extensions so it never looks deeper than 3 extra ply.

The new version with opening books and extensions etc is at the same place Fun chess. If you're a mac user with Java 1.5 then please use this. It's probably playing around 1650-1700 at the moment at the default level.

[hgm]

Extensions usually refer to the 'full-width' part of the search, i.e. before your 'remaining depth' counter hits zero. After that Quiescence Search starts, and almost everyone searches at least the 'good' and 'equal' captures (i.e. captures that after an exchange on the square they go to do not leave you with a loss). Many people do prune bad captures in QS.

In early versions of micro-Max I limited QS to recaptures to the same square only. This did work, and always dies out very quickly, but proved inferior to an all-capture QS once I implemented a primitive move sorting (MVV first; the rest in move-generator order).

Some people do extend captures in the full-width part of the search. Mentioned early version of micro-Max did extend all 'recaptures' (i.e. captures of the piece that moved on the previous ply) by a full ply.

Very important in QS is to determine first if the current evaluation already produces a (stand-pat) beta cutoff, and only start searching captures if it doesn't. Trying QxQ before PxR (when both are possible) usually gives smaller trees for the same search depth as doing it the other way around. This might at first glance seem strange, because there is no guarantee QxQ will win something, while PxR is a +4 even if he can recapture. But QxQ is a +9 if he cannot recapture, and even if he can, you can almost always play the PxR anyway. So the QxQ is the safest route to the +4. Because when you do PxR first, he will of course not recapture the Pawn even if he can, but play QxQ himself. So you will have to calculate all the way through the complications of the Q trade in any case, except that now it is you that gets a Queen behind and must hope you will be able to gain it back...

[tpetzke]

Hi Mike,

don't extend all captures, this is to much. Try limiting it to recaptures (captures at the same square the restore the material balance).

If I remember it right you have qSearch and normal search in one function and you count the depth upwards instead of downwards.

Make sure you don't extend captures when you are doing qSearch because here the stop condition is not depth but standing_pat or no more tactical move left.

Thomas...

[mike_bike_kite]

Thanks guys - that opened my eyes to a few things and my program now (finally) beats me. The problem was extending the search beyond stand pat situations - this meant it wasn't evaluating all the moves on a level playing field and it also meant it would quite often spend too much time looking down one narrow path rather than across a broad spectrum of moves.

It's taken 2 months and every second of my spare time but I've now managed to get it to a decent level. No idea what that level is though (probably 1800-1900) - how would I find out?

[hgm]

The only way to find out is to play a hundred games or so against opponents of known rating. But that is a bit difficult if you don't have a standard interface that allows you to play automatically.