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
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
