Thermopylay Marathon 2011 (live!)

Discussion of computer chess matches and engine tournaments.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
hgm
Posts: 23775
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Thermopylay Marathon 2011 (live!)

Post by hgm » Thu Feb 10, 2011 7:51 pm

hgm wrote:Spartacus had a spurious mate score at move 58 as well. I will also have to look into that.
Aiaiaiaiai...

Spartacus' check if a killer move is valid rejects diagonal moves with Pawns... and Hoplites! (Assuming thet are captures, and thus not valid killers, already searched with the captures.) After move generation non-captures are compared with the killer slots before they are searched, and skipped if they match. So killer moves with Hoplites are never searched at all!

This causes the spurious mate clame in the position

8/7R/8/5R2/2kh4/3h4/1K6/8 w - - 1 58
[d]8/7R/8/5R2/2kp4/3p4/1K6/8 w - - 1 58

After 58. Rhh5 Kb4 59. Rh4 Kc4 60. Rhf4 we get the position

[d]8/8/8/5R2/2kp1R2/3p4/1K6/8 w - - 1 58

and here both Hc2 and He2 killers, and Hd4 is pinned, so the only legal move left is 60... Kb4 followed by 61. Rxd4#

Incredible Spartacus still plays so well. Not searching killer moves should be a crippling bug!

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Thermopylay Marathon 2011 (live!)

Post by Evert » Thu Feb 10, 2011 8:03 pm

hgm wrote: Incredible Spartacus still plays so well. Not searching killer moves should be a crippling bug!
Sure, rub it in, why not? :P
I am curious about what makes Spartacus and Nebiyu so fast compared to the other entries (it's not simply that they strong, they reach larger search depths in less time). Is it selectiveness of the search? Staged move generation?

Daniel Shawul
Posts: 3762
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Thermopylay Marathon 2011 (live!)

Post by Daniel Shawul » Thu Feb 10, 2011 8:28 pm

There is just too many bugs inside the move generator. (1) I was not generating evasion moves in qsearch, (2) overflowing of mate_scores in hash table (16 bits only but I had 100000 as mate score for the last version), (3) overwriting of some moves etc etc... I think you should continue the games because I have too many things to work out. It could take me till tomorrow.
Last edited by Daniel Shawul on Thu Feb 10, 2011 8:33 pm, edited 1 time in total.

Daniel Shawul
Posts: 3762
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Thermopylay Marathon 2011 (live!)

Post by Daniel Shawul » Thu Feb 10, 2011 8:32 pm

Mine is excessive reductions. You should see my Go engine. I reduce too much there and it seems to work much better than not to. I don't think incremental move generation gains you anything significant. Infact I only try hash move before generating all :)

User avatar
hgm
Posts: 23775
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Thermopylay Marathon 2011 (live!)

Post by hgm » Thu Feb 10, 2011 8:45 pm

Spartacus indeed has staged move generation. It generates captures victim by victim, starting from the MVV from the opponent piece list, running through the stm piece list and doing 0x88 attack tests. A stage encompasses generation of captures of all victims of the same (approximate) value, and is followed by a bubble sort by attacker value. (As the stm piece list is traversed LVA first, this never requires many steps.) Then follow two killer stages, then non-capture generation, and finally bad captures, which are captures that were postponed based on guaranteed negative SEE (protected victim, and victim +protector < attacker). In QS everything from the killer stages is skipped, as it also is at d=1 when non-captures are futile (or even during the capture stages when it encounters a futile victim). Hash move and null move are also separate stages, done before any move generation. But after generation of King captures and check test. (Some improvement is possible here, by checking for King captures in the parent node.)

Spartacus is also fast because there is virtually no evaluation. It is just PST + material table + Pawn hash.

It does not have particularly severe reductions. I use R=2 for null move, and reduce remaining non-captures by 1 ply.
Last edited by hgm on Thu Feb 10, 2011 8:56 pm, edited 1 time in total.

User avatar
hgm
Posts: 23775
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Thermopylay Marathon 2011 (live!)

Post by hgm » Thu Feb 10, 2011 8:53 pm

Well, I will wait. I will start some 40/5 games with the new Catalyst in the mean time for fun.

Daniel Shawul
Posts: 3762
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Thermopylay Marathon 2011 (live!)

Post by Daniel Shawul » Fri Feb 11, 2011 4:33 am

Partially fixed https://sites.google.com/site/dshawul/N ... ects=0&d=1
Surprisingly it turned out not generating evasions in qsearch is much better.
But I have fixed the mating problem even though there is still some issues with giving the shortest mate.

Richard Allbert
Posts: 770
Joined: Wed Jul 19, 2006 7:58 am

Re: Thermopylay Marathon 2011 (live!)

Post by Richard Allbert » Fri Feb 11, 2011 6:15 am

Well Catalyst does seem to be scoring a bit better!

I still need to add some very basic eval terms, though.

At the moment it has just:

Psq tables
Rook, Queen, general on Open / Semi open files
Pawn doubled / isolated penalty, passer bonus
Hoplite isolated penalty, hoplite doubled / passer bonus
Material adjustment to encourage black to keep pieces

.. and that's it

:D

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Thermopylay Marathon 2011 (live!)

Post by Evert » Fri Feb 11, 2011 1:03 pm

hgm wrote:Spartacus indeed has staged move generation. It generates captures victim by victim, starting from the MVV from the opponent piece list, running through the stm piece list and doing 0x88 attack tests. A stage encompasses generation of captures of all victims of the same (approximate) value, and is followed by a bubble sort by attacker value. (As the stm piece list is traversed LVA first, this never requires many steps.) Then follow two killer stages, then non-capture generation, and finally bad captures, which are captures that were postponed based on guaranteed negative SEE (protected victim, and victim +protector < attacker). In QS everything from the killer stages is skipped, as it also is at d=1 when non-captures are futile (or even during the capture stages when it encounters a futile victim). Hash move and null move are also separate stages, done before any move generation. But after generation of King captures and check test. (Some improvement is possible here, by checking for King captures in the parent node.)
I've been thinking about doing some sort of staged move generation, since it seems to me you could safe quite a bit of time that way. At the moment, I generate all moves, score them and then sort them (with quicksort). This gives hash move, winning captures, killer moves, losing captures, quiet moves. I'm experimenting with flipping the order of quiet moves and losing captures, but so far that doesn't seem to help much overall.

It's a lot of extra work that's ultimtely unnecessary if the hash move ends up causing a cutoff. In Jazz, I actually keep track of the move with the highest score, and I try it before sorting the rest of the list. This already speeds things up nicely.
Spartacus is also fast because there is virtually no evaluation. It is just PST + material table + Pawn hash.
Sjaak has material, PSQ, mobility and king safety. Mobility is a fairly expensive thing to calculate, but it helps a lot for playing strength. The obviously missing element is some notion of pawn structure.
It does not have particularly severe reductions. I use R=2 for null move, and reduce remaining non-captures by 1 ply.
Sjaak is actually more agressive than that: I prune after a null move fails high (except if it fails high with a mate score) and I reduce moves lower down on the list by 1 or 2 ply, depending on the type of move. I've wondered whether this is too much, but if I reduce less it seems to perform worse in practice...

User avatar
hgm
Posts: 23775
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Thermopylay Marathon 2011 (live!)

Post by hgm » Fri Feb 11, 2011 1:59 pm

The problem with mailbox board always is to efficiently generate captures. The simplistic way of generating all moves (knowing the occupied from-squares from the piece list) is actually very competitive, and gives you the non-captures for free. In Joker I use a separate move generator for QS, saving tiny bit of time by not writing the non-captures to the move stack, but basically you still generate them.

The 'inverted' way I do use now is not really much more efficient. In stead of running through all pieces, and trying all moves of each to see if you hit something on the board, I now have to run through all victims, and then try all possible attackers to see if there is a 0x88 match. On a full board that means matching with 8 pieces, while pieces on average usually do not even have 8 moves in such positions. (Pawns are treated separately; in 'direct' generation I would have to test 2 squares in front of each Pawn for victims, while in 'inverted' generation I have to test 2 squares in front of each victim for attacking Pawns, and usually there are about as many Pawns as victims.)

The advantage, however, is that it speeds up as the board gets empty: the number of moves per piece would increase, but the number of potential attackers per piece will decrease. And a second advantage is that the inverted way is easy to stage, so that you can abort without having done everything when acheiving a cutoff or reaching the futile victims. So even on a 10x8 board it might be competative with direct generation. And it saves you a lot of sorting effort.

But the main problem remains that you are basically finding the moves through search: you try every move or attacker, testing if they produce a hit. While the fraction of hits is always quite small. So I mainly chose this approach because the attack tables will solve the latter problem. There I would only need a single access to the table for each victim, and if there are no attacks on it, that would be it.

Spartacus also prunes after null move fails high, but it searches the null move with a reduction of 2 ply. I don't dare to use higher reductions for the late moves, as I don't sort the non-captures. (Spartacus doesn't use history.)

Post Reply