[computer-go] A thought about Bot-server communications

[Don Dailey]

I forgot mention why FEN is flawed.   It's because it fails to capture
the complete state of the game.   It records en-passant information and
color to move,   but it's does not capture position history so you
cannot detect draws due to positional repetition.

In GO, this is probably a more serious problem. 

- Don


Don Dailey wrote:
> Nick Wedd wrote:
>   
>> When I play Go on a Go server, I do not try to remember the board
>> position.  I can always find out what it is by looking at the client
>> window on my screen.
>>
>> When a bot plays on a Go server, it does remember the position. This
>> is something that programs are good at, so it seems reasonable to
>> require them to do it.
>>
>> But there can be, very rarely, circumstances where a bot would like to
>> ask the server "what is the current board position?".  Here are some
>> examples.
>>     (1)  My bot's opponent has just made a suicide move.  My bot does
>> not realise that, under the ruleset we are using, suicide is
>> permitted. Therefore its board-update routine fails.  It knows that
>> its opponent has moved, and it knows that it does not know the current
>> position.  It would like to ask the server to send the current position.
>>     (2)  As (1), but with a move that my bot thinks, wrongly, is
>> forbidden by superko.
>>     (3)  My bot, or the platform on which it is running, has had a
>> serious accident.  I have relaunched my bot and it wants to resume its
>> game but has no knowledge of the position.
>>
>> If my understanding of the GTP spec at
>> http://www.lysator.liu.se/~gunnar/gtp/gtp2-spec-draft2/gtp2-spec.html
>> is correct, it is not possible for a bot to say "please tell me the
>> position".  Should it be possible?
>>
>>     
> Hi Nick,  
>
> Of course with GTP the engine can never take the initiative to
> communicate with a controller due to the asynchronous nature of GTP.   
> This keeps things simple but has some drawbacks.
>
> UCI  deals with this by always sending the position.   A UCI program
> does not need to track the state of the game since the controller does
> it.   For example UCI sends the whole game via a list of moves before it
> gives the command to search a position.       But even a UCI-like go
> protocol wouldn't solve the issue you are talking about unless the rule
> was to accept any kind of KO or suicide as a legal move for purposes of
> setting up board state.      I think UCI also has a setup mode.  
>
> I don't know how you would make a GTP compatible command because of the
> asynchronous nature of GTP other than having it be initiated by the
> controller.     I suggest that such a command should send a list of
> moves (not a board image) because you can construct a proper board state
> from a list of moves for any rule-set - but you cannot do this with a
> board image. 
>
> In computer chess there is a standard way to record a board position,
> but it is flawed.   It's still very useful and heavily used.    The same
> format could be used for GO with the same exact drawback.   In chess it
> looks like this:
>
>          r2q1rk1/p3b1pp/2p5/1pn5/1n1Bp1b1/1P6/PQ1PPP2/2RNKBNR b K -
>
> If we did this for GO,  the opening position in 9x9 go might be
> represented like this:
>
>      9/9/9/9/9/9/9/9/9 b -
>
> The hyphen at the end would be ko point - it might be 'e5' if it is now
> illegal to capture e5 due to simple ko,  otherwise it is a hyphen
> placeholder.    This represents black to move from the opening position
> with no simply ko capture possible.
>
> Digits represent sequences of empty intersections and we scan them 1 row
> at a time starting with the A9-J9 row (the top row in a digram view.)  
> Slashes separate rows but this is not technically needed if we want to
> save a few bytes (but it makes it more readable.)
>
> On 19x19 boards we have a problem because we cannot represent 19 empty
> spaces with a single digit character.   Even if we use hex digits we are
> limited to 15 distinct digits or 16 if we change the meaning of
> zero.      Even if we use hex digits we have to decide what represents
> white and black stones.     We can of course extend the hex system with
> additional letters.  Or we can ignore the problem and use 2 digits to
> make up the difference.    If we do that,  I suggest the 0 digit is used
> to extend the alphabet and it simply means 10.  If there are 10 or more
> we insist on using 0 first, then an addition digit  just to be
> consistent.     So the opening position in 19x19 might look like this:
>
>   09/09/09/09/09/09/09/09/09/09/09/09/09/09/09/09/09/09/09 b -
>
> Although 2 digits is wasteful, much of this goes away once the positions
> become complicated.
>
> The next issue is how to represent stones.  In chess white pieces are
> represented with upper-case characters and black pieces are represented
> with lower case letters.    If we follow that conventions we might pick
> an arbitrary letter of the alphabet to represent a stone and use
> upper/lower case to determine - or we could just choose "w" and "b" to
> mean white/black stone.   I prefer "w" and "b".
>
> You might think positions look a little cryptic with this notation,  but
> in my opinion the real value of fen notation is that you can physically
> type in a board position in just seconds.   In chess, you basically scan
> the board and type the piece and digits as you scan.  If there are 3
> empty squares you just type 3 and you are done.  
>
> In fact, this whole notation is based on what was done way before
> computers came along to quickly record chess positions on paper when
> games are adjourned.    It was invented by David Forsyth and it was
> called not suprisingly "Forsyth notation."    FEN notation is short for
> "Forsyth Edwards Notation" because Steven Edwards modifed it slightly
> for computer notation.   You can record a chess position on paper in
> about 10-15 seconds and by keyboard using FEN notation in about 5
> seconds.  
>
> The question comes up:  Is it really practical for go?     I cannot
> answer that.   In the old days before computers, were games adjourned
> and restarted at later times?   How was the position preserved?  Did
> someone draw a diagram on a piece of paper?    Or did they just replay
> the game?  
>
> Although even in chess we use graphical tools now to set up positions, 
> it's still much faster to create a fen diagram with a text editor.  
> This is for the same reason that "real programmers" are command line
> junkies - command line interface is almost always the better and faster
> way to do things that do not directly involve graphics or complex
> interactions where visual cues make a lot of difference.   Admittedly, 
> it would be more error prone with GO as the board is bigger and more
> complicated and you can see at a glance how many empty squares there are
> on a chess board without barely a thought but it's not quite as trivial
> in Go.     It's still probably faster using something like FEN in GO,  
> but I think creating positions manually in GO is done far less often
> simply because it's more painful no matter how you do it.   
>
> Before I go too much farther - is there already a commonly accepted
> simple and user friendly way to actually record a board position on
> paper that is roughly equivalent to FEN?
>
> FEN has similar characteristics to RLE (run length encoding) where
> sequences of the same "digits" are stored as a single data value with a
> count.   It's much more common in GO to have long sequences of the same
> piece type (several white or black stones on the same row.)  So we could
> encode a position in a very straightforward way with a different scheme
> - there are 3 kinds of intersections in GO,  white/black/empty.    So we
> could encode the type and count in pairs perhaps in the same scan order
> as in FEN.    For readability we should probably stop at the end of each
> row and thus have something like this:
>
>  
> e2bweweb3/b4w2beb/ew2b2w2b2/e2bebw2be/b4w3be/w2bwewb2e/wewew3be/ew2e2wb2e/e5w2be
> b -
>
> I typed this in from one of the 9x9 cgos games and it went pretty fast -
> and would be very fast with some practice.    Here is how it works:
>
>     e - empty
>     b - black stone
>     w - white stone
>
> For each row,  I type in the type and number of them.    If there is
> only 1, I ignore the count.   If you ignore the slash separator between
> rows, this is guaranteed to be at least as compact as if you layed them
> out 1 character at a time.   
>
> You could of course ignore the separate line separates and get very high
> compression ratio's in some types of positions.     the opening 19x19
> board would look like this:     
>
>        "e381 b -"
>
>
> Of course you could take such a representation and apply huffman
> encoding and such - but it would be interesting to find a very
> compressible system that only required the use of ascii printable
> symbols and was not unduly difficult to decode and encode.    
>
> Of course I have not researched this - perhaps such things have already
> been discussed or even created.
>       
>
>
> - Don
>
>
>
>
>   
>> A similar question applies to time.  When I play in a tournament, I am
>> allowed to look at my clock to find out how much time I have left.  I
>> am surprised to find that GTP provides no way for a bot to ask this.
>> (Maybe I am misunderstanding the spec.  I see that there are commands
>> 'time_settings' and 'time-left' that the server can use to inform the
>> bot of its remaining time, but I can find no indication of when, if
>> ever, these commands will be issued.)
>>
>> Nick
>>     
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
>