aspiration windows & infinite loop

[flok]

Hi,

Today I looked at my program playing against fairymax under xboard. Usually I let it battle via HGM's server. I then noticed that sometimes it does very very bad moves. Like giving away the queen, something that can be noticed in 1 ply.
So I looked through the trace-log of my program I noticed something odd.
Sometimes, this happens not very often, it goes into an infinite loop in the aspiration windowsize code until it timeouts.

I use -32767 / +32767 for infinite.
I use -10000 / +10000 for check mate.

The evaluation is the simples possible where pawn is e.g. 100.
For the window size I use 100. I could maybe reduce that to half a pawn but first I want to make sure the code itself is fine.

Code: Select all

current id depth: 1
F5-G4 [regular]     (1537    with [-32767,32767]) 
current id depth: 2
A3-A1 [regular]     (1597    with [1437,1637])
current id depth: 3
F5-G4 [regular]     (1597    with [1497,1697])
current id depth: 4
A3-A1 [regular]     (1697    with [1497,1697])
current id depth: 4
C3-C2 [regular]     (2056    with [1497,32767])
current id depth: 5
F5-D3 [regular]     (2156    with [1956,2156])
current id depth: 5
F5-D3 [regular]     (9995    with [1956,32767])
checkmate detected at 5
current id depth: 6
F5-D3 [regular]     (32767   with [9895,10095])
checkmate detected at 6
current id depth: 6
F5-D3 [regular]     (32767   with [9895,32767])
checkmate detected at 6
current id depth: 6
F5-D3 [regular]     (32767   with [9895,32767])

So upto and including depth 5, the search looks ok. Then it detects a check mate. This results in search() return infinite (32767).
First question (this is a sanity check): a search can (in bug free code) return infinite, right?
So I enlarge the window a bit: 9895...10095. This is beyond the maximum check mate score (of 10k). Second question: is this valid? Those values (e.g. > 10k) can never happen so setting it larger is silly?
After the larger window, it still returns infinite (32767). The window cannot be set larger so when it retries, it keeps returning that 32767 value and so it loops forever.


regards

[elcabesa]

I Don't understand. Up To depth 5 it looks like you opened your window in a single step to 32767, but at depth 6 you open the windows very slow. Is this right?

[flok]

@marco:

current id depth: 1
F5-G4 [regular] (1537 with [-32767,32767])

The score here was 1537, so for depth the window goes to 1437..1637

current id depth: 2
A3-A1 [regular] (1597 with [1437,1637])
current id depth: 3
F5-G4 [regular] (1597 with [1497,1697])
current id depth: 4
A3-A1 [regular] (1697 with [1497,1697])

this fals outside the window so the upper bound is set to infinite

current id depth: 4
C3-C2 [regular] (2056 with [1497,32767])

2056 is in the window, so depth 5 is to 1956...2156

current id depth: 5
F5-D3 [regular] (2156 with [1956,2156])
current id depth: 5
F5-D3 [regular] (9995 with [1956,32767])
checkmate detected at 5

9995 (check at depth 5) so the window is set to 9895...10095

question: for correctness(!) sake I should limit that to 10000, right?

current id depth: 6
F5-D3 [regular] (32767 with [9895,10095])

no score at all in that window or something else(?) so 32767 is returned

question: should we always get a value in range? (-10k...10k) or is an infinite value possible as well?

checkmate detected at 6
current id depth: 6
F5-D3 [regular] (32767 with [9895,32767])
checkmate detected at 6
current id depth: 6
F5-D3 [regular] (32767 with [9895,32767])

and here it loops

[cdani]

In Andscacs I use 10000-depth to mark the mate value.

I keep widening the aspiration window until it is able to contain this 10000 score.

[bob]

Hi,

Today I looked at my program playing against fairymax under xboard. Usually I let it battle via HGM's server. I then noticed that sometimes it does very very bad moves. Like giving away the queen, something that can be noticed in 1 ply.
So I looked through the trace-log of my program I noticed something odd.
Sometimes, this happens not very often, it goes into an infinite loop in the aspiration windowsize code until it timeouts.

I use -32767 / +32767 for infinite.
I use -10000 / +10000 for check mate.

The evaluation is the simples possible where pawn is e.g. 100.
For the window size I use 100. I could maybe reduce that to half a pawn but first I want to make sure the code itself is fine.

Code: Select all

current id depth: 1
F5-G4 [regular]     (1537    with [-32767,32767]) 
current id depth: 2
A3-A1 [regular]     (1597    with [1437,1637])
current id depth: 3
F5-G4 [regular]     (1597    with [1497,1697])
current id depth: 4
A3-A1 [regular]     (1697    with [1497,1697])
current id depth: 4
C3-C2 [regular]     (2056    with [1497,32767])
current id depth: 5
F5-D3 [regular]     (2156    with [1956,2156])
current id depth: 5
F5-D3 [regular]     (9995    with [1956,32767])
checkmate detected at 5
current id depth: 6
F5-D3 [regular]     (32767   with [9895,10095])
checkmate detected at 6
current id depth: 6
F5-D3 [regular]     (32767   with [9895,32767])
checkmate detected at 6
current id depth: 6
F5-D3 [regular]     (32767   with [9895,32767])

So upto and including depth 5, the search looks ok. Then it detects a check mate. This results in search() return infinite (32767).
First question (this is a sanity check): a search can (in bug free code) return infinite, right?

Not in a reasonable implementation. What does "infinite mean" and how would you separate one "infinite score" from another? In Crafty, "infinite" means "error" since no score should possibly be above mate.

So I enlarge the window a bit: 9895...10095. This is beyond the maximum check mate score (of 10k). Second question: is this valid? Those values (e.g. > 10k) can never happen so setting it larger is silly?
After the larger window, it still returns infinite (32767). The window cannot be set larger so when it retries, it keeps returning that 32767 value and so it loops forever.


regards

You certainly have a bug there. Have you looked at your evaluation code to make sure you don't have an array bounds problem that would let it produce a score > 10000 (which should never happen)...

[flok]

Code: Select all

checkmate detected at 6
current id depth: 6
F5-D3 [regular]     (32767   with [9895,32767])

So upto and including depth 5, the search looks ok. Then it detects a check mate. This results in search() return infinite (32767).
First question (this is a sanity check): a search can (in bug free code) return infinite, right?

Not in a reasonable implementation. What does "infinite mean" and how would you separate one "infinite score" from another? In Crafty, "infinite" means "error" since no score should possibly be above mate.

Infinite happens when for example no move was selected in a call to search(). This can happen when alpha/beta have a range in which no scores lay.

And that's what I think is happening. Over diner I gave it some thought and looking back in svn it looks like I accidently removed a break-statement that would trigger when mate was detected at some depth.
What I think is happening is, that at depth 5 we see a mate. Then, instead of aborting the search, we go to depth 6. Depth 6 is not possible; it would be a move after the checkmate.

For depth 5 with search depth 5, I would go to the quiesce search. There, the first thing what it does is check for mate etc. That code is not in the regular search I found out. So it would try to iterate of a movelist of size 0.
I have that variable "int bestVal = -infinite;" which gets updated for every evaluated move. As there are no moves evaluated, it'll return -infinite which ends up as 32767 at the bottom.

So I removed that break with a reason but apparently I forgot(?) to add that moves-check.

So the ticket can be close

[bob]

Code: Select all

checkmate detected at 6
current id depth: 6
F5-D3 [regular]     (32767   with [9895,32767])

So upto and including depth 5, the search looks ok. Then it detects a check mate. This results in search() return infinite (32767).
First question (this is a sanity check): a search can (in bug free code) return infinite, right?

Not in a reasonable implementation. What does "infinite mean" and how would you separate one "infinite score" from another? In Crafty, "infinite" means "error" since no score should possibly be above mate.

Infinite happens when for example no move was selected in a call to search(). This can happen when alpha/beta have a range in which no scores lay.

And that's what I think is happening. Over diner I gave it some thought and looking back in svn it looks like I accidently removed a break-statement that would trigger when mate was detected at some depth.
What I think is happening is, that at depth 5 we see a mate. Then, instead of aborting the search, we go to depth 6. Depth 6 is not possible; it would be a move after the checkmate.

For depth 5 with search depth 5, I would go to the quiesce search. There, the first thing what it does is check for mate etc. That code is not in the regular search I found out. So it would try to iterate of a movelist of size 0.
I have that variable "int bestVal = -infinite;" which gets updated for every evaluated move. As there are no moves evaluated, it'll return -infinite which ends up as 32767 at the bottom.

So I removed that break with a reason but apparently I forgot(?) to add that moves-check.

So the ticket can be close

As I said, that is a bug. If you can have a score > +infinity or less than -infinity, you have a bug. You should probably interpret "-infinity" as "checkmated" which is what I do. No smaller score than "mated right now". No larger score than "this move mates opponent instantly."

[flok]

As I said, that is a bug.

Yes, that is what I confirmed in my reply.