[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [computer-go] Perfect sub-tree move path (was Brute Force...)...
> 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.
Maybe, but not so sure. You are thinking only in terms of todays
technology and imagining only a few decades out. The physical laws of
nature seem to preclude the 32 man chess database, but I remember that
they said silicon had it's limits many years ago and they have pushed
way way past them. The quantum world is hardly understood and who
knows what is possible? Perhaps not in the 2000's but maybe the
2100's?
There are other ways to skin a cat too. Maybe some kind of
meta-database approach can give us the equivalent of the omnicient
database with several orders of magnitude less data combined with
sophisticated rules that we can't yet imagine.
But our discussion is more theoretical than practical, you are trying
to apply it directly practical.
Nevertheless, if such a database existed, it would be incredibly
valuable and the quality of play would mushroom considerably in chess,
perhaps not so in GO.
Even though we know it's not practical to keep very much of this
database in your head, the human brain can fill in a lot of holes with
meta-data. You could still learn thousands of opening sequences and
find pathways to positions you were quite comfortable with. Simply
training against such a database would improve your skill
significantly and be worth billions of these database positions.
- Don
Date: Fri, 12 Nov 2004 09:16:21 -0800 (PST)
From: "Jim O'Flaherty, Jr." <jim_oflaherty_jr@xxxxxxxxxxxxxxxxx>
Reply-To: computer-go <computer-go@xxxxxxxxxxxxxxxxx>
Sender: computer-go-bounces@xxxxxxxxxxxxxxxxx
X-Scanned-By: MIMEDefang 2.42
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/
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/