Author: Christophe Theron
Date: 13:28:59 12/28/97
Go up one level in this thread
On December 28, 1997 at 07:24:36, Thorsten Czub wrote:
>>* When it is the opponent's turn, select every move
>>* Your turn: select the best move (from a SEE+positional 1 ply
>>evaluation) and the very threatening moves (including checks of course)
>>* Opponent's turn: select several best moves and any threatening move.
>
>I call this the asymmetrie-search !
I understand well what you mean. My "summary" in made of several of your
comments, some other information by other people, and my own
observations on Psion and Genius. I try to put here these informations
in a suitable way to deduce the algorithm.
The above description you are quoting is another way to say "asymetric
search", in a way I can use to write a program.
>If you analyze , after you have sent YOUR move, with genius on the
>opponents move something horrible can happen:
>You let it again compute 9 searches or 11 and it plays a boring move.
>
>And than you get a sac by another mail-chess guy who has NOT genius but
>e.g. Wchess and the enemy plays a sac and you input the move in genius
>and genius sees in an instant that it is lost !!
>This effect comes from what I call the asymmetrie-search.
I see a paradox here. An asymetrical search should not behave this way,
because as you said it has seen every move you can do to it. So it has
also seen any sac you may do.
What you describe cannot be a side effect of the asymetrical search.
Instead it seems to be a classical horizon effect.
Don't forget that when you enter the opponent's reply the search is
going 2 plies deeper than the previous search in the same computing
time, because 2 moves have been played.
So a combination that could take 3 minutes and 5 plies brute-force to
compute now only takes 3 plies, and only a few seconds. This is likely
to be the explanation of what you are describing.
Any program shows this kind of strange blindness. Maybe Lang programs
show it more often because they are more selective.
>The advantage of this search was on the other hand:
>I don't have to compute that many branches.
>I am always seing threads.
>Sometimes I don't play the killer-move but a 2nd or 3rd best move.
>
>THIS is the reason genius plays boring !
Yes, I think you are right.
>>About the "shifted search": usually, the program is careful about what
>>could happen to him (looks at a lot of the opponent's moves). But if you
>>detect an agressive move (attacking the opponent), it could make sense
>>to "shift" and be careful for the opponent (looking at a lot of your
>>moves to see if a combination is possible).
>
>
>When I know I have a good main-line
>
>1 ply 2 ply 3 ply 4 ply 5 ply 6 ply 7 ply
>2nd best best 3rd best best 2nd best best 2nd best
>
>
>I could try to prove my 1,3,5,7 moves by shifting the principle.
>I know the best defense on ply1 is ply2. But i am NOT sure if ply 1 is
>really the best move.
>
>There must be a method to shift it and to keep the blunders in the
>1,3,5,7,9 iterations very small. Genius-level-small.
Sorry, but I still don't see your point. If you try to see if ply 1 is
really the best move by shifting the asymetry, you just end with 2
searches, each being smaller than a full width search, but the sum of
the 2 being bigger than a normal search.
>One other thing:
>I don't think the MxSy indication of the old Mephisto machines has
>something to do with plies.
>
>lets say M2S15.
>
>Or M4S17.
>
>Many people always said:
>This could mean M2 = 2 plies "brute-force" with overall S15=15 plies
>selective peak.
>
>I don't think this interpretation was ever true.
>
>Try it out with an old dedicated Mephisto machine.
>
>Use e.g. the Roma 16 Bit (68000 12 Mhz).
>Let it compute 1 second and force move.
>Write down the evaluation and the complete main-line and the MxSy =
>search-indicators.
>And you will be very astonished:
>Although M is often 0 or 1 the main line is very good, long, and
>accurate !
>HOW can any chess program create these accurate main-lines in 1 second
>on such a slow machine without hash-tables ??
That's the very interesting point we have to find out about. In fact the
strength of Lang programs is almost only in this feature.
In my previous post, I tried to give an idea. I hope you have already
written a chess program, or else the following may be cryptic for you:
Here is a rather classical alpha-beta search using a SEE in the terminal
nodes (leaves). I don't take care in this simple approach of using it
only at odd plies, but I should do it in the real program. A simple way
is to call Search with odd depth only.
int Search(side, depth, alpha, beta) {
if (depth==0) return(eval(side)-loss(side));
generate_moves(side);
for (every move) {
make_move();
score=-Search(opponent(side), depth-1, -beta, -alpha);
unmake_move();
alpha=max(alpha,score);
if (alpha>=beta) break;
}
return(alpha);
}
the call loss(side) is a call to the SEE. It returns the value of the
worst exchange that the opponent of "side" can make. For example, if the
opponent can win a pawn, loss(side) returns +value(pawn). The SEE can be
improved to return +INF when side is in check, or threatened to be mate
very soon.
Then, here is an improved version that is able to extend the search by 8
plies when non quiet positions are encountered:
int SelectiveSearch(side, depth, alpha, beta) {
// Notice the change here:
if (depth==-8) return(eval(side)-loss(side));
// Here, when we are in the selective part of the
// tree, we try to find a pessimistic score,
// which may improve alpha, or even produce
// a cutoff.
if (depth<=0) {
pessimistic=eval(side)-loss(side);
alpha=max(alpha,pessimistic);
if (alpha>=beta) return(alpha);
}
// No changes in the following...
generate_moves(side);
for (every move) {
make_move();
score=-SelectiveSearch(opponent(side), depth-1, -beta, -alpha);
unmake_move();
alpha=max(alpha,score);
if (alpha>=beta) break;
}
return(alpha);
}
In you want to degenerate the above version into a simple quiescence
search, just do:
pessimistic=eval(side)
and change generate_moves into generate_captures.
You can also make a change in order to always get a "sample" of what
could happen beyond the nominal depth (the depth you use in the first
call to "SelectiveSearch"). Change
if (depth<=0)
by
if (depth<=0 && beta<+INF)
Assuming you initially call the search by
SelectiveSearch(computer_side, depth, -INF, +INF)
the above change allows the program to always compute at least one main
line of length depth+8, with only a small part of the cost of a real
depth+8 search.
Many improvements are possible, especially generating only checks and
captures when depth<=0 and eval(side)<alpha-margin (futility pruning).
This is not really today's subject!
What do other programmers think of this?
I have implemented something close to the SelectiveSearch above in my
previous 16 bits versions of Chess Tiger. But my SEE and my evaluation
was not fast enough to be competitive. The current version of Chess
Tiger is much more "fast and stupid", and plays much better. But I'm
still not satisfied whith it and could return soon to the
"SelectiveSearch" method.
>As I said, there is a matrix that correlates the length and the search
>depth and (DAN, Vincent, I need your memory-help) when I remember it was
>
>(2 to the power of search-depth)+1 = length of main-line.
I'm not sure you need to go in such a strange field to explain the Lang
algorithms behaviour. But tell us more!
>If you prune heavily in the odd plies, and less in the even ones, and
>you have a static-exchange evaluation instead of capture-search, you can
>spare much computation time.
This does not give us a credible explanation of the very long lines we
get at ply 0. Check out my "SelectiveSearch"!
>If it comes to a capture in the main line the root evalaluation of
>genius if very very very often bullshit.
This could mean Genius uses a lot of static piece-square tables.
Programs using this approach often make serious errors when going from
middle game to endgame for example. This generally happens after a queen
exchange. See how much Genius evaluation drifts after such an exchange!
>All the advantage he had in the 80ties were eaten by opponent programs
>using null-move and hash-tables.
You can use null move in the "SelectiveSearch" algorithm I decribed
above. You can use hash tables also.
Look at the great endgames Genius plays. In my opinion, the way Richard
searches the tree is the key point to achieve such a great play. Of
course his passed pawns evaluation is great too, but without the depth
of the selective search it wouldn't be so efficient.
Richard can use null move and hash tables, and his algorithm is still
vastly superior in endgames.
Maybe the only weakness of Genius is an over-use of square-piece tables.
Worked well with slow computers, but now a dynamic evaluation would be
more accurate, especially to avoid the "blemish effect" (what happens
when you misevaluate an endgame position emerging from a queen exchange,
using the still active middle game tables).
>Today his concept is rusty. It still works but cannot reach the top
>again.
Wrong. It is a more intelligent approach, and could well be the future
of computer chess.
But I think we don't speak about the same thing. You were talking about
the asymetrical search, and you are right in this field. I'm talking
about expanding lines at the end of the search.
I would like to hear about other programmers opinions, but this is a
very sensitive domain, and I bet the only thing we will get is silence
from Chris, Ed, and other talented people. Too bad, cause I'd bet Rebel
does (or did) things like that too. CSTal is a slow program, so it could
be using it also.
So amateur programmers opinions are welcome. Together, can we get into
Lang's secrets before censorship covers the subject? :)
Christophe
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.