| |
Main
Date: 06 Dec 2006 15:20:19
From: Bucky
Subject: what kind of games are solvable?
|
Using the definition of "solved game" meaning that the first player
will always win, lose, or draw given perfect play.
I was trying to think of what characteristics of games make them
theoretically solvable or unsolvable. I think games involving random
chance are not solvable (Monopoly). Rock Paper Scissors is not solvable
because the action is simultaneous. Basketball is not solvable because
it doesn't have a finite set of moves.
Is there a simple characteristic that determines whether a game is
theoretically solvable? For example, "All perfect information games are
solvable. All non-perfect information games are unsolvable."
|
|
| |
Date: 07 Dec 2006 12:21:27
From: David Richerby
Subject: Re: what kind of games are solvable?
|
Bucky <[email protected] > wrote:
> Using the definition of "solved game" meaning that the first player
> will always win, lose, or draw given perfect play.
There are various definitions of `solved'. The one you're using is
often called `ultra-weakly solved', meaning that we know the result of
perfect play but we don't necessarily know what perfect play looks
like. (An example of such a game is chomp.)
> Is there a simple characteristic that determines whether a game is
> theoretically solvable? For example, "All perfect information games
> are solvable. All non-perfect information games are unsolvable."
All finite games of perfect information are solvable. Many infinite
games of perfect information are also solvable (for example, if the
set of winning positions for one of the players forms what is called a
Borel set, the game is solvable).
There are some non-perfect information games that are solvable. I
can't think of any non-trivial examples but here's a trivial one.
You pick a number between one and ten, without telling me what it is.
I pick a number between one and ten, without telling you what it is.
Whatever the numbers are, I win.
:-)
This all falls within the realm of Game Theory.
http://william-king.www.drexel.edu/top/eco/game/game.html
looks like it might be a good introduction but I've not done more than
skim it.
Dave.
--
David Richerby Erotic Surprise T-Shirt (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a fashion statement but not
like you'd expect and it's genuinely
erotic!
|
| |
Date: 06 Dec 2006 19:02:15
From: Ray Gordon, creator of the \pivot\
Subject: Re: what kind of games are solvable?
|
FINITE games are solvable.
--
Ray Gordon, Author
The OFFICIAL Ray Gordon Blog:
http://moderncaveman.typepad.com
"Bucky" <[email protected] > wrote in message
news:[email protected]...
> Using the definition of "solved game" meaning that the first player
> will always win, lose, or draw given perfect play.
>
> I was trying to think of what characteristics of games make them
> theoretically solvable or unsolvable. I think games involving random
> chance are not solvable (Monopoly). Rock Paper Scissors is not solvable
> because the action is simultaneous. Basketball is not solvable because
> it doesn't have a finite set of moves.
>
> Is there a simple characteristic that determines whether a game is
> theoretically solvable? For example, "All perfect information games are
> solvable. All non-perfect information games are unsolvable."
>
|
| | |
Date: 08 Dec 2006 11:37:06
From: David Richerby
Subject: Re: what kind of games are solvable?
|
Ray Gordon, creator of the \"pivot\" <[email protected] > wrote:
> --
> Ray Gordon, Author
> The OFFICIAL Ray Gordon Blog:
> http://moderncaveman.typepad.com
This is excellent news. For too many years, I have struggled with
the tide of unofficial Ray Gordon blogs, never knowing which ones
to believe. But now I can read the OFFICIAL blog and be happy.
Dave.
--
David Richerby Adult Projector (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ 16mm film projector that you won't
want the children to see!
|
| | |
Date: 08 Dec 2006 12:32:58
From: Ray Johnstone
Subject: Re: what kind of games are solvable?
|
On Wed, 6 Dec 2006 19:02:15 -0500, "Ray Gordon, creator of the
\"pivot\"" <[email protected] > wrote:
>FINITE games are solvable.
But chess with about 10^100 games might as well be infinite.
see:
http://members.iinet.com.au/~ray/Chessgames.htm
|
| | | |
Date: 08 Dec 2006 06:39:15
From: Ed Seedhouse
Subject: Re: what kind of games are solvable?
|
On Fri, 08 Dec 2006 12:32:58 +0800, Ray Johnstone <[email protected] >
wrote:
>On Wed, 6 Dec 2006 19:02:15 -0500, "Ray Gordon, creator of the
>\"pivot\"" <[email protected]> wrote:
>
>>FINITE games are solvable.
>But chess with about 10^100 games might as well be infinite.
>see:
>http://members.iinet.com.au/~ray/Chessgames.htm
The mathematical concept of "solvability" ignores such things. A method
is known for solving chess completely and the rest is a mere
implementation detail to a mathematician.
The fact that it would take longer by far than the estimated lifetime of
our whole universe to compute is beside the point as far as
"solvability" is concerned.
|
| | |
Date: 06 Dec 2006 21:28:37
From: johnny T
Subject: Re: what kind of games are solvable?
|
Ray Gordon, creator of the "pivot" wrote:
> FINITE games are solvable.
>
practically finite games are solvable.
|
|
