Chess for the Arduino

[chessplayer]

Greetings to all:

I am developing a chessplaying program for the Arduino.  The project is well underway (about 3,000 lines of C++) and should be completed in a month or so.  My plan is to release the source under the Creative Commons license so that others may extend the program with their own ideas.

The name of the program is "myopic" (i.e., shortsighted as it might not see all that human player would see).  It implements all the standard chess rules, although position repletion draws still need some work.  All move I/O is done with ASCII SAN (Standard Algebraic Notation).  Position I/O is done with FEN.  A somewhat lame 16x8 Ascii board output is also implemented.

All I/O is gated through a single pair of routines that currently use the default serial I/O pins; the idea is that it should be fun to develop alternative and additional means of communication using extra hardware (e.g., an LED array, a voice synthesizer, or a robotic arm).

The program uses a lot of RAM and requires an AVR with 8 KB SRAM memory, so it needs a Mega to run.  I regret that it won't operate with a 168 or 328, but my design target aims for playing strength and clarity of implementation -- and that means relatively lots of memory.  But I'm trying to leave a margin of around 2 KB for further expansion by others.

So, let's hear of some ideas for expansion.  Please feel free to post any thoughts you might have that would improve the project.

[chessplayer]

And here is some of the program's test output.  It is calculating movepath enumeration.  See http://www.research.att.com/~njas/sequences/A048987 for details.

Code: [Select]

myopic: Chess for the Arduino

MoveStackByteLen: 4096
MoveStackLen: 512
PlyLen: 32

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

bRbNbBbQbKbBbNbR
bPbPbPbPbPbPbPbP
 ::  ::  ::  ::
::  ::  ::  ::  
 ::  ::  ::  ::
::  ::  ::  ::  
wPwPwPwPwPwPwPwP
wRwNwBwQwKwBwNwR

w KQkq - 0 1

Depth: 0   Total: 1
Na3 1
Nc3 1
Nf3 1
Nh3 1
a3 1
a4 1
b3 1
b4 1
c3 1
c4 1
d3 1
d4 1
e3 1
e4 1
f3 1
f4 1
g3 1
g4 1
h3 1
h4 1
Depth: 1   Total: 20
Na3 20
Nc3 20
Nf3 20
Nh3 20
a3 20
a4 20
b3 20
b4 20
c3 20
c4 20
d3 20
d4 20
e3 20
e4 20
f3 20
f4 20
g3 20
g4 20
h3 20
h4 20
Depth: 2   Total: 400
Na3 400
Nc3 440
Nf3 440
Nh3 400
a3 380
a4 420
b3 420
b4 421
c3 420
c4 441
d3 539
d4 560
e3 599
e4 600
f3 380
f4 401
g3 420
g4 421
h3 380
h4 420
Depth: 3   Total: 8902
Na3 8885
Nc3 9755
Nf3 9748
Nh3 8881
a3 8457
a4 9329
b3 9345
b4 9332
c3 9272
c4 9744
d3 11959
d4 12435
e3 13134
e4 13160
f3 8457
f4 8929
g3 9345
g4 9328
h3 8457
h4 9329
Depth: 4   Total: 197281
Na3 198572
Nc3 234656
Nf3 233491
Nh3 198502
a3 181046
a4 217832
b3 215255
b4 216145
c3 222861
c4 240082
d3 328511
d4 361790
e3 402988
e4 405385
f3 178889
f4 198473
g3 217210
g4 214048
h3 181044
h4 218829
Depth: 5   Total: 4865609
Na3 4856835
Nc3 5708064
Nf3 5723523
Nh3 4877234
a3 4463267
a4 5363555
b3 5310358
b4 5293555
c3 5417640
c4 5866666
d3 8073082
d4 8879566
e3 9726018
e4 9771632
f3 4404141
f4 4890429
g3 5346260
g4 5239875
h3 4463070
h4 5385554
Depth: 6   Total: 119060324
Na3 120142144
Nc3 148527161
Nf3 147678554
Nh3 120669525
a3 106743106
a4 137077337
b3 133233975
b4 134087476
c3 144074944
c4 157756443
d3 227598692
d4 269605599
e3 306138410
e4 309478263
f3 102021008
f4 119614841
g3 135987651
g4 130293018
h3 106678423
h4 138495290
Depth: 7   Total: 3195901860


[chessplayer]

And here is the routine that does the recursive movepath counting:

Code: [Select]

ncType Pos::EMP(const plyType ply, const depthType depth, ML& prior)
{
 ncType nodecount;

 if (depth == 0) nodecount = 1;
 else
 {
   const plyType newply = ply + 1;
   const depthType newdepth = depth - 1;
   ML ml(prior);

   nodecount = 0;
   if (ply == 0) GenerateCanonical(ml); else GeneratePseudoLegal(ml);

   const mcType limit = ml.GetCount();

   for (mcType index = 0; index < limit; index++)
   {
     FEnv fenv;
     PEnv penv;
     ncType subsum;

     Execute(ml.FetchMove(index), fenv, penv);
     if (!EvilInCheck())
     {
       subsum = EMP(newply, newdepth, ml);
       if (ply == 0)
       {
         ml.FetchMove(index).Print(); PrintSpace();
         PrintUnsignedInt(subsum); PrintNL();
       };
       nodecount += subsum;
     };
     Retract(ml.FetchMove(index), fenv, penv);
   };
 };
 return nodecount;
}


[mowcius]

Woah!

Someone has a lot of time on their hands

I like it!

It is great that you will be releasing under CC

Keep me updated,

Mowcius

[chessplayer]

The program is actually rather simple; it is big only because it is made from a lot of small and simple parts, largely taken from some code I wrote back in the early 1990s.  More impressive are the chess programs written by some commercial authors that operate with only 256 bytes of RAM.  I might be able to write one of these, but again my aims are greater speed (and hence strength).

And now for a few expansion ideas:

1) The easiest thing someone might try is to connect some of board's output pins to a few LEDs and then in software tie each LED to one of the internal routines; turn on the LED when the routine is entered and turn it off when the routine exits.  With this, one has a real time display of the activities of the program as the relative brightness of the LEDs allows for a simple profiling.

2) A related idea would be to connect an analog output to a an amplifier that in turn drives a speaker; and then in software drive this from a collection of routines based on their calling frequency.  Perhaps different musical notes could be associated with different routines.  It might sound like the robot R2-D2!

3) Those handy 8x8 LED matrices are just begging to be used with a microcontroller chess program. The simplest idea is to take a monochromatic LED array and drive it in real time with each LED being illuminated if a piece is on the associated chessboard square in the analysis board.  Even better would be to use a multi-color LED array where the color would represent the color (say, red vs blue) of the corresponding piece on the board.  In either case, the display does not have to be updated many thousands of times per second; a 60 Hz interrupt is sufficient to eliminate any flicker.

4) A mostly software challenge could be to connect one Arduino to another and have a chess match.  Alternatively, connect one to the Internet to play all comers.

5) For those with a mechanical inclination and a sufficient budget, a robotic arm might be constructed that would move physical chessmen on a real chessboard.

[patrickmccabe]

well this is interesting considering what i am doing. I have already built, well im almost done, a chess robot. I am just starting some of the programming and then someone showed me this. I understand that is written in C and not arduino. We should talk more because i have the hardware almost complete and could maybe test your code.

[patrickmccabe]

here is the link to my chess robot that uses a arduino mega http://letsmakerobots.com/node/11007. I will update the robot in about a week or 2 because i made some big changes on how the pieces are read, it is now analog inputs and multiplexed.

[chessplayer]

It may be the case that due to limited SRAM capability, two Arduino boards will be needed for a robotic chessplaying system -- one for the chess program and one for the robot control.  My program is targeted towards an Arduino with 8 KB SRAM, although I'm trying to have about 2 KB SRAM reserve as a margin for future enhancements.

The program allows for a textual interface using the default Arduino serial circuit and the standard ASCII chess data standards.  This can be changed to also allow for simpler data exchanges like "move 4,1 to 4,3" and "move 6,7 to 5,5" instead of "1. e4" and "1? Nf6".

The program's SRAM usage is high relative to many other Arduino programs in part because it's using an eight byte chess move representation and it needs a move stack with hundreds of entries for speed and strength.  So that's 4 KB SRAM for a 512 entry move stack and reducing the move stack length would seriously limit the program's search depth capability.

[patrickmccabe]

im very much interested in the minimax program. This what i am going to use for chess strategy. It may very well be best for me to write my own code because i know how my robot is setup and  meant to work. Id love to see the minimax code, if you have it. I understand that you assign point value to moves. Then the program looks forward a few moves ahead and tries to do its favorable out come. Of course this is the hardest part of any chess program. The great thing about my robot is all pieces have their own analog value so we can easily read and find out what piece is what and where. But this last strategic end of the code is very interesting and lengthy, im sure you  know. I would love any help in code i could get from you and it would help me alot. So i may be on here a lot.

[chessplayer]

A good start: http://chessprogramming.wikispaces.com/

My program, just like many others, uses the negamax search framework.

From the wiki:

Code: [Select]

int alphaBeta( int alpha, int beta, int depthleft ) {
  if( depthleft == 0 ) return quiesce( alpha, beta );
  for ( all moves)  {
     score = -alphaBeta( -beta, -alpha, depthleft - 1 );
     if( score >= beta )
        return beta;   // beta cutoff
     if( score > alpha )
        alpha = score; // alpha acts like max in MiniMax
  }
  return alpha;
}


Of course, the devil is in the details as they say.  As an example, here are some of the details of myopic's C++ Move class:

Code: [Select]


// Move class

class Move: public Score
{
 public:
   sqrType GetFrSqr(void) const {return frsqr;}
   void PutFrSqr(const sqrType value) {frsqr = value;}
   sqrType GetToSqr(void) const {return tosqr;}
   void PutToSqr(const sqrType value) {tosqr = value;}
   manType GetFrMan(void) const {return frman;}
   void PutFrMan(const manType value) {frman = value;}
   manType GetToMan(void) const {return toman;}
   void PutToMan(const manType value) {toman = value;}
   mscType GetMsc(void) const {return msc;}
   void PutMsc(const mscType value) {msc = value;}
   ui8 GetFlags(void) const {return flags;}
   void PutFlags(const ui8 value) {flags = value;}

   void SetFlag(const mfType mf) {flags |= BX(mf);}
   bool TestFlag(const mfType mf) const {return flags & BX(mf);}

   void SetFlagM(const mfmType mfm) {flags |= mfm;}
   bool TestFlagM(const mfmType mfm) const {return flags & mfm;}

   bool IsBroken(void)        const {return TestFlagM(mfmBust);}
   bool IsCapture(void)       const {return IsSimpleCapture() || IsEnPassant();}
   bool IsCastling(void)      const {return (msc == mscCKS) || (msc == mscCQS);}
   bool IsCertain(void)       const {return TestFlagM(mfmCert);}
   bool IsCheck(void)         const {return TestFlagM(mfmChck);}
   bool IsCheckmate(void)     const {return TestFlagM(mfmMate);}
   bool IsDisamFile(void)     const {return TestFlagM(mfmAdaf);}
   bool IsDisamRank(void)     const {return TestFlagM(mfmAdar);}
   bool IsEnPassant(void)     const {return msc == mscEPC;}
   bool IsGainer(void)        const {return IsCapture() || IsPromotion();}
   bool IsHmvcReset(void)     const {return IsPawnMove() || IsCapture();}
   bool IsNull(void)          const {return TestFlagM(mfmNull);}
   bool IsPawnMove(void)      const {return IsManPawn(frman);}
   bool IsPromotion(void)     const {return msc >= mscPPN;}
   bool IsRegular(void)       const {return msc == mscReg;}
   bool IsSearched(void)      const {return TestFlagM(mfmSrch);}
   bool IsSimpleCapture(void) const {return IsManNotVacant(toman);}
   bool IsSpecial(void)       const {return msc != mscReg;}

   sqrType CalcEPVictimSqr(void) const;

   void MakeNull(void)
   {
     frsqr = tosqr = sqrA1; frman = toman = manVacant; msc = mscReg; flags = mfmNull;
   }

   void EncodeSAN(char **bptrptr) const;
   void Print(void) const;

 private:
   sqrType frsqr, tosqr;
   manType frman, toman;
   mscType msc;
   ui8 flags;
};


[chessplayer]

My chess program myopic can report on its own SRAM usage:

Code: [Select]

Global constant storage size: 262
Global variable storage size: 5036
Total program static storage size: 5298
Estimated stack storage size: 1024
Total program RAM storage size: 6322
Total available RAM size: 8192
RAM margin for libraries and expansion: 1870

The total available RAM size number of 8 KB is based on the Arduino Mega: http://www.makershed.com/ProductDetails.asp?ProductCode=MKSP5&Show=TechSpecs

That last figure of 1,870 free RAM bytes will surely shrink as development continues.  Still, there should be enough RAM left over for the addition of interesting hacks like speech output or output with LED arrays.  And of course, there should be enough RAM remaining driving a robotic arm; perhaps doing this by driving another Arduino that in turns handles the robot.

It seems to me that only a few commands are needed to drive a chess robot.

1) Reset
2) Raise/Lower
3) Grip/Ungrip
4) Move to (x, y), including off board locations
5) Signals for search completion, check, checkmate, etc.

The robot will have to send some feedback to the program:

1) New game request
2) User move data (x0, y0) to (x1, y1), including some special data like promotion choice
3) Position readout for a set-up or continued game

The Novag Citrine chess computer has a serial interface and uses reed switches and magnets to detect piece movement.  The DGT Project sells a full sized chessboard with special chessmen using RFID to identify individual pieces and this system is also available with a Bluetooth interface.  Both of these commercial products could be connected to an Arduino chess program.  What is needed is a reliable and affordable robotic arm.

Citrine:http:// http://www.chessusa.com/Merchant2/merchant.mvc?Screen=PROD&Product_Code=83-N01&Category_Code=ACC&Product_Count=1

DGT: http://digitalgametechnology.com/site/index.php/Electronic-Boards/dgt-bluetooth-wireless-e-board.html

[chessplayer]

There has been some progress with the chess program myopic; it can now solve traditional "Mate in N" chess problems.  Well, it can solve them if the value of N is not too big.  And only the first move of a forcing checkmating sequence is listed.  Also, the search is rather time-wise inefficient at this point.  Plus, the program doesn't yet understand serial input, so the input test position data has to be hard coded in the program source.

In the following run, the first four chess problems in Reinfeld's 1,001 Brilliant Ways To Checkmate were used as input test data:

Code: [Select]

TestMateSearch(4, "r1b2rk1/pp1p1pp1/1b1p2B1/n1qQ2p1/8/5N2/P3RPPP/4R1K1 w - - 0 1");
TestMateSearch(2, "2r1nr1k/pp1q1p1p/3bpp2/5P2/1P1Q4/P3P3/1B3P1P/R3K1R1 w Q - 0 1");
TestMateSearch(2, "rnbqkbn1/ppppp3/7r/6pp/3P1p2/3BP1B1/PPP2PPP/RN1QK1NR w KQq - 0 1");
TestMateSearch(3, "r1b1k2r/pp2bppp/8/3N2q1/2p5/8/PPP2PPP/R2QR1K1 w kq - 0 1");

The result output:

Code: [Select]

myopic v2009.12.11: Small system chess

Distance: 4   FEN: r1b2rk1/pp1p1pp1/1b1p2B1/n1qQ2p1/8/5N2/P3RPPP/4R1K1 w - - 0 1

bR::bB::  bRbK::
bPbP::bP::bPbP  
 bB  bP  ::wB::
bN  bQwQ::  bP  
 ::  ::  ::  ::
::  ::  ::wN::  
wP::  ::wRwPwPwP
::  ::  wR  wK  
[w - - 0 1]

Located forced mate: Qxf7+   Score: MateIn4   Nodes: 560441

Distance: 2   FEN: 2r1nr1k/pp1q1p1p/3bpp2/5P2/1P1Q4/P3P3/1B3P1P/R3K1R1 w Q - 0 1

 ::bR::bNbR  bK
bPbP::bQ::bP::bP
 ::  bBbPbP  ::
::  ::  ::wP::  
 wP  wQ  ::  ::
wP  ::  wP  ::  
 wB  ::  wP  wP
wR  ::  wK  wR  
[w Q - 0 1]

Located forced mate: Qxf6+   Score: MateIn2   Nodes: 561058

Distance: 2   FEN: rnbqkbn1/ppppp3/7r/6pp/3P1p2/3BP1B1/PPP2PPP/RN1QK1NR w KQq - 0 1

bRbNbBbQbKbBbN::
bPbPbPbPbP  ::  
 ::  ::  ::  bR
::  ::  ::  bPbP
 ::  wP  bP  ::
::  ::wBwP  wB  
wPwPwP::  wPwPwP
wRwN::wQwK  wNwR
[w KQq - 0 1]

Located forced mate: Qxh5+   Score: MateIn2   Nodes: 562064

Distance: 3   FEN: r1b1k2r/pp2bppp/8/3N2q1/2p5/8/PPP2PPP/R2QR1K1 w kq - 0 1

bR::bB::bK::  bR
bPbP::  bBbPbPbP
 ::  ::  ::  ::
::  ::wN::  bQ  
 ::bP::  ::  ::
::  ::  ::  ::  
wPwPwP::  wPwPwP
wR  ::wQwR  wK  
[w kq - 0 1]

Located forced mate: Nc7+   Score: MateIn3   Nodes: 564611

Done

[chessplayer]

Myopic's internals have been upgraded to support a search reporting a predicted variation, or "PV".  This means that a search will produce not just the (supposedly) best move, but also the predictions for a number of successor moves.  Now, PV calculations require O(N^2) memory where N is the maximum sequence length.  To make things fit in the 8 KB RAM limit of the AVR1280, the program sets an upper bound of seven moves in a PV.

The PV is shown with embedded move numbers, just as would be seen in traditional chess media and commercial chess programs.  The score and the analysis node count also appear in the output as before, but now the count is reported for each search instead of being a cumulative statistic.

The letters used for the colors and pieces are stored as initialized constant tables that take only a few lines of code.  This mean that users that prefer non-English abbreviations for colors and pieces can make changes easily.

Myopic's Arduino sketch is now about 24 KB long.  That's larger than I had expected at this point but still far below the AVR1280's 128 KB flash limit.  The program's RAM requirement has grown to be about 6,700 bytes of the 8,192 available.  Myopic does not use any EEPROM.

I've placed an order with SparkFun for one of their 8x8 RGB LED arrays with an attached AVR that communicates via a 125 KHz SPI channel.  The matrix firmware allows only a single display update format that requires a full 64 bytes of data; this in turn limits the refresh rate to about 200 Hz and there may be other factors that lower it even further.  However, the matrix firmware can be re-flashed to support other software protocols, and one improvement would allow random access of the individual LEDs.  When a chess move is made, it usually changes the contents of only two squares (three for an en passant capture and four for castling) and so only a few bytes need to be sent with an incremental updating scheme.

A re-flash of the matrix controller may also be needed for LED color management.  Some documents say that 256 colors are available while others say the limit is only eight.  Maybe somebody have already tried a re-flash to handle extra colors.  This will need more research.

SparkFun also sells a 128x64 monochrome LED array and I'll probably get one of this for displaying a (very tiny) chessboard.  But both it and an 8x8 LED matrix would be optional additions to the program; a user could still do battle with only a serial interface.

From Reinfeld's 1,001 Brilliant Ways To Checkmate, here are problems number six through ten as seen in the sketch source:

Code: [Select]


TestMateSearch(2, "r2q1r2/pp2np2/1bp4p/3p2pk/1P1N2b1/2PB2B1/P5PP/R2QK2R w KQ - 0 1");
TestMateSearch(3, "r1bqr3/pp1kn1pp/2pp4/6B1/1P6/PBp5/2P2PPP/R2QR1K1 w - - 0 1");
TestMateSearch(2, "6R1/p4p2/1p2q2p/8/6Pk/8/PP2r1PK/3Q4 w - - 0 1");
TestMateSearch(3, "6kr/1q2r1p1/1p2N1Q1/5p2/1P1p4/6R1/7P/2R3K1 w - - 0 1");
TestMateSearch(3, "6rr/p2b1pk1/1pn1p1p1/2qpPP2/3N2P1/2P1Q3/P2B2K1/2R4R w - - 0 1");

And here's the program's output for the above:

Code: [Select]


Distance: 2   FEN: r2q1r2/pp2np2/1bp4p/3p2pk/1P1N2b1/2PB2B1/P5PP/R2QK2R w KQ - 0 1

bR::  bQ  bR  ::
bPbP::  bNbP::  
 bBbP::  ::  bP
::  ::bP::  bPbK
 wP  wN  ::bB::
::  wPwB::  wB  
wP::  ::  ::wPwP
wR  ::wQwK  ::wR
[w KQ - 0 1]

Predicted variation: 1 Qxg4+ Kxg4 2 Be2#
Score: MateIn2   Nodes: 1567

Distance: 3   FEN: r1bqr3/pp1kn1pp/2pp4/6B1/1P6/PBp5/2P2PPP/R2QR1K1 w - - 0 1

bR::bBbQbR::  ::
bPbP::bKbN  bPbP
 ::bPbP  ::  ::
::  ::  ::  wB  
 wP  ::  ::  ::
wPwBbP  ::  ::  
 ::wP::  wPwPwP
wR  ::wQwR  wK  
[w - - 0 1]

Predicted variation: 1 Qxd6+ Kxd6 2 Bf4+ Kd7 3 Be6#
Score: MateIn3   Nodes: 50162

Distance: 2   FEN: 6R1/p4p2/1p2q2p/8/6Pk/8/PP2r1PK/3Q4 w - - 0 1

 ::  ::  ::wR::
bP  ::  ::bP::  
 bP  ::bQ::  bP
::  ::  ::  ::  
 ::  ::  ::wPbK
::  ::  ::  ::  
wPwP  ::bR::wPwK
::  ::wQ::  ::  
[w - - 0 1]

Predicted variation: 1 Qe1+ Rxe1 2 g3#
Score: MateIn2   Nodes: 334

Distance: 3   FEN: 6kr/1q2r1p1/1p2N1Q1/5p2/1P1p4/6R1/7P/2R3K1 w - - 0 1

 ::  ::  ::bKbR
::bQ::  bR  bP  
 bP  ::wN::wQ::
::  ::  ::bP::  
 wP  bP  ::  ::
::  ::  ::  wR  
 ::  ::  ::  wP
::  wR  ::  wK  
[w - - 0 1]

Predicted variation: 1 Rc8+ Qxc8 2 Qxg7+ Rxg7 3 Rxg7#
Score: MateIn3   Nodes: 42347

Distance: 3   FEN: 6rr/p2b1pk1/1pn1p1p1/2qpPP2/3N2P1/2P1Q3/P2B2K1/2R4R w - - 0 1

 ::  ::  ::bRbR
bP  ::bB::bPbK  
 bPbN::bP::bP::
::  bQbPwPwP::  
 ::  wN  ::wP::
::  wP  wQ  ::  
wP::  wB  ::wK::
::  wR  ::  ::wR
[w - - 0 1]

Predicted variation: 1 Qh6+ Rxh6 2 Bxh6+ Kh7 3 Bf8#
Score: MateIn3   Nodes: 43844

[chessplayer]

It's not specific to the Arduino, but here's a reference to a chess program written for the ATMega88V that could be ported to a Duemilanove:

http://www.andreadrian.de/schach/#Selbstbau_Schachcomputer_SHAH





In partial compensation for requiring an AVR1280, my program will (hopefully!) be faster, stronger, and easier to understand than the one in the above link.

[illu]

nice work !!!