🚀 go-pugleaf

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. But as we don't know too much about an optimal algorithm for
most of the interesting strategic games we should try to put up some other
mesaurement for the complexity (which somehow influences the computational
cost one would suggest) of these games. 'Optimal algorithm' here means
optimal,  considering time and space of a digital computer.

So what should that new measurement be? First I would like to tell something
about an 'everyday-experience' of someone playing these games. When I played 
a lot of chess with friends and on tournaments we used to talk about
about our matches by describing what mainly happened on the board. The phrases
were something like ('played sicillian defense-Taimanow-variant',
'we rochaded to different sides, agressive play', 'sacrificed a rook near
his king', 'made a classical h7-bishop-sacrifice', 'very positional game',
'highly tactical' ...). Sometimes we just put up the local position to
show where the mistake was. 

So it seems, that by these pieces of information we are able to tell someone 
about the rough character of a match of chess. One condition is, that 
the one who says something about a match should not be too much better 
than the recipient, because he would not understand very well. 

As you may have noticed I called the phrases pieces of information, I could
also call them symbols or (quite abstract) patterns, describing some
abstract structure of a match. Now the question seems to be, how many
of these symbols, or lets call them >Infocs< for now, are needed to
describe a match accurately? The next question is, of course, what does
it mean 'accurately'? I am doing no exact mathematics now so I don't want to
discuss this questions to the (probably not existing) end. Just my 
oppinion: The recipient of the flow of information should be able to
reconstruct the match in a way, that others would say they are talking about
(nearly) the same match. 

By the way, one could also reduce the model by talking about positions
rather than whole matches. 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  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. 


One last thing I would like to contribute to the discussion about what is the
more complex game, Go or Chess. I am playing II. Dan in GO and
ca. ELO 2000 in Chess and I suppose that the Complexity according to the
above definition of GO is higher than the one of Chess or Bridge.
For if I try to explain an other Dan-player of how my match has been,
I would have to talk a long time to give him a accurately good impression
of the match. Not so in chess.

Last I would like to hear some ideas about other words for >Infocs<, as
I think there are a lot of possibilities (I heart of 'chunks' a time go).

I think the model presented is not very precise, as I have not tried
to put up a mathematical model so far. But hopefully it is enough to
give an impression of my point of view to the Complexity-theme.

Holger P. Krekel , University of Hildesheim, Germany


-- 
Holger P. Krekel        vox +49 511 818993                    hpk@prim.han.de
Uni Hildesheim		krekel@informatik.uni-hildesheim.de