Attack table

[Reinhard Scharnagl]

Hi Sune,

different points of view are what creates dimension. So it is not at all bad having different philosophies.

After having nearly completed an 8x8 and 10x8 aware GUI I am just about to finish my Smirf engine. Thus wait and see. But I am sure because that being my first approach to complete a real engine the result would be something later to be improved in a lot of aspects.

Reinhard.

[Sune Fischer]

Hi Reinhard,

Indeed. Interesting to hear how other people do it, even if they do critize and ignore your good advices

I will have to challenge you to a match on FICS when Smirf is ready!

It will be tree size vs. speed then.

-S.

[Uri Blass]

Hi Uri,

I also do similiar things but I think that with good move ordering you can replace x,y,z by the fact that the moves are low in the list and also saving checking conditions x y z for the remaining moves.

Well I think it amounts to the same

You probably apply conditions x,y,z to your sorting process in some way to make the bottom moves "prunable", so it's a question of semantics really.

You can see my implementation as an O(n) sorting device which kicks in when conditions are ripe.

Actually I think my implementation is a bit faster because there is no suffling of moves on the list, futile moves are simply deleted.

-S.

Hi Sune,

I did not say that today I use order of unsorted moves to decide about pruning but only that I believe that if I sort them in a smart way then it may be possible to use the information in a productive way.

The point is that the fact that some moves did not fail high can reduce the chances that other moves will fail high if you sort every move so you can let yourself prune even when less conditions happen thanks to knowing the fact that no move failed high.

Uri

[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