Computer Chess Club Archives

Search

Terms

Messages

Subject: Let's add 3x3 and 4x4x4 Tic Tac Toe; both are solved

Author: Jonathan Lee

Date: 19:43:34 12/11/02

On December 11, 2002 at 12:45:59, GuyHaworth wrote:

>H.J. van den Herik, J.W.H.M.Uiterwijk and J. van Rijswijck, in a paper:
>
>"Games Solved: Now and in the Future"
>
>give a table (Table 6) of the 'state-space complexity' and 'Game-tree
>complexity' [i.e. the number of positions and number of games] of some 18 games
>... in alpha-order:
>
>  Awari, Checkers, Chess, Chinese Chess, Connect-Four, Dakon-6,
>  Domineering (8x8), Draughts, Go (19x19), Go-Moku (15x15), Hex (11x11),
>  Kalah (6, 4), Nine Men's Morris, Othello, Pentominoes, Qubic, Renju (15x15),
>  Shogi
>
>Some of these like Connect-Four, Dakon-6, Domineering (for many board-sizes),
>Go-Moku (some variants), Hex (to 6x6 if not 6x7 boards), Kalah, Qubic and Renju
>have been 'weakly-solved', i.e. given a 'theoretical game-value' for the initial
>position.
>
>The authors address the question of the 'intrinsic difficulty of the game', for
>which the state-space and game-tree complexity numbers give a rough indication.
>
>However, it has to be admitted that there is a game with arbitrarily large
>state-space and game-tree figures which is not complex at all but trivial to
>evaluate, namely, Nim.
>
>The numbers following are the power of 10 for the 'state-space complexity' and
>'game-tree complexity' of the games:
>
>                    state, game
>
>  Awari               12    32
>  Checkers            21    31
>  Chess               46   123
>  Chinese Chess       48   150
>  Connect-Four        14    21
>  Dakon-6             15    33
>  Domineering (8x8)   15    27
>  Draughts            30    54
>  Go (19x19)         172   360
>  Go-Moku (15x15)    105    70
>  Hex (11x11)         57    98
>  Kalah (6, 4)        13    18
>  Nine Men's Morris   10    50
>  Othello             28    58
>  Pentominoes         12    18
>  Qubic               30    34
>  Renju (15x15)      105    70
>  Shogi               71   226
>
>As the counter-example of Nim shows, these figures are not necessarily
>correlated with the difficulty of solving the game or writing a program.
>
>But the survey is perhaps the most comprehensive done cross game-domains so far:
>
>Artificial Intelligence, v134 (2002) p. 277-311.
>
>Reprinted in "Chips Challenging Champions", Elsevier (2002),
>(eds. J. Schaeffer and J. van den Herik)
>ISBN 0-444-50949-6

Re: Let's add 3x3 and 4x4x4 Tic Tac Toe; both are solved Russell Reagan 21:28:21 12/11/02
- Re: Let's add 3x3 and 4x4x4 Tic Tac Toe; both are solved Jonathan Lee 03:44:45 12/12/02
  - Re: Let's add 3x3 and 4x4x4 Tic Tac Toe; both are solved Matthew White 18:05:25 12/12/02
  - Re: Let's add 3x3 and 4x4x4 Tic Tac Toe; both are solved Jonathan Lee 04:14:36 12/12/02
    - Re: Let's add 3x3 and 4x4x4 Tic Tac Toe; both are solved Daniel Clausen 04:43:53 12/12/02
      - Re: Let's add 3x3 and 4x4x4 Tic Tac Toe; both are solved Jonathan Lee 10:01:28 12/12/02
        
        Re: Let's add 3x3 and 4x4x4 Tic Tac Toe; both are solved Daniel Clausen 10:04:09 12/12/02
        
        Re: Let's add 3x3 and 4x4x4 Tic Tac Toe; both are solved Uri Blass 10:09:02 12/12/02
        
        Re: Let's add 3x3 and 4x4x4 Tic Tac Toe; both are solved Russell Reagan 12:21:16 12/12/02
        
        Re: Let's add 3x3 and 4x4x4 Tic Tac Toe; both are solved Uri Blass 13:49:02 12/12/02
        
        Re: Let's add 3x3 and 4x4x4 Tic Tac Toe; both are solved Daniel Clausen 11:16:38 12/12/02

This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.