[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[computer-go] Perfect sub-tree move path (was Brute Force...)...
Don (and others),
Consider Vincent's original assertion - there is a perfect line of play. As you (and others) have
pointed out, the perfect "line" of play is actually a tree subset of all possible moves at each
node. This tree notion results in an exponential explosion, one that vastly exceeds the
memorization capabilities of humans.
And even given awesome data encoding techniques, also vastly surpasses the any storage mechanism
available now or for centuries into the future, presuming electron spin as the memory mechanism
and entire planets as the atomic databanks. This leads me to the conclusion...the perfect
"sub-tree" play paths is a theory with little or no value.
Now consider that we are talking about two human (and presumably finite and fallible) players.
Given player A cannot perfectly memorize the huge trees of decisions occurring just a small number
of moves out (Go or Chess), the pressure on player A is to choose the move with the tree subset
with the shortest "long branch". This is the move leading to a Player A win in the least number
of remaining moves. This means that there are that many fewer options Player A must have
committed to memory to ensure he stays with the "perfect" sub-trees. It increases his odds of
completing the game "perfectly".
However, this same pressure acts on player B in exactly the opposite way. Player B’s goal will be
to ensure he chooses the move that requires player A have the maximum number of future choices
committed to player A’s limited memory. Player B is playing to maximize Player A’s fallibility.
Player B is not playing to win, lose, or even to tie while player A is successfully remaining on
the "perfect" play track. Player B is merely trying to push player A into a board state for which
player A (being fallible which implies forgetful) cannot recall the "perfect" move.
If player B eventually succeeds in getting player A to make an "imperfect" move, the game moves
into an state where the outcome is no longer guaranteed, and returns to probabilistic.
>From all of this, I make the following assertions:
A) There is currently no means by which to produce a “provable” or “certain” perfect sub-tree move
path data set. There is neither the computation power nor the storage capacity to deal with it
for Chess or Go. Checkers is now converging on producing that solution. Chinook’s endgame DBs
are now finally approaching the first half of the game. They started from the end game and are
working backwards. This is not reasonably possible with Go. I speculate it is not even
reasonably possible with Chess, but have not given it sufficient thought to be sure.
B) If ever a single “perfect path” is discovered through either Chess or Go having the appearance
all moves from game start to end are forced, the motivation on player B to not cooperate in
following that path will cause it to NEVER BE COMPLETELY PLAYED, thereby taking away the path’s
claim to value.
C) For the foreseeable future (centuries), it is going to be creativity (likely human, unlikely
computer) that finds lines off of know sequences which alter play. This can be seen as Go Joseki
DBs are occasionally updated when some 9 dan, after spending years researching and playing,
discovers a nuance of weakness in a particular response, exploits it and then the world finds out
when he utilizes it in a game.
For me, this leads me to be quite optimistic about Go’s future. I am not so interested in Chess
anymore thanks to the brute force techniques finally playing at GM levels.
Jim O’Flaherty
--- Don Dailey <drd@xxxxxxxxxxxxxxxxx> wrote:
>
> Joss,
>
> > 1) White wins and so black has no real "best move", (s)he therefore
> > plays as well as possible, but always knowing that a loss was inevitable
> > assuming that white plays perfect responses.
> > ...
> > ... If not, black may as well resign after the first move
> > and so the single best line is simply: White moves, black resigns.
>
> Personally, I don't think there is much basis for defining "resign" as
> a best move (even in a losing position) which is essentially what you
> are doing. "Best" means better than the rest and it makes sense to
> consider it valid for the "the rest" to be a null set. (At least it
> makes sense in set theory to consider null sets valid sets.)
>
> As you point out, there are other ways to define "best." You can
> define "best" based on opponent modeling, trying to make things more
> complicated for the opponent. But then this is not really chess, it
> is a different game which is no long deterministic. I admit that it
> is probably more like the game as humans play it!) It's probably
> likely that based on this definition the "best" move may actually turn
> a draw into a loss in some cases if it can increase your chances of
> winning against a fallible opponent.
>
> This is just for fun, but if you want to extend your definition of
> "best" and make it a little more "human", I would try something like
> this:
>
> 1. If position is a win, the best move leads to checkmate in the
> least number of moves. If you are on the losing side, the
> "best" move delays the inevitable for as long as possible.
>
> 2. Draws are little trickier due to 50 move rule, insufficent
> material, etc. So I would go with this:
>
> Both sides want to delay the game as long as possible
> (presumably to give the opponent a chance to blunder.) There
> are 4 ways to draw (not including by agreement which we define
> to always be "bad"):
>
> 1. Three fold repetition.
> 2. stalemate
> 3. Insufficient material.
> 4. 50 move rule.
>
> OBSERVATION: All games in chess must eventually terminate, if not by
> an outright win or stalemate, by an eventual draw by repetiton.
>
> Throw out the 50 move rule for this definition, it's not
> technically relevant and is a human concieved device to shorten
> the game.
>
> Throw out insufficient material. This is another device to make
> the game much nicer for human players and is not intrinsic to
> the game. All of these kind of games terminate eventually due
> to repetition.
>
> So the best move in a drawn position, is the move which delays
> the "bitter end" the longest, assuming no 50 move rule or
> insufficient material!
>
> Please note, even 3 fold repetition is not a draw unless claimed, but
> for calculating this new hypothetical definition of "best" move, we
> assume that it MUST be claimed when it first occurs, otherwise the
> game would NEVER terminated in many positions. (We could technically
> even throw out repetition, but then our omnicient computer would hang
> up in an infinite loop trying to find the end of the game and it would
> always play for repetition when a win wasn't possible.)
>
> - Don
>
> _______________________________________________
> computer-go mailing list
> computer-go@xxxxxxxxxxxxxxxxx
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/