I think the discussion about solving Go on 7x7 is lacking some clarity. I am
not an expert in game theory, but hopefully my understanding is correct and may
help everyone understand and use the same terminology for game solutions.
Solving a game is not a matter of opinion--there are specific definitions and
requirements for solving a game.
The solution to a game involves knowing the final result of a game from a given
position when both sides play optimally. The different types of solutions
(ultra-weak, weak, strong) vary depending mostly on what positions they deal
with (the initial position, any position, etc) and method they use to prove the
solution (just proof or proof plus algorithm).
In a simple game with a small game tree, like Tic-Tac-Toe (Naughts and
Crosses), it is feasible to show all possible positions (765 with symmetry) and
you could prove perfect play directly on the entire game tree (showing that
perfect play from both sides results in a draw). Most (interesting!) games are
too complex to expand the entire game tree so the solution consists of a
logical proof and/or algorithm. In order to condense (or ingore) large
portions of the game tree, a solution via proof uses assumptions and logical
reasoning to derive a result based on perfect play (without necessarily showing
what perfect play looks like). A solution via algorithm shows that perfect
play leads to a win (or draw depending on the game) from a given position for
any possible opponent response.
A strong program that plays a game and never loses (!) is not a solution unless
there is a proof that shows it can win (or draw) for any possible opponent
strategy/move.
Let's re-examine the definitions of solutions (from
wikipedia: http://en.wikipedia.org/wiki/Solved_games):
Ultra-weak
In the weakest sense, solving a game means proving whether the first player
will win, lose, or draw from the initial position, given perfect play on both
sides. This can be a non-constructive proof (possibly involving a strategy
stealing argument) that may not actually help determine this perfect play.
Weak
More typically, solving a game means providing an algorithm that secures a win
for one player, or a draw for either, against any possible moves by the
opponent, from the beginning of the game.
Strong
The strongest sense of solution requires an algorithm which can produce perfect
play from any position, i.e. even if mistakes have already been made on one or
both sides.
The key words are "solving/solution", "proving/proof", "perfect play", and
"algorithm".
So a strong program that never loses is an "algorithm" which may or may not
embody "perfect play", but is not a "solution" without the accompanying "proof"
which shows it is "perfect play".
Ben.
________________________________
From: Aja <[email protected]>
To: [email protected]
Sent: Wednesday, July 13, 2011 8:38 PM
Subject: Re: [Computer-go] 19x19 opening books
Thanks Erik, Alvaro and Ingo. I got the point now. So, even if a strong Go
program never lost on 7x7, it still solves nothing because the opponent didn't
try any possible moves.
Aja
----- Original Message ----- From: "Álvaro Begué" <[email protected]>
To: <[email protected]>
Sent: Wednesday, July 13, 2011 11:35 PM
Subject: Re: [Computer-go] 19x19 opening books
Ingo is right. But I interpret "weakly solved" the same way Erik does:
Not only do you have to provide a program that always obtains the best
result in practice, but you need to be able to prove that this is
always the case.
On Wed, Jul 13, 2011 at 11:29 AM, "Ingo Althöfer" <[email protected]> wrote:
> Proper komi will be integral,
> and the perfect result will be a draw.
>
> Ingo.
>
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
