Attack table

[Zach Wegner]

Hello Reinhard,

I estimate the futil fully to be expanded nodes to be about 50%, where sorting may be wasted time (to what I am not sure, because of earlier creating better informed nodes inside the transposition table).

This estimate is way off. In ZCT, I collect the number of PV, CUT, and ALL nodes in the main search. For a 9-ply and 10-ply search, respectively, from the starting position the numbers are:

Code: Select all

fail highs=30940    pv nodes=308      fail lows=12754
fail highs=77445    pv nodes=379      fail lows=32686

So fail high nodes are about 2x the other types (I included both odd and even plies because they typically would have different ratios). I believe that your philosophy is somewhat sound, but you should really test it out once you have a fully working engine.

[Reinhard Scharnagl]

Hi Zach,

... So fail high nodes are about 2x the other types ...

well, I want to remind here that there is another thread now on move generation. There some new examples have been placed by me.

After having thought somehow over the whole thing, I have modified my approach now somewhat. Now I do no longer sort completely, but instead build up a priority queue (O(n)) from which the top moves fastly could be fetched (in total (O(n*log(n))) in ordered sequence.

Reinhard.

[Volker Böhm]

Spike move generator has been programmed some time ago. But your discussion motivated me to take a look at it. At first some info about spike move generation:

Spike has different move generators for different situations:

1. A move generator for generating capture moves at q-search
2. A move generator for generating capture moves at standard search
3. A move generator for generating non capture moves at standard search

(and some subset like a move generator when in check or a move generator that generates only checking moves.)

Spike has a lazy move generation. It first tests the "hash move" without generating moves, then generates captures, then uses the killer moves without generating non capture moves. At last Spike generates the non captures. This results in the following (test from 100 positions WM-Test, fixted search depth 8):

from about 133 million nodes: there are
38 million calls to generate q-search captures
16 million calls to generate standard-captures
2,5 million calls to generate silent moves.

conclusion: About 40% of nodes have a capture move generator. The most optimization should be done in capture move generation.

Spike generates pseudo legal moves that may leave the king in check. But it generates seldom illegal moves as basic tests are made in move generator (example: the field a king moves to is not attacked by an opponent).

I had tested some special move geneators:
1. Generating only escapte moves when in check: works very well and saves time.
2. Incremental capture move generation. Works, is hard to implement and saves no time (twice as fast, but must be called twice as often because of lazy generation).
3. Capture move generator that checks fist wich piece could be captured an then tries to find out wich piece is capturing. (using attack tables). Didn?t won speed thus thrown out again.

Spike uses incrementally build attack tables. Why?

It was a decision made while programming the move generator. At this time we did not know how often the attack tables would been used in spike. At present we use the attack tables for the following:

1. Capture move ordering (a simple table-lookup based SEE)
2. Pre-decide for SEE-based pruning in Q-Search (a real SEE will only be made if the table-lookup based SEE shows a potentional pruning move).
3. King attack
4. Detection of hanging pieces in eval

Maybe later it could be of use for mobility.

My tests shows that a full attack table generation at every ply takes about 4 times more time than an incremental updated table.

Greetings Volker

[Reinhard Scharnagl]

Hello Volker,

to use a capture only move generator on the first view looks interesting. On the second view I see a little problem: there are situations, where every capture will lead to bad consequences, and where it would be better to make a silent move instead. I am not sure, whether those moves could be fully substituted by a single null move?

Reinhard.

[Volker Böhm]

Hi Reinhard,

in q-search I only try captures. In q-search I allow my program to stand pat, thus to use the current eval if no capture leads to a higher score.

in "normal" search I generate moves lazyly

1. hash move (if there is one, else i use IID to find one)
2. "good captures"
3. "bad captures"
4. "killer moves" (silent moves)
5. silent moves.

I hope this answers your question.


Greetings Volker