Monday, December 20, 2010

Rin - an abstract strategy game

Update: A reference implementation of Rin is now available online.
Update: Rules are rewritten to clarify certain points. Thanks to Wei-Hwa Huang for reviewing the draft.
Update: Omar Syed has written and kindly released a zillions-of-games rule file for Rin.
Update: Rin is entered in the Thousand-Year Game Design Challenge.
Update: Rin on BoardGameGeek.

Rin (as known as 环棋, 環棋, リング ゲーム) is a two-player abstract strategy game played on a 16×16 grid with 256 intersection points.

fig. 0 - A Rin board.
fig. 0 - A Rin board.

The two players are conventionally called Black and White; each player has an unlimited number of playing stones in his color.

Players take turns placing their own stones on the board and surrounding territory with rings. The object of the game is to have the most territory (and hence most stones) on the board when the board is full.

Black takes the first turn of the game. From then on, each player takes two turns in succession before the other player moves; hence, the turn order is B-W-W-B-B-W-W-B-B-..., etc.

Each turn consists of two steps:
1. The player puts one stone of his own color on any unoccupied intersection point.
2. The player fills in any ring that he has just made (explained below).

fig. 1 - An example of opening moves.
fig. 1 - An example of opening moves.

The set of 60 intersection points along the four edges of the board (including the four corners) is called the safe zone. A stone that can trace a path along grid lines to the safe zone, only going through empty intersection points or stones of its own color, is alive. Any stone in the safe zone or connected to the safe zone through just stones of its own color is not only alive, but immune; non-immune stones can potentially be captured by the opponent.

fig. 2 - An example of a corner situation.
fig. 2 - An example of a corner situation where all stones are alive.
A, B, E, I are all situated in the safe zone (and therefore immune) while G, J, K, N can reach the safe zone via G-C, J-F-G-C, K-L-H-D/K-O-N-M, and N-M, respectively.

A player makes a ring when he creates a group of stones that surround at least one vacant point or an enemy stone, in such a way so that any enemy stones in the ring are no longer alive. All enclosed enemy stones, if any, are immediately killed and removed from the board; then all points inside the ring are immediately filled by stones of the same color as the ring.

fig. 3 - An example of a black ring.
fig. 3 - An example of a black ring.
In the previous example, if it's Black's turn to play, Black can place two stones at L and O to form a ring G-J-O-L that surrounds the white stone at K, which is immediately killed and replaced by a black stone.

fig. 4 - An example of a white ring.
fig. 4 - An example of a white ring.
In the same example, if it's White's turn to play, White can place two stones at C and H to form a large ring, B-C-H-K-N-I-E, that fully encloses the vacant point F plus two black stones at G and J, all of which are immediately taken by White.

The game ends when the entire board is filled. At that point, the winner is the player who has the most stones on the board. A Rin game may also end in a draw if each player controls 128 points.

Additional notes

  • Point coordinates consist of a row number (increasing from top to bottom) and a column number (increasing from left to right), both zero-based. The top left corner is therefore (0, 0).
  • Eight points with strategic implications are marked with a small dot on the board: (3, 6), (3, 9), (6, 12), (9, 12), (12, 9), (12, 6), (9, 3), (6, 3). Markers do not affect the gameplay.
  • Passing is not allowed (and not useful anyway).
  • Rin was designed by Zhen Wang in 2010.

The text and images of this page are available for modification and reuse under the terms of the Creative Commons Attribution-Sharealike 3.0 Unported License.

Thursday, November 25, 2010

What I learned from building on AppEngine

WordGap is an anagram search tool for Scrabble players. I built it over two weekends as a coding exercise to learn more about Python and Google AppEngine. I was aware of AppEngine's many limitations before designing the simple web app, yet I soon got bitten by a few undocumented quirks.

IOError: [Errno 24] Too many open files (the local server for development) leaks file handlers and throws an IO exception "too many open files" once a few thousand entities are written to the local datastore. This seems to be a regression bug, which will hopefully get fixed in the next SDK release. What really surprised me is that dev_appserver rewrites the entire datastore file every time db.put() is called.

How not to store 178,000 words in Datastore

WordGap needs to quickly search anagrams from 178,000+ words in TWL. It seemed reasonable to me to dump the word list into the datastore. So I wrote an incremental datastore initialization script that stores a thousand words at a time to work around AppEngine's 30-second request deadline. It took me almost 40 minutes to construct the datastore in production, using up 2.55 CPU hours (39% of free daily quota). I churned out another 2.97 CPU hours in 45 minutes to update the database schema, during which time I realized the rudimentary capabilities of AppEngine's query engine, which essentially support inequality operators only, are inadequate to fulfill WordGap's search needs — WordGap should be able to find words comprised of letters from a given set of letters, including blank tiles (wildcard letters), preferably under 500 milliseconds. I can't think of an efficient datastore query without creating an astronomical amount of index.

How not to store 178,000 words in memory

It then occurred to me that I could simply keep all the data in memory. With pre-calculated bitmasks, the whole database is well under 5MB without any compression. AppEngine is surely capable of handling that, right? Well, not if you store all words in a Python dictionary with 178,000+ keys like I tried initially. That works flawlessly on the local dev_appserver but totally chokes AppEngine in production with this error message: "Exceeded soft memory limit with 299.965 MB after servicing 1 requests total". Apparently Python's dictionary/hashmap implementation has a huge memory overhead. I eventually converted the database to two sorted lists to keep the average memory consumption under 40MB and achieve an average request latency of ~200ms. The initial request could be twice as slow, though, because AppEngine needs extra time to warm up an app instance. It happens pretty frequently to low traffic apps like WordGap.

All that said, I'm still quite pleased with AppEngine overall. Deployment and maintenance just can't be simpler. It's an awesome rapid web application development tool if you're fully aware of its limitations.

Thursday, October 14, 2010

Printable Havannah Boards

I'm sure someone has done this before, but I couldn't find any high-resolution Havannah boards online, so I whipped up some DSC-compliant PostScript to draw seven printable Havannah boards (from base-4 up to base-10 in one PDF file).

In case you haven't heard of Havannah and didn't bother to read the Wikipedia article, it's the name of an awesome abstract board game invented by Christian Freeling. Havannah combines some elements of Hex and TwixT, with a delicate taste of Go. Under its simple rules lies a rich repertoire of strategies and tactics that fascinates me.