[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [computer-go] Perfect sub-tree move path (was Brute Force...)...
Don,
Point taken! As I was writing that, I did think of the quantum computer and how technically it
may be able to handle some form of "meta-data" representation and perhaps cover much more area.
And I agree...for the same reason existing memorizing Joseki's are valuable to a player as he
skills up.
Jim O'Flaherty
--- Don Dailey <drd@xxxxxxxxxxxxxxxxx> wrote:
>
> > 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/
>
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/