GlyphChess

What is GlyphChess?

GlyphChess on the Desktop

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
    assembled piece
  2. The pieces template is a DataGlyph address carpet.

    pieces template



    The board template is also a DataGlyph address carpet.

    board template

  3. 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 GlyphChess on a Xerox DocuCenter 440
    This consumer grade scanner would be nearly ideal for GlyphChess if it wasn't so excruciatingly slow. CanoScan LiDE 30
  4. 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
    GlyphChess scan    GlyphChess detail
  5. 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
    automatic glyph detection
  6. 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
    desktop scanner registration image
    test pattern
    photocopier platen
    photocopier registration image
  7. 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.

    noisy registration image
  8. 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.

    GlyphTone

    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.

    imagelogical values
    piece     
    ...11111111101010...
    ..1101010101000000..
    .100101010100000000.
    10111111111110101110
    01011111111101010111
    10111111111110101111
    00001010101000000010
    10111111111110101111
    00001010101000000010
    00010101010100000101
    01011111111101010111
    00010101010100000101
    00001010101000000010
    10111111111110101111
    01011111111101010111
    0011111111111010111.
    .00111111111010101..
    ..0101010101000001..
    ...01111111101011...
    		  
  9. 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
    xboard chess GUI

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.


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