Use Cute Chess variant to play gomoku

[nkg114mc]

Hi all,

No sure it is a valid topic for the forum (let me know if it is not, and I will remove this post). Computer gomoku (also known as "five-in-a-row") has be developing fast in the past years. But there is no such a tool like Cute Chess for computer gomoku, especially cutechess-cli which allows users to run large scale engine-to-engine matches across all popular OS platforms. I once have an idea to modify the Cute Chess to get such a tool. Since Cute Chess support variant chess games, probably we can add another "variant" and turns it to a gomoku game.

After working for a few days, I have got a very naive but working version. By specifying the "variant" gomoku, one can play engine-to-engine games with Cute Chess now. There are several key differences between gomoku and chess game:
1) Computer gomoku allows to play on variant size of boards, from 5x5 to 24x24. So for cli I add a "-boardSize" option to support this.
2) Computer gomoku engines use Gomocup protocol.
3) The PGN format might not work for gomoku games, since the move format are different.

At the beginning, my main goal is just developing a cli tool. I did not even expect that Cute Chess GUI would still work. But surprisingly it does. However, because all the graphical resources are for chess, it makes the displayed board and pieces look very wired: it shows a gomoku game with chess pieces and a larger chess board :


After replacing the board and pieces with the gomoku graphical resource downloaded from wiki, it looks much better:

Currently the GUI does not support human player for gomoku. You can only launch an engine-to-engine game or tournament.

So far it is still incomplete. One of key functionality is still missing: opening suite. Without open suite support, the user can not play large scale tournaments, since there will be a lot of repeat games. But it is still a question that what's the best file format for gomoku games. SGF might be a good choice, but I am not sure.

Thanks for all the developers of Cute Chess to create such an excellent tool. I name the new project "Cute Gomoku", but you can still use it to play chess at this moment. Github repo: https://github.com/nkg114mc/cutegomoku

[hgm]

I would think that most Chess GUIs that support variants would allow you to play Gomoku; it is just a game with piece drops, where you start with all pieces in hand. There are no side effects to the moves (as there would be in Go, where stones would disappear when surrounded). I don't think WinBoard/Xboard would have any problem playing it. The WinBoard Alien edition even supports a 'variant go', which implements capture by surrounding.

I also see no reason why Polyglot books would not work for Gomoku. My mini-Shogi engine uses a book in Polyglot format, and there are many drop moves in the opening there.

[nkg114mc]

I would think that most Chess GUIs that support variants would allow you to play Gomoku; it is just a game with piece drops, where you start with all pieces in hand. There are no side effects to the moves (as there would be in Go, where stones would disappear when surrounded). I don't think WinBoard/Xboard would have any problem playing it. The WinBoard Alien edition even supports a 'variant go', which implements capture by surrounding.

I also see no reason why Polyglot books would not work for Gomoku. My mini-Shogi engine uses a book in Polyglot format, and there are many drop moves in the opening there.

Thank you for the reply, Mr. Muller! I did not fully understand the concept of "drop pieces" at the beginning. If that's the case as you mentioned, then yes, looks like variant chess can take care of everything that gomoku needs. It would make things even better because we can apply the chess engine protocol rather than just Gomocup protocol. Winboard Alien edition is good resource for me to study.

For the book format, Polyglot is definitely a choice. In fact, even PGN is a choice if we have a better move string format (Gomocup move string contains two numbers separated by ",") that allows the PGN parse to recognize the move (and if PGN support chess variant, I feel that it is not problem any more). The key of this issue is not about which format works, it is about which format works most widely in computer gomoku community. So I guess it is more than a technical question, but a question about what standard to follow (which requires the computer gomoku programmers to figure out), I think.

[hgm]

Dropping pieces is putting them from a reservaoir (know as 'the hand' or 'holdings') onto the board. Usually captured pieces get into the hand of their capturer, in games like Shogi or Crazyhouse.

I didn't know Gomoku at all, and was a bit puzzled you needed 4 coordinates to describe a turn. But I am starting to suspect now that this is because a turn actually consists of a pair of drops. This is indeed a deviation from what you have in typical chess variants, where a turn consist either of a single drop or a single board move.

The WinBoard Alien edition can handle games with 'multi-leg moves', though; you can suppress turn change there by playing the move with Ctrl pressed, and can then do two drops in a row. I don't think this would work for the book moves, though; it would not probe the book after a partial turn, to get a move for the remaining 'leg'. So it would need to get the pair of moves from the book probe at the start of the turn, which would require the book in the Gomoku case to store pairs of moves. This is not standard. Polyglot format does use 16 bits for encoding the move, so in principle you could encode a pair of drops on boards up to 19x19 with that. The alternative is to implement book probing also after a partial move, and only put partial moves into the book.

Normally WinBoard would use a P@sq notation for drops, where P is the ID of the piece type, and sq the square coordinates as (lower-case) letter + number. The Alien edition makes an exception for this when only a single type participates in the game, and leaves out the 'P@' prefix in that case. So that the drop moves just become the square name. It would separate multiple drops that form one turn by commas.

[nkg114mc]

Thanks for the explanation about the drop pieces, Mr. Muller. I suspect that you are misled by the screenshot I took. If a "turn" means a move, then you only need 2 coordinates to describe a move, which is basically just the file and rank of square that the new stone was placed. This is exactly the same as go. You see 4 coordinates probably because Cute Chess display moves in the PGN format, where each line actually indicates a "round" including two moves.

I think the P@sq or just sq notation is a good idea rather than the pair of coordinates in my opinion, and that will makes the PGN format available for gomoku. So at least for gomoku we don't need to concern about the "multi-drop" issue. Polyglot book should have no problem either. It is still great to learn how the Winboard Alien handle this multi-drop moves in other games though

[hgm]

Ah, OK. Indeed I had not understood that CuteChess displays two turns on one line. If Gomoku is just single drop per turn, there doesn't seem to be any reason why the standard edition of WinBoard / XBoard should not be able to handle it too, and in particular be used to create or edit a Polyglot book. The standard binary distribution is compiled for a maximum board size of 16x16, though, and this might not be large enough for Gomoku, so it might have to be recompiled.

The standard move format in Polyglot books could also be unsuitable: Polyglot books encode the move in 16 bits, as toSquare + boardSize*fromSquare + boardSize*boardSize*promotionCode, where drop moves are indicated by a special promotionCode. For 16x16 boards the boardSize is 256, so that no room is left for promotion codes at all. (Fortunately promotion is very rare in opening lines, so even for 16x16 boards the format is still usable.)

In games with only drops is is of course enormously wasteful to reserve codes for indicating the fromSquare; all 16 bits could just be a single square number, so that you could handle boards up to 256x256. Even for other games with large boards the format is wasteful. E.g. Tai Shogi has a 25x25 board, so a (fromSqr, toSqr) representation would already require 19 bits. The use of 'polar coordinates' would be more efficient; the fromSquare could be indicated relative to the toSquare by an orientation (2 bits) and a location along the ray with that orientation, e.g. as toSquare + boardSize*orientation + 4*boardSize*rayLocation; that would run up to 60,000, so that more than 5000 codes would remain available for special moves (like Knight jumps and double captures). Drops could be indicated by just having a single extra code for what otherwise would indicate an (orientation, rayLocation) pair, i.e. you woud (for 25x25) need 4*24+1 of those instead of 4*24. If this was chosen to be the lowest number (i.e. encode drops as toSquare, and board moves as toSquare + boardSize*(orientation + 4*rayLocation + N), with N=1), games with only drops would automatically fit in a much smaller number of bits than what other games with the same board size would need. Tai Shogi has no piece drops, but it has Hook Movers and a Universal Leaper, which move in a way very similar to drops, for which the polar coordinates would fail. There only is a very limited number of those pieces, though, and I guess they could be handled by taking N larger, so that their moves will be encoded as toSquare + boardSize*k, where k indicates the piece.

I probably should switch the move-encoding/decoding algorithm WinBoard uses to this format, for boards above a certain size.