: Clyde is teaching a graduate course titled
Games, Game Theory, and
the Theory of Games
He tells me that there are basically eight kinds of games governed by
three 2-valued parameters. (1) 2-player or multi-player,
(2) complete information or incomplete information,
(3) luck or no luck.
For example Chess or
are 2-player, no hidden information, no luck
(I won't quibble about the coin toss to see who goes first.)
There are natural examples of most of the combinations. The one
I have the most trouble with is multiplayer with no hidden information
and no luck.
(Clyde is NOT as dogmatic as the above indicates. One other
aspect I've left out for this post is that some games are
impartial and some are not.)
: Here is a multiplayer game with no luck and no hidden
pick up sticks
: For Clyde's class that not a game.
: Why not? Its alot more fun than NIM!
Help me answer my darling. What makes something a game rather than a sport?
Not sure pick-up-sticks is a sport either.
Lets try to get NATURAL examples of each category:
One issue- the terms are not that well defined
so you may disagree with some of these.
We break it into two basic categories
(for a better picture of the results goto
1) Complete Information
2) Incomplete Information
2-player, no luck. Go, Chess, Nim:
Nim has had some nice math associated to it.
Chess and Go have inspired very nice computer techniques
(was alpha-beta pruning developed for chess originally?).
There are some recent techniques for GO which I will talk about
in a later posting.
2-player, some luck: Backgammon, Can't Stop
(a natural game but not that well known). Sorry! (that's not
be apologizing, that's the game Sorry!). Parcheesi.
Multiplayer, no luck: Chinese Checkers.
I do not know of ANY other examples.
Multiplayer, luck: Monopoly (and similar games).
2-player, no luck. Stratego, Battleship:
These are debatable. In fact, it may that that if defined
carefully this combination is impossible.
2-player, luck: Gin and most 2-player card game.
Multiplayer, no luck: Clue where each player only moves 5 squares per turn,
so dice needed. One of Clyde's students families plays it this way, hence
it is a natural game.
Multiplayer, luck: Poker. Most multiplayer card games.
: Many games are hard via complexity theory. For example,
GO and CHESS are EXPTIME complete
Do these results tell us things about real games?
Posted By GASARCH to Computational Complexity
at 12/10/2009 10:58:00 AM