GlyphChess

What is GlyphChess?

A chess game with real wooden pieces is placed on top of a scanner or photocopier platen. At any point during the game, one may scan the board position and feed it into a computer chess engine for analysis. GlyphChess tests and exercises the address carpet features of the DataGlyph Toolkit. [homepage] [faq]

How does GlyphChess work?

1. Construct a GlyphChess set. The board is laser printed onto a transparency. The DataGlyphs for pieces are similarly printed onto paper, and then transferred to the bottom of the wooden chess pieces with good old fashioned scissors and gluestick.
   

   GlyphChess pieces

The pieces template is a DataGlyph address carpet.





The board template is also a DataGlyph address carpet.



2. Scan the board, capturing an image of the chess game. The exact resolution and characteristics of the scanner don't really matter, it just has to be of high enough quality that we can successfully make out the DataGlyphs.
   

   Xerox DocumentCentre 440 plays a mean game of GlyphChess

   This consumer grade scanner would be nearly ideal for GlyphChess if it wasn't so excruciatingly slow.

3. Once the image is captured, we send it to a computer running custom software for processing. An example scanned image is shown below.

   scan	detail

4. A DataGlyph at the bottom of the board functions as a registration pattern. Locate its position using the DataGlyph detection functions from the toolkit. A white paper is glued to the top of the transparency so that the registration pattern appears as black marks against a white background.

   automatic glyph detection

5. Register the board. The black squares on the board are for the human players only, the GlyphChess software extrapolates all square positions solely from the registration pattern. Take all the points from the registration pattern and use them to determine the rotation, scaling, skew, etc. of the scanned image. The address carpet gives us lots of points from glyph coordinate system in (u,v) and their corresponding pixel positions in the (x,y) coordinate system. We solve for the affine transform with a least square error fit for a,b,c,d,e,f. This does a pretty good job, although a little bit of error begins to creep in as we extrapolate further and further away from the registration DataGlyph.
   x = au + bv + c
y = du + ev + f
   

   test pattern desktop scanner
   test pattern photocopier platen

The computer can find squares even in the presence of noise. This board is covered with extraneous objects, to the point where the computer has a much easier time reading out the board positions than the human.


6. Look for DataGlyphs in all the squares. If there is a DataGlyph, decode it. The first step in decoding is to locate the glyphmarks. In the picture below, the red dots indicate where the imaging layer has detected glyphmarks. Click on the image to see the entire board.

   
   
   

   The second step in decoding is to turn those marks into logical ones and zeros, and decode those logical values into a location in the address carpet. From the address carpet location, we can determine which chess piece is present.

   image	logical values
   	...11111111101010... ..1101010101000000.. .100101010100000000. 10111111111110101110 01011111111101010111 10111111111110101111 00001010101000000010 10111111111110101111 00001010101000000010 00010101010100000101 01011111111101010111 00010101010100000101 00001010101000000010 10111111111110101111 01011111111101010111 0011111111111010111. .00111111111010101.. ..0101010101000001.. ...01111111101011...

7. Write out the board state in FEN notation, which is a simple chess notation to describe board positions. FEN notation is understood by a number of computer chess programs. We use the crafty chess engine with the xboard graphical user interface. Other chess engines such as GNU Chess work as well.

   FEN Notation
   11111111/111111r1/11111111/11111111/11bN1B11/1p111R11/p11K1111/k1111111 w - - 0 1

   corresponding board position

Why

Like many fun hacks, GlyphChess has paid off in unexpected ways. First, testing DataGlyph software and algorithm changes is a lot more engaging. It is hard to get excited about 99.98% vs. 99.97% decode rates in testsuite #73, but if a rook disappears, well that is simply unacceptable! We've found GlyphChess an excellent diagnostic and quality assurance motivator that inspires rapid bug hunting and closure. Second, it turns out some of the software technology refined for GlyphChess is applicable to more boring, but commercially important domains. Finally, GlyphChess is a compelling demonstration vehicle for DataGlyph Toolkit technical capabilities, including our DataGlyph location routines, our ability to decode arbitrarily rotated DataGlyphs, and our very high tolerance of variation in scan resolutions and positioning. GlyphChess works and it works well.

We also gained valuable experience about DataGlyph application building.

Acknowledgements

I thank the Desert Punks ice hockey team for helping me obtain copious amounts of spare time. Tom Breuel for suggesting I rewrite GlyphChess as single C program, even though I think he was being sarcastic. Bryan Pendelton and Amanda Williams for photography expertise. PARC's Advanced System Development Laboratory for mostly being on vacation between Christmas and New Years. Xerox Corporation for funding the DataGlyph Toolkit and providing a plethora of scanning hardware. My boss Ruth Rosenholtz for listing GlyphChess on our monthly report.

Jeff Breidenbach, jbreiden <at> parc.com Last modified: Thu Jan 16 13:37:31 PST 2003