Talk:Game complexity
From Wikipedia, the free encyclopedia
[edit] Move-sequence complexity bogus?
I cut this section from the article because (a) I couldn't find anything on the web that indicates that this is a real term in game complexity research; and (b) as far as I can tell from this somewhat confusing definition it's the same thing as game tree complexity. Gdr 12:19, 2004 Jul 8 (UTC)
- A "move-sequence" is the succession of moves from the "game start" to the "game end". A "move" (Go term) is the action of a player performed during his turn and thereby transforming one "game state" to its successor, its next "game state". The "number of move-sequences" is the total number of move-sequences that might occur legally according to a game's rules. It is expressed as a function in a parameter. A typical parameter is the number of objects that form the board of a game. E.g., N = 64 squares in Chess or N = 361 intersections in Go. Since determining a "number of move-sequences" M(N) is a difficult mathematical problem for many interesting games, one uses bounds to limit the unknown, precise functions: a "lower bound" L(N) or an "upper bound" U(N). The following holds: L(N) < M(N) < U(N). E.g., for Go (with simple rules) trivial bounds are: L(N) = N! and U(N) = N^(3^N). So for the precise "computational complexity" M(N) of Go we can say: N! < M(N) < N^(3^N).
[edit] Legal Positions In Tick-Tack-Toe
I have written a program which counts the legal positions in tick-tack-toe and I get 5890.
[edit] Other board games
What about Arimaa? Does anybody have a clue about that one? 132.231.54.1 21:15, 1 Feb 2005 (UTC)
[edit] Where the numbers in the table come from
I would like to see a reference to the numbers in the complexity table, i did some calculations for the othello game and i'm getting lower values that the ones show in the table.
[edit] Average Branching Factors and Average Moves Per Game
I think it would be most clarifying to make the complexity of various board games directly comparable by adding columns to the table for the average branching factors and average moves per game (for a rationally played game). It may not be easy to retrieve this information for some entries, however. --BadSanta
- I agree. Anyone know any numbers/calculations? Give me formulas and I can calculate. 70.111.251.203 19:09, 21 February 2006 (UTC)
[edit] Can someone update the table with the added games?
Various cells in the table are blank. I don't think that FischerRandomChess would have the same values as regular chess.
- Well, only one starting position in FRC would return EXACTLY the same values as in standard chess. [Guess which one?] The rest of the 960 starting positions possible for a game would return slightly different values, higher or lower, with the average of all for a game randomly chosen being very close to that of standard chess. After all, we are dealing with exactly the same pieces on the same board, just differently placed at the beginning of the game. --AceVentura
[edit] Complexity class for Connect6
An editor suggested that generalized Connect6 might be EXPTIME-complete. I removed this, because it's almost certainly false: if I understand the rules of Connect6 correctly, since pieces never move or capture once placed, a game can last no more moves than there are spaces on the board, and that's a polynomial function of the board size. It may well be PSPACE-complete, using similar methods to those used to show that generalized Gomoku is PSPACE-complete, but I think we need a reference. Gdr 01:16, 3 January 2006 (UTC)
[edit] Under which category?
Shouldn't this article be under combinatorial game theory and not just regular game theory?70.111.251.203 03:05, 7 February 2006 (UTC)
- Sure. I've changed it, but in future, Be bold. ··gracefool |☺ 04:35, 7 February 2006 (UTC)
[edit] Chart of Complexities
Although certain game exceed other games in complexity by state space and/or game tree, this is largely do to the size of the boards, numbers of pieces, etc. Thus the table is misleading; the game of Chess has a board size of 8x8, thus 64 squares, Go has a 19x19 board, with 361 intersections. Go is over 5 times as large, while the game complexity is comparatively only approximately 3 times as complex (4 if you're generous, doesn't matter). {correction - the numbers for Go were horrendously wrong when you were looking at the comparison. The actual numbers for Go are 10 to the 172 for state space and 10 to the 766 for game tree.} Because of the lack of a 1:1 ratio, the games can't be compared on equal ground. The game of chess is actually more complex for it's size. I'm not sure how pieces play into this. Here is a table:
| Game | log(State space) | log(Game tree) | Complexity class of suitable generalized game | Board size (number of squares/intersections for a piece) |
|---|---|---|---|---|
| Tic-tac-toe | 3 | 5 | PSPACE-complete | 9 |
| Nine Men's Morris | 10 | 50 | ? | ? |
| Awari | 12 | 32 | ? | ? |
| Pentominoes | 12 | 18 | ? | ? |
| Connect Four | 14 | 21 | ? | 42 |
| American checkers | 21 | 31 | EXPTIME-complete | 64 or 32? |
| Lines of Action | 24 | 56 | ? | 64? |
| Othello | 28 | 58 | PSPACE-complete | 64 |
| Backgammon | 20 | 144 | ? | 24? |
| Chess | 46 | 123 | EXPTIME-complete | 64 |
| Chess960 | 46 | 123 | EXPTIME-complete | 64 |
| Xiangqi | 75 | 150 | EXPTIME-complete | 90 |
| Shogi | 71 | 226 | EXPTIME-complete | 81 |
| Go | 172 | 360 | EXPTIME-complete | 361 |
| Connect6 | 172? | 140? | ? | any size depending on board size, but if on 19x19, then 361, can be larger though |
| Arimaa | 54 | 440 | ? | 64 |
This chart actually shows how Shogi and Arimaa are the most complex games per space. Shogi because of both numbers, and Arimaa only because of the Game Tree. Does anyone know where that 440 number for Arimaa's Game Tree came from? It doesn't make much since considering how you can choose the initial setup of pieces, but there are superior setups, and almost always people put all their rabbits in the back row.
70.111.251.203 14:08, 7 February 2006 (UTC)
- Maybe there is a relationship that should be made between the state space and the game tree too. 70.111.251.203 13:34, 9 February 2006 (UTC)
[edit] Poker
There are a lot of different variants of poker, and the complexities vary depending on the number of players; maybe we should create a separate page just for the poker variants? Ben Standeven 20:31, 9 March 2006 (UTC)
- If you have the numbers, put them on here for now. No point in making a seperate page if there is very little information on it. 128.6.175.59 21:09, 13 April 2006 (UTC)
[edit] Moves per game in Arimaa
I removed the question mark from the Arimaa average game length of 35. That is in fact the average length of rated games between humans on arimaa.com, as calculated from the publicly available database of games played there. Games involving two computers are slightly longer on average because sometimes neither computer can come up with a plan. Games between expert humans (rated over 1900) are also longer on average, about 45 moves per game. However, compared to chess, top-level Arimaa is intrinsically a slightly shorter game. The greater length of Arimaa games occurs because agreed draws are forbidden and resignation is highly discouraged on arimaa.com. If resignation and agreed draws were forbidden in chess, the average expert game of chess would probably be well over 45 moves. --Fritzlein 17:53, 19 June 2006 (UTC)
Also, how was the game-tree complexity of 190 calculated for Arimaa? With an average branching factor of 15000, and 35 moves per game (70 half-moves) I calculate log(15000^70) = 292. --Fritzlein 18:00, 19 June 2006 (UTC)
[edit] E[a^b] != E[a]^E[b]
The article defines game-tree complexity to be "the total number of possible games that can be played". It then says "a reasonable estimate can be made by raising the game's average branching factor to the power of the number of plies in an average game" but this is completely wrong. For example in chess the estimate seems to be 30^(2*40) = 1e+118, but even if only 1% of games are 60 moves long instead of 40 moves, those account for 0.01*30^(2*60) = 1e+175 games. So on for even rarer, but longer games. In other words to estimate the total number of possible games by computing a^b, one cannot use averages for a and b, instead one should use values closer to the maximum possible.
I conclude that either game-tree complexity is NOT "the total number of possible games that can be played" (but something else), or pretty much every number in the table is grossly underestimating the game-tree complexity. Which one is it? 69.109.189.208 02:10, 19 February 2007 (UTC)
[edit] Example tic-tac-toe
It is not true that
"When rotations and reflections of positions are considered the same, there are only 26,830 possible games."
Proof: Firstly, no game is symmetrical with respect to rotations or reflections. That is because each game has at least five moves, and a symmetry can be preserved only for at most three moves. Please note that we are talking about game-tree complexity, where the order of the moves is relevant, see article. Secondly, the order of the symmetry group of rotations and reflections is eight. Therefore, there are 255168/8 = 31896, not 26830, different games up to rotations and reflections. --80.129.78.128 15:26, 19 March 2007 (UTC)
