From: torbenm@diku.dk (Torben AEgidius Mogensen)
Newsgroups: rec.games.go,rec.games.board,rec.games.chess
Subject: Re: Complexity - Ideas
Keywords: Complexity of strategic games
Date: 7 Sep 92 11:37:27 GMT
Organization: Department of Computer Science, U of Copenhagen

hpk@prim.han.de (Holger Krekel) writes:

>After a reading a lot of oppinions about the Complexity of Strategic games
>I would like to make some notes and attempt to put up a model
>which allows further discussions about the complexity of games. 

>Many articles talked about the Complexity of strategic games by examining
>the number of positions or the number of possible moves. Others
>suggested that rules has to be taken into account. Everybody would
>agree.

>So what should that new measurement be?

> We would then have an idea of how much 
>information a position has. We could invent a protocol which allows
>us to get an idea of the amount of information a special position has:

> -- Someone plays the role of the sender (say S)
> -- Someone plays the role of the recipient (say R) 
>   (about the same strength as S)
>  LOOP:      -- the sender transmits some >Infocs< to the recipient. 
>             -- the recipient asks  for more >Infocs< to get a more
>                complete idea of the position
>             -- return to LOOP as long as the position is not (nearly)
>                identical
> -- Count the number of >Infocs< needed and the number of questions and 
>    compute somehow the amount of information out of these questions.    


>What is the intention of the model so far? If we look at ourselfes
>we (should) agree, that the more (structured) Information we get from 
>the world the more complex it seems to us. And if we get enough information
>(or should we call it  >Infocs< too?) of the world and can handle this 
>information (which means in an abstract way 'just' information processing)  
>we are able to act, and if we do it accurately we are able to survive. 


>Combining this model to the above ideas and applying it to the 
>World of Chess, GO or Bridge one could come to the following 
>definition of Complexity of a Game. The complexity of a game mainly
>depends on the amount of >Infocs< needed to make a very good move.  
>So Complexity means something like on how many >Infocs< the possibilities
>to make a move depend on and how many possibilities there are. Once we 
>have the >Infocs< and their influence on the decisions, we should be able 
>to formalize the whole thing and write a good program, which should 
>be able to survive against other good >Infocs<-processers. 

[various parts deleted]

The number of >Infocs< you would need depends also on how many
different >Infocs< you have. If you can use a lot of different names
for different opening games (e.g Sicilian opening), you can reduce the
needed number of >Infocs< to describe the position/game. A more
neutral measurement (and more information theoretical) would be to see
how few bits were needed to describe a position or game.

In Chess the position can either be descibed as the position of each
piece as a square number or "off board" or by listing the moves
required from the initial position to reach the present prosition.

The first has roughly 65^32 ~ 10^ 58 possibilities (65 possible places
of 32) pieces. Not all of these are possible though (pawns can't go
backwards, bishops can only be at one colour etc). A rough estimate of
legal positions is 10^50.

Each move can be represented as a piece (16 possibilities) and a
destination square (64 possibilities). N moves thus gives N^(16*64)
possibilities (which already for N=2 gives more than 10^300). This is
also too much, as no piece can reach all squares. Assuming maximum
mobility for each piece, a pawn can move to 4 places, a rook to 14, a
bishop to 13, a knight to 8, a queen to 27 and a king to 8 places.
This gives 8*4+2*14+2*13+2*8+27+8 = 137 possible moves. In any given
position most of these are not possible, so a rough estimate limits
this to 50 possible moves. So N moves is gives a maximum of N^50
possibilities. For N=20 this gives 10^65 posibilities.

Probably, positions close to the beginning of the game are most
efficiently described by the moves leading to it, but later positions
by the positions of the pieces.

Your suggestion seem to indicate that you are only interested in
representing "interesting" games (that is, games played by competent
players). In this case we can limit the number of moves at a given
position to a few "reasonable" moves, possibly in the order of 4-6 on
average. This gives roughly N^5 posibilities for N moves, or less than
10^7 for 20 moves. This is so compact that this for almost any
position would be most efficiently represented by the moves leading to
it.

But how do we agree on numbering the "reasonable" moves? A suggestion
is to agree on a fixed evaluation function (from a good chess program)
and sort the moves according to the score from that function (highest
to lowest). Since numbers can be coded such that small numbers take
less space than big numbers and the reasonable moves would tend to get
good scores, we can expect an average of around 3-4 bits per move, or
less than 200 bits for a 50 move game. This gives chess a relatively
low complexity. The 10^50 positions requires 166 bits, which is
roughly the same.

Going to Go, we can describe a position by 3 posibilities for each
grid position (black, white or empty). This gives 3^(19*19) ~ 10^172
possible positions. Not all of these are legal (groups with no
freedoms), so the number of legal positions are somewhat less, say
10^170. Looking at the number of "reasonable" moves we have a much
higher number than in chess. Not being an expert, I would guess 15-20
on average in the beginning falling to 5-10 in the endgame. Let's say
15 on average. A game also has more moves than a chess game (~ 300),
so this would give about 5-6 bits per move for 300 moves = 1650 bits.
The 10^170 positions require 571 bits. Both these measures would give
Go a much higher complexity than Chess.

These kinds of measures overlook several important factors of game
complexity: How "obvious" are the good moves and how bad is the
consequence of playing a single bad move at one point?

An examples of a game with obvious moves (in the sense of being easily
calculated) is Nim. You have a set of rows of matches. The players
alternately pick a number of matches from a row. The player to pick
the last match loses the game. In some variants you can pick your
matches from the middle of a row, effectively splitting the remaining
matches into two rows. Given a sufficient large game, the number of
positions is quite large (especially with the split rule) and the
number of resonable moves is large (either one of several winning
moves or any move at all, since you can't win). This gives the game a
reasonably high complexity score, but it is fairly easy to program a
strategy that wins if a win is at all possible. This doesn't even
require very much calculation.

Games with low consequences of occasional bad moves are games where
you sum over a large number of unrelated occurences, e.g. playing a
series of short games and adding the scores. Some games has similar
effects built into a single play.

Chess and Go do not (obviously) fall into either category, so their
complexity measures are reasonable.

Another important complexity factor is how long it can take before the
consequences of a bad move becomes apparent. A property like this
makes playing by look-ahead difficult. In Go the consequence can show
up many moves after a bad move.

	Torben Mogensen (torbenm@diku.dk)
Newsgroups: rec.games.go