Starting with move ordering.

[Luis Babboni]

Hi people!

After tried useless to do a successfull QS without move ordering, I´m starting this first.

To be sure I´m understading things right:

When in many places there is a talk about "move generator" and for example how fast it is and if have no bugs testing it with perfts, what is test is a the "Move generator + move making" or just the "move making"?
I guess is the "Move generator + move making" but want to be sure.

I mean:
At ply 1, you could generate all moves without need to make any move. But for generate all ply 2 moves, you first need to make moves generated at ply 1. I´m right? For example you need to actualize en passant stuff, castle rights; etc. before know wich moves are legal at ply 2.
I read somewhere that just not count in perfts the 50 moves rules and 3rd repetition rule.

My actual "move generator" do not store moves, work this way:
-make move 1 of ply1
-make move 1 of ply 2 from board state after make move 1 of ply 1
...

If things are as I understood, then my actual "move generator" will be faster than a new "move generator" that include "main move generator plus moves maker" that work this way:
-generate all moves at ply 1.
-make move 1 ply 1
-generate all moves at ply 2 starting from board state after make move 1 of ply 1
-make move 1 at ply 2 of moves generated starting from board state after make move 1 of ply 1
...

It is suppoused that the time lost doing it this last way, will be less than the time gain thanks to better alpha beta cuts using move ordering that is only possible in the last way. In fact the QS be faster too. I´m right?

Thanks for your time in case you could take a look to this question!

[hgm]

Consider it this way: suppose that by ordering the moves you find cut-moves on the average after 2 attempts, while when you randomly order the moves, you would find them in 6 attempts. As all-nodes and cut-odes alternate per tree level, half the plies are cut-nodes. So if you search 12 plies deep, 6 of the levels consist of cut-nodes, and your branching factor is a factor 3 larger there without move ordering. That gives a factor 3^6 = 729 for the number of leave nodes in your tree.

So you have the choice between making things twice slower by running through the moves twice (once for generating, once for searching), and searching 729 times fewer nodes at half the speed, or doing the original number of nodes at the full speed. What do you think is faster?

[Sven]

Hi people!

After tried useless to do a successfull QS without move ordering, I´m starting this first.

To be sure I´m understading things right:

When in many places there is a talk about "move generator" and for example how fast it is and if have no bugs testing it with perfts, what is test is a the "Move generator + move making" or just the "move making"?
I guess is the "Move generator + move making" but want to be sure.

I mean:
At ply 1, you could generate all moves without need to make any move. But for generate all ply 2 moves, you first need to make moves generated at ply 1. I´m right? For example you need to actualize en passant stuff, castle rights; etc. before know wich moves are legal at ply 2.
I read somewhere that just not count in perfts the 50 moves rules and 3rd repetition rule.

My actual "move generator" do not store moves, work this way:
-make move 1 of ply1
-make move 1 of ply 2 from board state after make move 1 of ply 1
...

If things are as I understood, then my actual "move generator" will be faster than a new "move generator" that include "main move generator plus moves maker" that work this way:
-generate all moves at ply 1.
-make move 1 ply 1
-generate all moves at ply 2 starting from board state after make move 1 of ply 1
-make move 1 at ply 2 of moves generated starting from board state after make move 1 of ply 1
...

It is suppoused that the time lost doing it this last way, will be less than the time gain thanks to better alpha beta cuts using move ordering that is only possible in the last way. In fact the QS be faster too. I´m right?

Thanks for your time in case you could take a look to this question!

Regarding your question about alpha-beta search: yes, the time "lost" by storing the generated moves and ordering them will be less by several orders of magnitude than the gain you get from move ordering.

"Perft" is a common test to verify correctness of your basic program parts which mainly consist of:
- move generator,
- making and unmaking moves,
- is-in-check testing, and
- move legality checking.

So "perft" does not cover evaluation, alpha-beta-based tree search, move ordering, or any kinds of search features. It ignores the 50-moves rule and repetition draw, as you wrote, and additionally also draw by insufficient material.

With a recursive function "Perft" can be implemented quite easily, and it becomes even easier if you have a move generator that only stores legal moves in the move list. But it can also be done without the latter. The general structure, with a "legal move generator", is:

Code: Select all

UINT64 perft(int depth) {
    UINT64 nLeaves = 0;
    int nMoves = generateLegalMoves();
    if (depth == 1) return nMoves;
    for (all moves) {
        makeMove();
        nLeaves = nLeaves + perft(depth - 1);
        unmakeMove();
    }
    return nLeaves;
}

and without it:

Code: Select all

UINT64 perft(int depth) {
    if (depth == 0) return 1;
    UINT64 nLeaves = 0;
    generatePseudoLegalMoves();
    for (all moves) {
        makeMove();
        if (not(lastMoveWasIllegal())) {
            nLeaves = nLeaves + perft(depth - 1);
        }
        unmakeMove();
    }
    return nLeaves;
}

[Luis Babboni]

Consider it this way: suppose that by ordering the moves you find cut-moves on the average after 2 attempts, while when you randomly order the moves, you would find them in 6 attempts. As all-nodes and cut-odes alternate per tree level, half the plies are cut-nodes. So if you search 12 plies deep, 6 of the levels consist of cut-nodes, and your branching factor is a factor 3 larger there without move ordering. That gives a factor 3^6 = 729 for the number of leave nodes in your tree.

So you have the choice between making things twice slower by running through the moves twice (once for generating, once for searching), and searching 729 times fewer nodes at half the speed, or doing the original number of nodes at the full speed. What do you think is faster?

It seems I understood!
Thanks HG!

[Luis Babboni]

Thanks Sven!
It seems I understood.

Just now I´ll take a better idea about how fast my move generator is.
When I tested it, in my machine do about 1 million moves per second and when I compared with others seems not as bad as I spected.... but I compared two different things: my "just moves maker" with others "moves generator + moves maker".
I still not know how much slower my future moves generator will be, but even being far slower, I hope the engine will become not those 729 times faster HG says (I guess my moves ordering not will be too good at least at the begining) but faster!.....

And then my version with QS will be better than my version without QS as actually without move ordering.

[Sven]

Thanks Sven!
It seems I understood.

Just now I´ll take a better idea about how fast my move generator is.
When I tested it, in my machine do about 1 million moves per second and when I compared with others seems not as bad as I spected.... but I compared two different things: my "just moves maker" with others "moves generator + moves maker".
I still not sure how much my future new moves generator will be, but even being far slower, I hope the engine will become not those 729 times faster HG says (I guess my mos ordering not will be too good at least at the begining) but faster!.....

And then my version with QS will be better than my version without QS as actually without move ordering.

Don't think too much about "speed" (i.e. "moves per second") at the moment - think about
1. how things should work,
2. how to implement it correctly, and
3. how to use effective algorithms (not optimized - postpone that for later - but not wasting a very huge amount of time).

As to the "729", HGM did not mean that the engine would be 729 times "faster" (in terms of nodes per second), just that it might search 729 times less nodes in the same time, for the example he chose.

[Luis Babboni]

Thanks Sven!
It seems I understood.

Just now I´ll take a better idea about how fast my move generator is.
When I tested it, in my machine do about 1 million moves per second and when I compared with others seems not as bad as I spected.... but I compared two different things: my "just moves maker" with others "moves generator + moves maker".
I still not sure how much my future new moves generator will be, but even being far slower, I hope the engine will become not those 729 times faster HG says (I guess my mos ordering not will be too good at least at the begining) but faster!.....

And then my version with QS will be better than my version without QS as actually without move ordering.

Don't think too much about "speed" (i.e. "moves per second") at the moment - think about
1. how things should work,
2. how to implement it correctly, and
3. how to use effective algorithms (not optimized - postpone that for later - but not wasting a very huge amount of time).

This is the plan!
I want to fight against most common search algorithms to understand it better before start a new more polished code.

As to the "729", HGM did not mean that the engine would be 729 times "faster" (in terms of nodes per second), just that it might search 729 times less nodes in the same time, for the example he chose.

Yes, yes.

[Luis Babboni]

It seems I could implemented move ordering without bugs... at least for the moment I did not found any.

But the engine do not play better than without it.

The speed was reduced from around 600Kmoves/sec to less than 300Kmoves /sec. My code is not good at all, but on the other side, at each depth the number of moves needed to be analized was lowered to around 1/3.

That results in usual one ply more search for "with move orderer" version.... but when remains few pieces on board, that advantage near disappear and the "without move order" version reach usually 2 ply more depth!! *

*: I still did not any seriosu statistics, just see numbers in the air.

Is a knew effect?

Thanks!

[ZirconiumX]

Your move sorting shouldn't slow you down too much - how do you sort your moves?

I would suggest you add two counters to your program. One measures the total number of fail highs, and the other measures the number of fail highs on the first legal move searched. Dividing the second by the first gives you a measure of how efficiently you are searching.

[Ras]

Some notes on the move sorting:

1) many programs don't actually sort the moves in the sense that they would generate a sorted move list from the previously unsorted one. Instead, they do a selection sort. Means, they:
- go through the full unsorted move list
- pick up the move with the highest associated value
- swap that move to movelist position 0
- for the second move, they do the same, but start scanning the list at position 1 instead of position 0

That can be faster as long as one of the first few tried moves gives a cutoff so that the rest isn't tried out. However, the worst case running time is O(N^2).

2) for those that do actually sort the list, the worst ones really use "bubble sort". This is total nonsense, of course.

3) the next best ones use whatever sorting algorithm their programming language offers. This is especially slow in case of C with the qsort because every comparison results in a function call. That can be a huge waste of time.

4) for lists of not more than (typically) 80 elements, quicksort is slow due to the overhead. See here: http://embeddedgurus.com/stack-overflow ... d-systems/

For the CT800, I got a considerable speedup when I changed NG-Play from the C library qsort to a self-written shellsort. Still, the program spends around 12% of its time in the sorting routine. I can confirm Jones' observation that shellsort is faster than heapsort, which I had also tried and benchmarked.

5) conclusion: if your program actually sorts the list, use shellsort as sorting algorithm. It is fast, easy to implement, non-recursive. Use the Ciura sequence (1, 4, 10, 23, 57, 132, 301, 701, 1750) - 57 is the maximum useful value.