Author: Don Dailey
Date: 09:30:54 06/12/98
Go up one level in this thread
On June 11, 1998 at 21:09:33, Fernando Villegas wrote:
>On June 10, 1998 at 18:20:19, Don Dailey wrote:
>
>>On June 10, 1998 at 17:59:22, Fernando Villegas wrote:
>>
>>>On June 10, 1998 at 07:26:02, Mark Taylor wrote:
>>>
>>>>On June 10, 1998 at 05:58:53, Carlos Adan Bonilla wrote:
>>>>
>>>>>...the computer may select a
>>>>>complicated line rather than an "easy-to-see-for-humans" line, even if
>>>>>that line is not so good.
>>>>>Also, in lost positions, the computer will select the lines in which
>>>>>there is an opponent move that is a mistake and could turn the game back
>>>>>to a drawing position (or winning).
>>>>
>>>>I have had similar ideas & believe that statistically this sort of
>>>>strategy would gain better results (esp. against human & weaker computer
>>>>opponents). The strategy does not mean playing weaker moves, when there
>>>>is a better move available. It means playing a move that gives the
>>>>opponent a choice of one good move out of ten bad moves, rather than
>>>>playing a move where the opponent has one bad move & ten good ones, even
>>>>though an alpha-beta search might return identical scores for the two
>>>>moves.
>>>
>>>
>>>I have thought of this same idea and even I posted here speculating that
>>>a kind of device like that could be one of the secrets of CSTAL.
>>>Precisely I said that the CSTAL style suggested that he did not use the
>>>usual alfa beta porunning techniques, but something different, something
>>>where the main purpose is creating pressure, not just to suppose the
>>>adversary will do the very best move
>>>Fernando
>>>
>>>I have thought about how this kind information could be gathered in an
>>>>A/B search without slowing things up - it would mean searching the very
>>>>sub-trees that A/B currently ignores. Maybe this could be gathered in a
>>>>search on the programs' turn when TOOT has predicted the opponents move
>>>>(& the programs' next move has already been computed).
>>>>
>>>>Any ideas anyone?
>>
>>
>>I tend to doubt the idea it does not do alpha/beta pruning. It's style
>>could perhaps be explained simply by aggressive evaluation. Thorsten
>>tried to explain it once to me but it was in such high level language,
>>there were no useful details (which perhaps was the intent!) I got
>>a vague impression it was pretty selective but this doesn't explain
>>an aggressive style. When playing Cilkchess against it, I noticed
>>it's scores were often way below or above a pawn even in positions
>>that seems relatively even to me.
>>
>>I think it might be possible to create such a program by making
>>key evaluation terms very aggressive. I imagine getting it right
>>takes a lot of tinkering. It often plays completely unsound moves,
>>but gets away with it. Its strength seems to be based more on
>>"playing the opponent" than technically correct chess. But this
>>is truly impressive since I view this as the more difficult task.
>>It truly does play like "Tal", knowing which moves give it winning
>>chances despite the "theoretical correctness" of the move.
>>
>>- Don
>
>
>Hi Don:
>I am not programmer and so maybe I have not the right to even discuss
>theses issues with you, but let me do a try. If I do not understand this
>wrong, alfa beta search technique is based in a selection mechanism in
>which the engine choose the line where the adversary can get the minimun
>amount of score, no matter how the evaluation is done, but what if the
>engine choose a line where the adversary maybe can pick a better scored
>move BUT there a lot of other moves lurking there with traps, bad
>scores, etc? Then it is no more alfa beta oprunning such I understand
>it. Or in other words, the engine is not playing on the ground to
>suppose perfect moves -in terms of his own code source- by the adversay,
>but putting the maximum number of problems. Please, Don, explain me the
>movie -as we say in chile- if I am werong supposing that in thisd last
>case is not alfa beta-
>Fernando
Hi Fernando,
Here is an example of a beta cutoff. The maximizer thinks high scores
are good, the minimizer thinks low scores are best. As you see, the
minimizer will choose the move with the score of 5 since it is the
lowest of his options. He will look at the 7, 8 and 6 though hoping
to find a lower score but he will not be able to.
In the second line, the first move the minimizer looks at is a 2 which
(for him) is better than the 5. So we already know that if the
maximizer plays the second move, the minimizer will have the option of
getting a score of 2 which the maximizer can simply avoid by playing
the first move. Obviously, the maximizer would rather get a 5 by
playing the first move than getting a 2 (or less.) In my example, it
turns out the minimizer would actually get a -5 but this is not
relevant unless the maximizer is dumb enough to play the second move.
These other moves (19, -5, 3 and 6) are a waste of time to search
because the maximizer already knows he should not play the second move
leading to them.
Maximizer -> 5 <= 2
/ /
/ /
/ | | \ /
minimizer -> 5 7 8 6 2 19 -5 3 6
This is all alpha beta prunning is, it is guranteed to return the same
exact result that looking at EVERY move would. There is no risk or
change of moves or style issues. It is just a great big free speedup,
especially with big tree's where these cutoffs are happening all over
the place.
You are right when you say we expect the opponent to play the best
moves (from the computers point of view.) I've had MANY MANY people
suggest that the program would go beserk if the opponent did not play
the best move, asserting that this would somehow confuse the program.
The search tree is not subject to psychological tactics and this would
only have the effect of letting the computer get a position IT thinks
is better. The only time this is a good strategy is if the computer
is wrong, but this is an evaluation issue, not a search issue.
Now you are suggesting a strategy that I think is quite sound. Given
a choice of moves, try to execute the ones that give your opponent the
greatest chance of going wrong. But I contend that this strategy is
nothing more than an alternate scoring method. This "new" method may
involve tree factors, but I guarantee it will wreak havoc with the
alpha/beta method. CSTAL seems strong enough to me that I tend to
doubt it is using this, but it is possible. Perhaps there are
approximations to this that are cheap to compute?
Essentially, there are two scoring strategies.
A) Play the very best move objectively. (Karpov, Fischer)
B) Play the move that gives you the best winning chances (Kasparov,
Tal)
In my opinion (subject to debate I'm sure) Karpov and Fischer applied
method A, always trying to play the very best move. Method B is
employed certainly by Tal, and by Kasparov in my opinion.
Method A I'll call the GOD method. Probably an omnicient being (with
a 32 man database) would employ this method. Method B is more human
and I feel all human players use it, even if they strive for method A.
Larry Kaufman hypothesised that if you indeed had the skill to always
use method A, you would get better results with method B against a
fallible opponent. The reason for this is that if you have a certain
draw, the best move on the board is ANY move that leads to a draw.
But an immediate repetition of position (for instance) might lead to a
draw. Why not prolong the game and give the opponent an opportunity
to err? Or perhaps you quickly trade down to a position that any weak
player can hold? Why not complicate things, even as we keep a draw in
hand.
This concept could in principle be extended to playing deliberately
unsound moves. If you are playing a weak master, knowledge of your
opponent and his weaknesses might require an unsound move to avoid a
likely draw. Now we are getting into a different kind of game theory
and probabilities, opponent modelling and other factors come into
consideration. It's all interesting stuff, and I think it likely
CSTAL does some of this stuff.
However, I find it challenging enough to just focus on sound play.
Trying to play other games with the search is a major distraction and
I'm more interested (from a scientific point of view) in making a
program play as correctly as possible. I guess you could say I'm
assuming the opponent is a "perfect" chess player in the game
theoretic sense of the word. If I had a choice of creating a 2900
rated chess player that played as perfect as possible or one that was
excellent at playing "swindles" and "sacs", I would prefer the more
boring (but theoretically more sound) first method.
The most desirable method would be a combination of the two. First
priority absolute soundness, but within this, try to pose as many
problems for your opponent to solve as possible.
- Don
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.