List of solved games?
Insane Ranter
Mike Hutton
> Is there an "offical" list of games that are solved?
What do you mean by "Solved"?
A more accurate term could be "solvable".
Noughts and Crosses is the most obvious case of a "solved" game. But
it is a simple game with no luck. Adding any element of luck produces
a problem which needs to be framed before you can hang any idea of
"solvability" to it.
There are innumberable "trivial" games where this applies. I can't
imagine anyone would bother compiling a list as it would be
exhausting.
Othello (Reversi) is certainly a solvable game; it's just that AFAICT
no-one has bothered to actually solve it yet (I nearly did at uni but
ran out of time).
There are surprisingly few of these; some games verge on being
solvable, but have an indeterminate length which makes life difficult
- chess and draughts being two cases in point.
What I suspect you actually mean is a list of games where there is a
single strategy which, when followed, will give either a guaranteed
victory, or an overwhelming chance of victory.
In that case the list would be rather longer, and subject to rather a
lot of personal opinion.
Mike.
Christopher Pound
Mike Hutton <huttm_s...@hotmail.com> wrote:
>What I suspect you actually mean is a list of games where there is a
>single strategy which, when followed, will give either a guaranteed
>victory, or an overwhelming chance of victory.
Solved is a common term. There are definitions and examples at
http://www.wikipedia.org/wiki/Solved_board_games
Brent Ross
// news:<iK3Ma.5201$wG....@fe04.atl2.webusenet.com>...
// > Is there an "offical" list of games that are solved?
//
// What do you mean by "Solved"?
//
// A more accurate term could be "solvable".
I doubt he's interested in "solvable"... that would include
every abstract, no luck game just to begin with. I'm pretty
sure he's just interested in ones that have actually fallen to
analysis and are known as forced wins or draws (that's typically
what "solved" means).
// Noughts and Crosses is the most obvious case of a "solved" game. But
// it is a simple game with no luck. Adding any element of luck produces
// a problem which needs to be framed before you can hang any idea of
// "solvability" to it.
//
// There are innumberable "trivial" games where this applies. I can't
// imagine anyone would bother compiling a list as it would be
// exhausting.
I can't imagine someone listing all the trival ones either... certainly
not the ones where you can draw the entire game tree out be hand
like Noughts and Crosses. Still, someone probably is keeping track
of the non-trivial ones and that list wouldn't be unreasonable.
// Othello (Reversi) is certainly a solvable game; it's just that AFAICT
// no-one has bothered to actually solve it yet (I nearly did at uni but
// ran out of time).
I believe 6x6 has been done... there are almost certainly people
working at solving this one as computer based competition has been quite
fierce in Othello since the 90s. The fact that it isn't solved yet
is merely a statement of the difficulty of the problem with today's
technology (both hardware and software). Nine-man Morris was cracked
not to long ago and that took some tricky evaluation techniques.
Othello is popular enough that I imagine that there are probably
a dozen Grad and PhD reseach projects right now working on how to
crack it.
// There are surprisingly few of these; some games verge on being
// solvable, but have an indeterminate length which makes life difficult
// - chess and draughts being two cases in point.
Chess, draughts, and even Go are inherently solvable. You seem to be
defining "solvable" as "close enough solved with current technology".
That's certainly an interesting list, but it's not a list of solvable
games (only a subset of it). It's also highly subjective (as you
point out) and so it's completely impractical.
A list of games that is solvable isn't practical either... it's simpler
just to list conditions and evaluate the games in turn (Concentration
has been "solved" for a set of conditions that abstract out the random
chance). The most practical list is probably games that have been
solved... after all, this is a fairly new science and a lot of the
effort has really been focused on a handful of games, so there really
can't be that many.
Brent Ross
Torben Ægidius Mogensen
> Othello (Reversi) is certainly a solvable game; it's just that AFAICT
> no-one has bothered to actually solve it yet (I nearly did at uni but
> ran out of time).
6x6 Othello has been solved and is (AFAIR) a win for the 2nd player.
I expect the ful game to be solved in a couple of years at most, given
the increase in computer capacity.
I seem to recall that Checkers has been solved, but that may also have
been on a smaller board.
The two above have been solved by what essentially amounts to
exhaustive search. There are also games (such as NIM) where the proof
of solution is by giving an efficient way to compute a winning move
(where such exist). Hex has been proven a sure win by the first
player, but this has been through a non-constructive proof (as
discussed here recently), so there is no effective algorithm for
playing the game.
Chess and Go are solvable, because they limit the length of a game
either by avoiding repetitions (Go) or limiting the number of moves
between captures (Chess). They are, however, not even close to being
solved. Solving Go on small boards should be realistic (and have
probably been done), but this would say little about the full game.
In general, any finite and determinsitic game can theoretically be
solved. Nondeterministic games (involving dice or randomly dealt
cards) can be solved up to probability (with perfect play, there is A%
chance of a 1st player win, B% chance of 2nd player win and (100-A-B)%
chance of a tie). Only very simple games of this kind have been
solved.
Torben
Glenn Kuntz
(No official list I'm aware of, unless one exists in some math department
someplace.)
Insane Ranter <n...@spam.net> wrote in message
news:iK3Ma.5201$wG....@fe04.atl2.webusenet.com...
Maurizio De Leo
"Insane Ranter" <n...@spam.net> ha scritto nel messaggio
news:iK3Ma.5201$wG....@fe04.atl2.webusenet.com...
> Is there an "offical" list of games that are solved?
I don't think this is "official" in any way, however :
Strongly Solved (perfect play in any position)
- Nought and Crosses
- Awari
- A bunch of artificial easy games (example 2x2 go)
Weakly Solved (reaching the game theoretical value from starting position)
- Connect-Four
- Nine Men's Morris
Ultra-weakly solved (the game theoretical value of the starting position is
known)
- Hex
Solvable ( given enough time on an existing supercomputer)
- Checkers 8*8
- Othello
Maurizio
Bruno Wolff III
>
> In general, any finite and determinsitic game can theoretically be
> solved. Nondeterministic games (involving dice or randomly dealt
> cards) can be solved up to probability (with perfect play, there is A%
> chance of a 1st player win, B% chance of 2nd player win and (100-A-B)%
> chance of a tie). Only very simple games of this kind have been
> solved.
That isn't quite correct. If A and B don't have a consistant valuation
of wins, losses and draws then the game isn't zero sum and hence might
not be solvable. If draws aren't possible then the game will be zero sum.
Blackberry
>
>Is there an "offical" list of games that are solved?
What would be the officiating body?
--
"Live the life you love, Use a god you trust
And don't take it all too seriously"
- Love and Rockets, "Your Private Future"
Chris M. Dickson
<n...@spam.net> writes
>Is there an "offical" list of games that are solved?
I've heard of the existence of a document called the "Olympic List"
which lists 15 games and states whether they are solved or not - and, if
not, what status the world's best computer players are at. You can find
it at http://www.mdcc.edu/users/dkaiser/paper/chap2.htm under "current
state" about half-way down. I don't know to what extent the situation
has changed since that document. (Oh, the wikipedia article someone
mentioned suggests that Awari was solved and found to be a draw only
last year, so that's pretty recent.)
See also http://www.cs.ualberta.ca/~games/ . Mig Greengard reports in
item 103 at http://www.chessninja.com/dailydirt05.htm that Jonathan
Schaeffer "... is an A1 nice guy. (Now back into checkers after years
away. He plans to solve the game once and for all.)"
Exciting!
Chris
--
Chris M. Dickson, Middlesbrough, Great Britain; ch...@dickson.demon.co.uk
Labyrinth Games: puzzle and game consultancy http://www.qwertyuiop.co.uk/
MSO Worldwide -*- Bringing Brains Together -*- http://www.msoworld.com/
Insane Ranter
"Blackberry" <sp...@anthrobunny.com> wrote in message
news:bds8s...@drn.newsguy.com...
> On Mon, 30 Jun 2003 19:39:41 -0400, "Insane wrote:
> >
> >Is there an "offical" list of games that are solved?
>
> What would be the officiating body?
Newsgroup
Glenn Kuntz
Omigosh, he really *is* insane! :-)
Have you bothered to search Google?
Here's a start:
http://www.wikipedia.org/wiki/Solved_board_games
Insane Ranter
"Glenn Kuntz" <crok...@frontiernet.net> wrote in message
news:EekMa.49$%r7...@news02.roc.ny...
Thanks!
Insane Ranter
Matt Ruff
-- M. Ruff
dan
Dan
--
"Every man ought to exercise the faculties of his mind, and think and
examine for himself, that he may be the less likely to be imposed on, and
that he may form as accurate an opinion as possible of the measures of his
ruler."
- A Farmer - (1810)
.
.
"Matt Ruff" <storyt...@worldnet.att.net> wrote in message
news:3F02779...@worldnet.att.net...
Sebastian Bleasdale
>Has Advanced Squad Leader been solved yet?
The only way to win is not to play at all.
--
Sebastian Heaven is full
- God Away
Insane Ranter
"Sebastian Bleasdale" <sbl...@chiark.greenend.org.uk> wrote in message
news:slrnbg6rjc...@chiark.greenend.org.uk...
> Matt Ruff wrote:
> >Has Advanced Squad Leader been solved yet?
>
> The only way to win is not to play at all.
Or play Squad Leader