Hidden move ordering savings based on piece list shuffles

[maksimKorzh]

Hi Guys

I've discovered a thing that has confused me at very least...
So I was debugging my search because it returned weird moves when time is up.
I didn't yet manage to fix that while my JS implementation seems to be the same as C one,
but that doesn't matter.

So I've started breaking down the process and suddenly realized that if I do following:

Code: Select all

nodes = 0;
alphabeta(-infinity, infinity, 4);

nodes = 0;
alphabeta(-infinity, infinity, 4);

nodes = 0;
alphabeta(-infinity, infinity, 4);

nodes = 0;
alphabeta(-infinity, infinity, 4);

Then the output would be:

Code: Select all

output:
nodes: 6515
nodes: 2806
nodes: 3846
nodes: 3546

I thought may be something wrong with my movegen, but either perft or disabling beta cutoffs gives the same number of nodes every time.
So I started to think: if the difference in nodes is caused by the beta cutoffs it means that the move ordering is changing.
So I disabled move ordering but the node count was still different every next run.
Finally I decided to check piece lists and yes - that was the matter of piece order in piece list.
My piece list incremental updates are implemented exactly the same way as in VICE, so in VICE (JS) same test gives similar results.

Did anyone reveal this behavior before?
Is it ok for piece lists to swap piece order while piece-square associations remain correct?
Can we exploit this behavior to improve move ordering?

P.S. What does it means if engine sacs queen or does similar weird move when the time is up?

[eligolf]

Hi,

I have thought the same thing many times before and got the conclusion that the peice list itself shouldn't matter. Personally I generate all moves as they appear on the board or in the piece list. Then the sort function will handle the rest to sort the moves from top candidates to lower candidates. The initial piece list itself has nothing to do with the order of which you try each move, not in my engine at least. All is handled within the sort function just before going into the recursive looping over possible moves.

Sorry if I misunderstood anything in your question.

[Harald]

Since this is alphabeta() and not perft() I think you use the normal search function.
Do you use the transposition table (hash table)?
And don't clear it between calls?
Do you count the nodes before or after the hash table access?
Do you skip branches because of hash table lookup results?
Even when you start with -infinity, infinity each time the stored values in the hash table are updated all the time.
With each call you will get another node count.
Though the node count should decrease in general there could be situations where an early cut
with some score will hide another better cut or allow another branch with more nodes to come into the search.
Just a guess.

[maksimKorzh]

Since this is alphabeta() and not perft() I think you use the normal search function.
Do you use the transposition table (hash table)?
And don't clear it between calls?
Do you count the nodes before or after the hash table access?
Do you skip branches because of hash table lookup results?
Even when you start with -infinity, infinity each time the stored values in the hash table are updated all the time.
With each call you will get another node count.
Though the node count should decrease in general there could be situations where an early cut
with some score will hide another better cut or allow another branch with more nodes to come into the search.
Just a guess.

Hi Harald, no in this version no hash table yet)
The different number of nodes is caused by the shuffled piece list.
It produces beta cutoffs in different places, but if I reinit all before new search
then the number of nodes is the same which is enough I think.
I'm now more like struggling with an issue of how to prevent PV table from writing line that scores 0 after return on time up.

[maksimKorzh]

Hi,

I have thought the same thing many times before and got the conclusion that the peice list itself shouldn't matter. Personally I generate all moves as they appear on the board or in the piece list. Then the sort function will handle the rest to sort the moves from top candidates to lower candidates. The initial piece list itself has nothing to do with the order of which you try each move, not in my engine at least. All is handled within the sort function just before going into the recursive looping over possible moves.

Sorry if I misunderstood anything in your question.

So do I.
Can you please do me a little favor?

Please tell me (if you have time for this test obviously) whether the number of nodes would different in your engine in case of this test:
1. start engine in UCI mode
2. position startpos
3. go depth 5 (repeat several times WITHOUT re initializing starting position, so piece lists won'r be initialized from scratch, but would remain in the state after previous search )
4. what are the numbers of nodes for each next search? Are they always remain the say or differ from previous?

[Ras]

P.S. What does it means if engine sacs queen or does similar weird move when the time is up?

Where do you generate and store the root move list? Inside or outside the alphabeta search? If inside, then any weird move would improve the initial alpha of -infinity. Then time is up, search aborts, and you'd get that nonsense move. The solution is to make sure that in iterative main deepening, you search the leftmost path of the previous iteration first. This would also yield better search performance because alpha is raised quickly.

[maksimKorzh]

P.S. What does it means if engine sacs queen or does similar weird move when the time is up?

Where do you generate and store the root move list? Inside or outside the alphabeta search? If inside, then any weird move would improve the initial alpha of -infinity. Then time is up, search aborts, and you'd get that nonsense move. The solution is to make sure that in iterative main deepening, you search the leftmost path of the previous iteration first. This would also yield better search performance because alpha is raised quickly.

Thanks, yeah, already figured that out on my own and fixed.