[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [computer-go] Modern brute force search
Vincent,
You are basically saying that you believe only a single opening move
wins for white and the rest of white's initial move choices must be
either forced draws or losses for white.
I would find it remarkable if this was the case even with just the
first move.
I do believe there are many positions, maybe even most positions,
where only a single move is best in the game theoretic sense.
But you cannot be correct about there being only a single winning
line, here's the proof by contradiction based on your premise:
You say there is only 1 winning line and that chess is won for
white. Therefore only ONE white move wins (the rest must lose or
draw or you are already wrong.)
Black has 20 possible responses to any first white move. But all 20
responses MUST lose against the single winning white move (because
of your premise that white wins by force.)
Even though blacks 20 responses all lose, white must still have a
response for each of those 20 moves. That means we have already
branched to 20 different lines of play, all of them based on perfect
play by both sides.
But you say that there is only 1 line of play. There is a
contradiction here.
The only possible way the 1 line argument can hold is if the game is a
theoretic draw, in which case the only possibility is that 1 move
draws for white, everything else loses. Then it must be the same for
blacks first response to white, etc until the game ends in a draw.
So there are 4 possible cases here and only 1 of them can be true:
1. Game is won by white, many lines of "best" play.
2. Game is won by black, many lines of "best" play.
3. Game is a draw, only 1 single "best" line of play.
4. Game is draw, many lines of "best" play.
Option 3 is virtually impossible, though I can't furnish a proof.
Option 2 is extremely unlikely, although I have heard "tongue in
cheek" arguments for this based on the idea that black might be able
to take advantage of the fact that white has to be the first to
commit!
- Don
X-Sender: diep@xxxxxxxxxxxxxxxxx
Date: Thu, 11 Nov 2004 18:43:46 +0100
From: Vincent Diepeveen <diep@xxxxxxxxxxxxxxxxx>
Cc: computer-go@xxxxxxxxxxxxxxxxx
X-Virus-Scanned: by XS4ALL Virus Scanner
X-Scanned-By: MIMEDefang 2.42
At 10:05 11-11-2004 -0500, Don Dailey wrote:
>
>Richard,
>
>Vincent is NOT saying that there is a player who knows the best line.
>He is saying that if a hypothetical computer was built that could
>calculate the best line, the top players would commit it to memory.
>
>Of course I think Vincent underestimates the difficulty of doing this.
>I doubt there is a single "best line", there must be many ways to play
>a perfect game of GO.
I am sure there is just 1 line.
in chess egtb's we can clearly see that the optimal play involves usually a
single line.
Only when it is real simple then there is sometimes more choices.
>Just as a silly example, let's say it turns out that Chess is a draw
>from the opening position. Both white and black players must learn
Please assume white begins and wins. At the top level a top GM tries to
draw with black and hopes for a win with white.
If white begins and wins things are more difficult in chess.
idemdito in go. black begins and wins. no question about it.
>every possible way to achieve this result. Let's say that it's a draw
>against all 20 of the first possible moves. The black player must
>learn the correct response to every one of these 20 moves because he
>doesn't know which white will choose. The white player could
>specialize in just one of those first moves. However it will probably
>be the case that black has more than one "drawing" response to
>whatever move white chooses. White will be forced to know how to
>respond to each of these. Each player can take turns "specializing"
>in one subtree at each point, but it's easy to see this will still
>quickly mushroom out of control.
A major problem for software, and this problem is not easy to solve, is
that the longest line from a human viewpoint is very trivial to see usual.
It's the medium term 'computerish tactics' that is hard.
>A really strong human would benefit enormously from this knowledge,
>perhaps the equivalent of several hundred ELO rating points, but it
>still wouldn't guarantee a draw because he simply could not remember
>the whole tree of possibilities. What a really great player could
You seem to underestimate what professional players, go or chess usually know.
Usually they know more books than even the biggest hand written openings
book of a chessprogram. And that's several million big.
>attempt to do is memorize enough of the tree to get him to positions
>he feels very comfortable with, but this wouldn't be fool-proof.
memorizing is very simple. most players never forget any game they played.
it would be wishful thinking that in go the things aren't the same.
>In GO, it's even more unlikely that even a top player could memorize
>enough sequences to play perfectly, and I even doubt it would bring
>the level of play up very much since it would probably be common
>practice to quickly get away from the most "obvious" continuations in
>order to nullify the memorization.
In Go from human viewpoint many sequences are near to forced. The play
happens at a very tiny area of the board. That's why reading deep in go is
not a single problem.
Even a real poor go player has no problems to calculate a deep forced win
there.
In such forced wins usually there is many moves which from computer
viewpoint are 'unforced' by any definition.
A human just knows: "this move is needed to garantuee X Y Z".
No computer knows that. Go or chess.
Just imagine a pro player.
A good example is perhaps 10x10 draughts. Right from the start software
found tactical tricks which no human could ever find. Any trick from a
world champion was found instantly.
Yet for example my friend Marcel Monteba who plays at a master level
strength (doesn't have a title yet), he easily can beat any software.
>From a mathematical viewpoint it is very difficult to explain to scientists
why chess is so much simpler.
>From human viewpoint it is very simple.
In chess, just centralize your pieces and you win.
In draughts the center is not so important like in chess.
So building up is very important.
It's very difficult to explain to a program why a certain move doesn't
build up the position.
Now imagine this, draughts is 10x10 board from which 50 squares get used.
Go has exactly the same symmetry like chess, but also the center initially
is not so important.
That means that the move selection from human viewpoint is very simple and
from a computer viewpoint real terrible.
So a perfect playing database when using opponent modeling (see v/d Herik
and others for this publication www.icga.org), it is very well possible
that the computer plays a move after which the very deep win is just very
logical for a professional player as he just sees 1 move at a time as the
rest sucks. Especially in Go this scenario is very likely.
So if professional players, who already will go up a lot in strength by
being able to research what perfect play looks like, if you put them
against a 361 stone database, then obviously it's real difficult to fool them.
Just don't underestimate how good human learning is.
So far human learning has always outclassed anything else in the universe.
>- Don
>
> Date: Thu, 11 Nov 2004 08:21:20 -0600
> From: Richard Brown <rbrown@xxxxxxxxxxxxxxxxx>
>
> Vincent Diepeveen wrote:
> > In whatever game we play.
> >
> > The 361 stone go database will beat of course every player very easily,
> > just like a 32 stone database in chess will beat the strongest
players very
> > easily.
> >
> > The reality is of course that by the time we have a 32 stone database
and
> > that there will be a 361 stone database for go, that players have looked
> > into it and already know the best line by head.
>
> Really? Do you know a go player who knows the "best line"? Wow!
>
> > So they can win with white in chess and with black in go very easily
when
> > using the optimum line.
>
> Well, sure, theoretically. That is to say, _if_ they know the optimum
line.
>
> Again, I must ask, who is this go player, who knows the optimum line?
>
> I think that the rest of the go world would like to meet this great
master!
>
> --
> Richard L. Brown Office of Information Services
> Senior Unix Sysadmin University of Wisconsin System
> 780 Regent St., Rm. 246
> rbrown@xxxxxxxxxxxxxxxxx Madison, WI 53715
>
> _______________________________________________
> 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/