Attack table

[Zach Wegner]

Hello Reinhard,

The n in my case refers to squares (although it is constant in my program) in that mobility calculation takes a set amount of time no matter what, unless the number of squares is different. To show this here is some code:

Code: Select all

scoretemp = 0;
for (x = 0; x < 64; x++)
        scoretemp += mobtable[x][side][board->attacks[side][x]];

Yes, it is a large table, but at least it's smaller than my SEE table (and the same size as two of my four rotated bitboard lookup tables).

For my move sort, I use selection sort (I think most people use it), because usually only one or two moves are needed to be picked off the list before a cutoff happens (or it is a PV or ALL node, so it doesn't matter, ordering could be skipped but it is hard to determine this).

Regards,
Zach

[Reinhard Scharnagl]

Hi Zach,

indeed O(n)! Where n = 64*16 (fields, directions or pieces).

But you also stated:

... or it is a PV or ALL node, so it doesn't matter, ordering could be skipped ...

even when a lot of people would act like that, how do you come to the conclusion that ordering does not matter in fully expanded nodes? (Or did I understood it wrong?)

Regards, Reinhard.

[Zach Wegner]

Hello Reinhard,

Well, in PV nodes the best move should be searched first to raise alpha, but in an ALL node, it absolutely does not matter. Every move is searched, it's just wasting time to put them in a specific order.

Regards,
Zach

[Uri Blass]

Hi zach,

It is also a waste of time to search moves when you are sure that it is an all node.

You can simply return alpha.

The point is that if you know that it is an all node you can quit the search and if you do not know it then the order of moves can be important.

Note that for the last moves I use the order of generated moves but the reason is not that I believe that order of moves is not important but because I believe that my order of moves is not efficient.

I believe that good order of moves should give an estimaste to the probability to generate cutoff for every move but unfortunately my program is not evaluating probabilities today and I do not know about a single program that does it.

Uri

[Reinhard Scharnagl]

Hi Zach,

as far as I understood, the decision to sort moves within a to be expanded node is to be done BEFORE knowing, that it might be fully analysed. To have its move sorted thus is not wasted time, because in case it would NOT be fully expanded, you will profit a lot.

If you would be able to decide this question before expanding a node, you probably seem to be able to also identify the best move. So why searching at all?

Reinhard.

[Sven Schüle]

Well, in PV nodes the best move should be searched first to raise alpha, but in an ALL node, it absolutely does not matter. Every move is searched, it's just wasting time to put them in a specific order.

It is also a waste of time to search moves when you are sure that it is an all node.

You can simply return alpha.

The point is that if you know that it is an all node you can quit the search and if you do not know it then the order of moves can be important.

Hi Reinhard, Uri, Zach (ordered alphabetically ) and all others,

can someone please explain why move ordering could be skipped at an ALL node?

Up to now I thought that move ordering were good at all types of nodes in any kind of alpha-beta search algorithm. Even at an ALL node (which is, to check that we're using the same terminology, a node where all existing subtrees have to be expanded), move ordering will have an influence on the size of the subtrees no. 2 .. N if there are N subtrees.

Is my knowledge outdated, or completely wrong, or are we talking about different things?

Regards,
Sven

[Reinhard Scharnagl]

Hi Sven,

I prosume Uri simply has forgotten the word "not" in "... not to search ..." ;-) .

Regards, Reinhard.

[Sven Schüle]

Hi Reinhard,

I'm sorry but this does not yet answer my question.
By the way, I think you are wrong because Uri also wrote "... simply return alpha ... you can quit the search ..." so I don't believe it was a typo.

Hi Uri,
did you really mean to skip the whole search at ALL nodes? What is your reason then?

Sven

[Uri Blass]

Hi Sven,
I thught about all node as node that all moves fail low.

Maybe I am wrong and this is not the definition of all node but I was based on Zach's words that suggested that definition and Zach wrote:

"Well, in PV nodes the best move should be searched first to raise alpha, but in an ALL node, it absolutely does not matter. "

Uri

[Uri Blass]

Hi again Sven,To answer your question I meant to skip the search in a node that all moves fail low because if you know it before searching you can skip search.

It is even a good idea to skip the search if you are almost sure that iall moves are going to fail low and the remaining depth is small enough and I do it in movei.

Uri

[Reinhard Scharnagl]

Hi Uri,

would you agree that when the decision is made to investigate a node by expanding and maybe search that then move ordering always will make sense?

Reinhard.

[Uri Blass]

Hi Reinhard, the answer is positive if we assume that ordering moves does not cost time but if it cost time then the question is what is the price.

There are some points:

1)It may be logical not to order only part of the moves when the remaining depth is small.

2)It may be logical not to order all the moves if you do not trust your program to have good order for the rest of the moves.

3)Another reason not to order all the moves is in case that you believe that ordering them may do the order worse later in the tree.

When I think about the way that I order moves I think that it certainly can happen.

Note to order all the moves and not to order only part of the moves mean the same here and I mean deciding to order only the first moves and after enough moves to stop ordering and use the order that they were generated.

Uri

[Dan Honeycutt]

Hi Sven:

I'm sorry but this does not yet answer my question.

I don't know if following posts answered your question or not. Didn't appear so to me so I'll add my 2 cents.

All nodes arise in cases where, for example, you just had your queen captured by the ply below. The reason it got captured is you made an idiotic move two plys below and left it hanging. When you search this node nothing is going to return a score better than alpha because of that idiotic queen move. Move order doesn't matter - you are going to search every move and none of them is going to repair the damage.

Like Uri says, if you knew it was an all node you could skip the search and return alpha. But you don't. The move that cost you your queen was most probably a blunder. But, just maybe it was the start of a dazzling combination. You don't know until you search.

Dan H.

[Sven Schüle]

Hi Dan,

many thanks for your explanation! This definition of ALL nodes had been unknown for me yet.

My conclusion is that move ordering is always relevant for nodes which are expanded, because you do not know in advance whether a node is an ALL node. Of course there may be heuristic techniques to guess, with acceptably high probability, that a node is an ALL node. But even in those cases I would apply move ordering because I think that it is much cheaper to do so for one node than to get many large additional subtrees (large due to missing move ordering) because there is a low but non-zero probability that the guess fails.

In my engine Surprise, move ordering currently is applied as follows:
- Each generated move is assigned a pre-value immediately at generation time.
- Ordering is done implicitly (selection sort), the searcher requests move by move from the move list, and the move with the highest pre-value which has not been expanded yet is returned.

Cheers,
Sven

[Reinhard Scharnagl]

Hi Sven,

the legal move generator within my growing Smirf engine could be used with an option, which controls the level of work to be done:

a) refuting a check thread only
b) generating all moves (with full information: capture, check, e.p. ...)
c) generating all moves like in b) preevaluated and sorted
d) like c) but investigating, whether check threats are mates or not

The sort I use is a variant of shell sort. Thus it seems to me to be more efficient in average as the selection sort, which may of course avoid unnecessary efforts in only partially expanded nodes but would be very expensive especially in big and fully expanded nodes. I am still convinced that an O(n*log(n)) type sorting procedure would be less time consuming in average. But this could be verified only in real tests.

Regards, Reinhard.

[Sune Fischer]

Hi Reinhard

I am still convinced that an O(n*log(n)) type sorting procedure would be less time consuming in average. But this could be verified only in real tests.

I am less convinced of that. These sorting devices eat lots of time.

Consider it from a purely statistical POV, if 50% of the nodes are fail-high nodes and on those you manage a 90% cutoff in the first move, then a full sorting of the move list appears to be wasted around 45% of the time.

Even if it is O(n logn) it's still inefficient.

Near the leaves, where things are speed critical and move ordering less important, I just sort and search the first few moves (5 I believe), then the rest as they go without sorting.

Compared to sorting all moves the program is 10-15% faster and the tree only increases by around 1-2%.

-S.

[Dan Honeycutt]

Hi Sven & Reinhard:

All these fancy sort routines I'm with Sune, an O(n) bubble sort.

Dan H.

[Zach Wegner]

I disagree. A bubble sort is O(n^2), and if you are only doing an iteration of it for every move, it is doing the same thing as the selection sort, but less efficiently. A selection sort just finds the best move out of those remaining, not exactly a "fancy sort routine."

Regards,
Zach

[Sune Fischer]

Hi Zach

Well, I think Dan meant selection sort, he agreed with me and I meant selection sort

The idea is simply that we believe to have such a good move ordering, that if there is a move to cutoff we will be able to search it first, we don't worry about any other moves at this time.

After a few moves the probability that it is an all node, is so high that sorting is just not worth the time anymore.

Which is more efficient to your program isn't hard to figure out at all.
It's just comparing changes in the size of the tree to the change in speed.

-S.

[Uri Blass]

Hi Sune,
I am not so sure about it.

The problem may be that after some moves the quality of order of moves that you can get becomes worse .

The question is what is the probability that you choose the best move in the next move to search when you do full sorting.

In the first moves the probability is high because there is a good chance that some hash move or some good capture is the best move but after some moves the probability is small because you have no idea which quiet move is best.

Uri