How can a program beat itself? Where is the randomness?

[JayRod]

I set two identical engines to play each other, one set to 50% strength in Arena ("The engine gets a lower amount of time. The engine thinks it is playing under a lower time control with less time to make a move. With a strength of 50% Arena pretends to the engine, it is running with half the time of the level that is currently set.")

At 40/4, or six seconds a move average, the weaker engine lost at roughly 150 points Elo difference. Why?

If each engine goes though the same algorithm, with no variation, shouldn't the results always be a victory for the stronger engine? Obviously then, some variation is needed, generated by a random number generator, but where does that variation go? In the move list ordering the best candidate moves for the chess engine? That is, the candidate moves that will be examined (since with such limited time I'm sure some candidate moves are prioritized over others)?

JayRod

[op12no2]

In Arena you can use an opening book and get both engines to play N moves from the book at random; then play from there on their own. I used N=6. Seems to work OK.

Edit: ha, ignore me - not what you we talking about I just realised.

[tpetzke]

If the engines differ in the time control they are likely to produce different moves. Often the move produced by the engine with more time is better but not necessarily always.

If I run the STS suite I sometimes see my engine getting the right move early (by luck) and then switching away from the best move. In such cases less time would have produced a better move.

So there is no guarantee that the engine with more time always wins.

Thomas...

[Stan Arts]

No because computerchess is not so exact. The one side has white, the other has black, and they are still playing chess.
One side is likely to be better, a program's style is likely to suit a certain position from a certain side etc. And wins/losses come even when the programs are completely equal, losses come even though a program is guaranteed to be better etc.

[syzygy]

I set two identical engines to play each other, one set to 50% strength in Arena ("The engine gets a lower amount of time. The engine thinks it is playing under a lower time control with less time to make a move. With a strength of 50% Arena pretends to the engine, it is running with half the time of the level that is currently set.")

At 40/4, or six seconds a move average, the weaker engine lost at roughly 150 points Elo difference. Why?

Your first paragraph answers the second.

[bob]

I set two identical engines to play each other, one set to 50% strength in Arena ("The engine gets a lower amount of time. The engine thinks it is playing under a lower time control with less time to make a move. With a strength of 50% Arena pretends to the engine, it is running with half the time of the level that is currently set.")

At 40/4, or six seconds a move average, the weaker engine lost at roughly 150 points Elo difference. Why?

If each engine goes though the same algorithm, with no variation, shouldn't the results always be a victory for the stronger engine? Obviously then, some variation is needed, generated by a random number generator, but where does that variation go? In the move list ordering the best candidate moves for the chess engine? That is, the candidate moves that will be examined (since with such limited time I'm sure some candidate moves are prioritized over others)?

JayRod

deeper search reveals more information. Even playing at equal time there is randomness because time sampling is done at discrete intervals while time itself is a continuous thing.

Don't forget search is not perfect information until it sees a forced mate or draw. So a deeper search sometimes leads you down a false path that falls out from under you later in the game...

[CRoberson]

The Horizon Effect is the primary answer to your question. Even with a deeper search the Horizon Effect can and does cause loses.

[JayRod]

@Dr. Hyatt, CRoberson

Thank you. If you can summarize where the Horizon Effect occurs, at a blitz level program, in a few sentences without this thread becoming a long tutorial on how chess programs work, that would be appreciated.

I was under the impression that two programs that have identical source code would search the chess tree in the same order (http://en.wikipedia.org/wiki/Tree_traversal), to quiescence, with the usual tree pruning tricks. So as you seem to say, if both have the same time, then the only logical way the weaker engine (which by definition searches less of the chess tree) can win is if it 'blunders' into the winning line since the stronger engine, having more time, erroneously sees a line that might work better, but in fact it has a hidden defect (past the Horizon) that makes playing this line a fatal mistake. But--and I guess this is what is surprising--if in fact this is the only way the weaker engine can win, then chess has more traps than I imagined. My hardware was a quad-core i5 PC, 32 bit OS, which you would think would allow the engines to search 10 ply or more (in fact the engine announces mate in six).

I was originally thinking perhaps the programs routinely employ a random number generator to pick which lines of the chess tree they will examine first, which implies both engines are NOT searching the same part of the chess tree at any given time period, if the time period is short, and that's why the weaker engine wins sometimes (that is, the weaker engine happens to be at a part of the chess tree where the 'objectively correct' line resides, while the stronger engine is hopeless lost in some thicket of the chess tree that has worse lines. Is this scenario also possible? Or is it always that the weaker engine just picks a 'natural move' that the stronger engine erroneously rejects, in favor of a 'deeper' line that is in fact a fatal line?

JayRod

[bob]

@Dr. Hyatt, CRoberson

Thank you. If you can summarize where the Horizon Effect occurs, at a blitz level program, in a few sentences without this thread becoming a long tutorial on how chess programs work, that would be appreciated.

I was under the impression that two programs that have identical source code would search the chess tree in the same order (http://en.wikipedia.org/wiki/Tree_traversal), to quiescence, with the usual tree pruning tricks. So as you seem to say, if both have the same time, then the only logical way the weaker engine (which by definition searches less of the chess tree) can win is if it 'blunders' into the winning line since the stronger engine, having more time, erroneously sees a line that might work better, but in fact it has a hidden defect (past the Horizon) that makes playing this line a fatal mistake. But--and I guess this is what is surprising--if in fact this is the only way the weaker engine can win, then chess has more traps than I imagined. My hardware was a quad-core i5 PC, 32 bit OS, which you would think would allow the engines to search 10 ply or more (in fact the engine announces mate in six).

I was originally thinking perhaps the programs routinely employ a random number generator to pick which lines of the chess tree they will examine first, which implies both engines are NOT searching the same part of the chess tree at any given time period, if the time period is short, and that's why the weaker engine wins sometimes (that is, the weaker engine happens to be at a part of the chess tree where the 'objectively correct' line resides, while the stronger engine is hopeless lost in some thicket of the chess tree that has worse lines. Is this scenario also possible? Or is it always that the weaker engine just picks a 'natural move' that the stronger engine erroneously rejects, in favor of a 'deeper' line that is in fact a fatal line?

JayRod

The horizon effect is simply the result of exhausting the allowable search depth. If something doesn't happen within the search horizon, it doesn't happen at all as far as a program is concerned. So the trick is to delay something until you can no longer see it, and then pretend it doesn't exist. It is still there of course, just invisible. The most common issue is a check, since that demands an immediate response and can push some tactical issue beyond the search horizon. The usual counter-measure is to extend the search depth on a check so that you don't push the ultimate issue beyond the visible horizon. And today we have another issue, namely search reductions. Each time you apply a search reduction, you bring the horizon closer and threaten to make something important turn invisible.

It was much more noticeable back in the 80's when the search depth was only hitting 8-10 plies. Today we are 3x in terms of search depth, which reduces the horizon effect significantly (but does NOT eliminate it of course.) The more moves you have between the root and the search horizon, the greater the chance that you can maintain an "out" and avoid getting burned too badly. But it is still there. And it still influences games today, and will continue to do so.

[kbhearn]

There is generally no explicit randomness in the search. There's semi-random effects caused by timing, particularly in the case of an SMP search where some nodes might get searched under one timing and not under another due to threads getting preempted by the system at different points resulting in different nodes visited, different splits, even more different search order, different hash entries available at a given node, etc.

The most common case for the weaker engine winning though is where a line is bad for the stronger engine but neither the strong nor weaker engine see it and the weaker engine just falls into 'oh, i'm winning!', the stronger engine likely even seeing it first but not being able to do anything about it by then.

The less common case of seeing more is bad should be very uncommon these days but would involve a long line where a large unavoidable advantage occurs at the cost of a disadvantage that takes an even longer line to see how to defend it and have the disadvantage you gave up become the relevant issue. At current search depths the chance that the root evaluation relies on such leaves is... rare.