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