TITLE: The Beginning of a New Project
AUTHOR: Eugene Wallingford
DATE: September 01, 2010  9:12 PM
DESC: 
-----
BODY:
"Tell me you're not playing chess," my colleague said
quizzically.

But I was.  My newest grad student and I were sitting
in my office playing a quick couple of games of
<A HREF="http://en.wikipedia.org/wiki/Progressive_chess">
   progressive chess</A>,
in which I've long been interested.  In progressive
chess, white makes one move, then black makes two;
white makes three moves, then black makes four.  The
game proceeds in this fashion until one of the
players delivers checkmate or until the game ends in
any other traditional way.

This may seem like a relatively simple change to the
rules of the game, but the result is something that
almost doesn't feel like chess.  The values of the
pieces changes radically, as does the value of space
and the meaning of protection.  That's why we needed
to play a couple of games: to acquaint my student
with how different it is from the classical chess I
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2005-12.html#e2005-12-23T10_19_08.htm">
   know and love</A>
and which has played since a child.

For his master's project, the grad student wanted
to do something in the general area of game-playing
and AI, and we both wanted to work on a problem that
is relatively untouched, where a few cool discoveries
are still accessible to mortals.  Chess, the fruit
fly of AI from the 1950s into the 1970s, long ago
left the realm where newcomers could make much of a
contribution.  Chess isn't solved in the technical
sense, as
<A HREF="http://www.sciencemag.org/cgi/content/abstract/1144079">
   checkers is</A>,
but the best programs now outplay even the best
humans.  To improve on the state of the art requires
specialty hardware or exquisitely honed software.

Progressive chess, on the other hand, has a funky
feel to it and looks wide open.  We are not yet
aware of much work that has been done on it, either
in game theory or automation.  My student is just
beginning his search of the literature and will know
soon how much has been done and what problems have
been solved, if any.

That is why we were playing chess in my office on a
Wednesday afternoon, so that we could discuss some
of the ways in which we will have to think differently
about this problem as we explore solutions.
Static evaluation of positions is most assuredly
different from what works in classical chess, and I
suspect that the best ways to search the state space
will be quite different, too.  After playing only a
few games, my student proposed a new way to do search
to capitalize on progressive chess's increasingly
long sequences of moves by one player.  I'm looking
forward to exploring it further, giving it a try in
code, and finding other new ideas!

I may not be an
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2005-06.html#e2005-06-06T17_04_28.htm">
   AI researcher first</A>
any more, but this project excites me.  You never
know what you will discover until you wander away
from known territory, and this problem offers us a
lot of unknowns.

And I'll get to say, "Yes, we are playing chess,"
every once in a while, too.
-----