NXC: autonomous chess program + chess robot for NXT

[HaWe]

That's pretty cool. I'd be interested to know a couple things:
1) How does it evaluate the board (to determine if a move is "good")
2) How do you plan to distribute the processing across multiple NXTs.

Steve

the evaluation is made by 3 things:
1st, the "piece balance sheet" before/after the move (considering the balance after all deepenings: it's sort of Alpha-Beta-Search);
2nd, if the opponent is put in check (currently weighted too high);
3rd, some other criteria by this subroutine which evaluates the stationing by very simple criteria (they have to be kept simple not to induce completely wrong stategies in some cases):

Code: Select all

/******************************************************************************/
void Score (char CK, char RK, char &board[]) {
/******************************************************************************/
// scBlackP 104                 // score of piece values
// scBlackS 105                 // score for strategy (positioning)
// scBlackC 106                 // score for check
// scWhiteP 108
// scWhiteS 109
// scWhiteC 110


  float pwi,pbl,    // sum of piece values
        cwi,cbl,    // sum of check values
        swi,sbl;    // sum of strategy values
  int   n,          // current sqr number index
        b,          // square number
        pv,         // piece value
        piece;      // piece type
  char  WiK, BlK;   // flags for king found


  cwi=cbl=pwi=pbl=swi=sbl=0;
  WiK=BlK=false;

  for (n=0;n<120;++n) {
    b=board[n];                              // square number
    piece=b&7;                               // piece type

    if (!(n&0x88)) {                         // valid square
       pv=pvalue[b&piece];                   // piece value

       if (b&8)  {                           // white
         if (pv<0) WiK=true;                 // King found
             else pwi+=pv;                   // add piece value to score
         if ((b&32) && (piece==4)) swi+=1;   // bonus for virgin K
         if ((b&32) && (piece==6)) swi+=0.6; // bonus for virgin R
         if ((piece==1)&&(n<72))   swi+=0.5; // bonus for pawn ahead
         if ((piece==1)&&(n<23))   swi+=1;   // bonus for pawn at opp.side
         if ((piece==1)&&                    // opening: P in center pos
              ( ( (n==68)&& (!board[67]))||( (n==67)&&(!board[68]) ) )
              &&(board[97]&32)&&(board[98]&32)&&(board[101]&32)&&(board[102]&32))
             swi+=2;
         if ((piece==3)&&(n<112)&&(n>8)) ++swi;    // bonus for knight off 1||8
         if ((pv==1)&&(n<8)) swi+=16;   // pawn->Queen (+extra Queen piece value)
       }

       else
       if (b&16) {                           // black
         if (pv<0) BlK=true;                 // King found
             else pbl+=pv;                   // add piece value to score
         if ((b&32) && (piece==4)) sbl+=1;   // bonus for virgin K
         if ((b&32) && (piece==6)) sbl+=0.6; // bonus for virgin R
         if ((piece==2)&&(n>47))   sbl+=0.5; // bonus for pawn ahead
         if ((piece==2)&&(n>95))   sbl=+1;   // bonus for pawn at opp.side
         if ((piece==2)&&                    // opening: P in center pos
              (( (n==51)&&(!board[52]))||((n==52)&&(!board[51])))
              &&(board[17]&32)&&(board[18]&32)&&(board[21]&32)&&(board[22]&32))
             sbl+=2;
         if ((piece==3)&&(n<112)&&(n>8)) ++sbl;    // bonus for knight off 1||8
         if ((pv==1)&&(n>111)) sbl+=16; // pawn->Queen (+extra Queen piece value)
       }
    }
  }


  if((CK & 8)) {cwi=-1;  }
  if((CK &16)) {cbl=-1;  }

  if (!WiK) {pwi=cwi=swi=-120; }  // king capture marker
  if (!BlK) {pbl=cbl=sbl=-120; }

  board[104]=pbl; board[105]=sbl; board[106]=cbl;
  board[108]=pwi; board[109]=swi; board[110]=cwi;

}

The parallelizing is made by the main routine:
on 2 NXTs, it will start the 1st ply search including all follow-up-deepenings on all even fields on the master and on all odd fields on the BT slave.
Having 3 or 4 bricks it will be based on subsets like modulo 3 or 4 so that not 1 brick is supposed to have all the work on the first (or last) 2 ranks at the start.
It waits until all slaves are finished and then it compares the board scores of all subset moves.

[hassenplug]

I think there's a typo part way down your code. This line:

if ((piece==2)&&(n>95)) sbl=+1; // bonus for pawn at opp.side
Should read
if ((piece==2)&&(n>95)) sbl+=1; // bonus for pawn at opp.side

If it were me, I'd combine all these things into a single value (balance sheet, 'check', other criteria) because then you could weight some values more than others.

Looks like there should be quite a few ways to optimize that code. (that's good, right?) If you don't want suggestions, feel free to skip the rest of this post...

One thing I would do is avoid calculating things every time through the loop. Only do it once, where possible. For example, at the start of the game, you can calculate the total piece value, and then only change that value when a piece is captured.

Also, it looks like you're scanning the entire board each time, looking for pieces, when I'd think you would just have an array for all the [non-captured] pieces, and scan through that.

Fun to think about.

Steve

[HaWe]

yes, correct about that typo, thanks !
Scanning the board to score the positioning and extraordinary factors like pawn-promotions to extra queens and effects for direct or discovered checks, which all have to be passed to the next ply level or back to the one before anyway, then adding a piece value incidentally (if a piece was found during strategy scan) didn't appear time-critical yet.

As you got my code, you may try it out by your own: Just take the calculation time for 1 opening ply by a stop watch, then change my code into your version and again take the calculation time for the same ply (consider that you will have to manage and maintain and pass and reset the array for all the non-captured pieces to other levels additionally)! I'm really curious about your observations!

[hassenplug]

As you got my code, you may try it out by your own: Just take the calculation time for 1 opening ply by a stop watch, then change my code into your version and again take the calculation time for the same ply (consider that you will have to manage and maintain and pass and reset the array for all the non-captured pieces to other levels additionally)! I'm really curious about your observations!

I would be interested in doing that, if I had time for another project. And as much as I'd like to have an NXT-powered chess-engine, I have way too many other things on my list.

I'm not sure the best place to see the differences would be with 1 ply and a stop watch. However, I suspect you'll quickly see the changes when you go farther along.

For example, for an opening move, there are 20 options. And, you won't see much change if the program is only executing that function 20 times. However, if you look at your opponent's 20 options, and your second move (say, also 20 options, but I'm not really sure) and your opponent's second move (another 20) then for ONLY your first two moves, and your opponent's first two moves, the program will be going through this function 160,000 times. That's where those tweaks will really start to make a difference.

Steve

[HaWe]

actually I'm calculating only 3 plys (20*20*20=8000 moves) which lasts over all about
2-3 hours.
The 8000 function calls including all loops have to be done anyway as mentioned above.
8000 loops in this function with 32 additions including evaluation of 2 if-statements each lasts:
1 minute
(time to spare, but
minus 20 sec for empty looping itself including the incrementation of the loop counter which is time that is consumpted anyway,
minus the additional time (not tested, no idea how much) you will now need in order to copy an array[32] 8000 times to a dummy and pass the copy to another function by value and back to the calling one...)

[hassenplug]

The 8000 function calls including all loops have to be done anyway as mentioned above.
8000 loops in this function with 32 additions including evaluation of 2 if-statements each lasts:
1 minute

My mistake. I didn't mean to suggest that was the best change for speeding up the code. I'm sure there are other parts of the program that could make much bigger improvements in the speed/time.

The way I would address this challenge would be to create a global multi-dimensional array (or very large array with some kind of pointer) and use that to store all values. Changing the second-dimension (or pointer) would allow you to do 'recursion' of sorts (no need to forfeit your kingdom).

Then, create a list of 'valid moves' and scan through that, instead of scanning the entire array of squares.

Why does your board include squares that the pieces can not move to?

Steve

[HaWe]

it's simply the implementation of the 0x88 board design ;)
http://www.mindstormsforum.de/viewtopic ... 352#p57366
http://home.hccnet.nl/h.g.muller/board.html
http://home.hccnet.nl/h.g.muller/max-src2.html
0x88 is a proven design, although of course there are other proven board designs as well (e.g., like the bitboard).
My intention was to get anything like a chess program working autonomously on the NXT, never to write a competitive chess program. (A couple of years ago I didn't think I could manage to do even this).
That would need a deepening of at least 6 plys, the current PC version by Muller has a deepening of 8-9 , which currently would probably last about 1 year for each move to be calculated by the NXT autonomously (though it's theoretically possible to do this with my code easily).
As I said before: It was just a test for myself to see if I had understood the underlying ideas and try put them into a non-recursive code and see if I'll be able to get it working at all.
So if you have any ideas how to make it 50% faster I'll try it glady - but not for making it 0.1% faster or anything that requires to re-program the whole basic algorithms - and it will need that you'll provide "real code", not just a vague idea out of the blue - AND you first of all will need to understand the complex interplay of all sub-functions why they are working this way and not other way (because e.g. one seeming disadvantage of one algorithm is bought by giant following advantages by other dependent algorithms - although I admit that this is not always the case with my approaches and solutions, Muller's solutions are surely exponentially better and faster).
After all my personal fun is not to have a perfect code but to have an autonomously playing chess robot both calculating moves and providing all the moves (the automatically generated ones - even if not perfect - as well as the manually chosen ones) by a real robot arm on a real chess board.
:)

[hassenplug]

OK.

I suspect it will be very difficult to find a simple tweak that can cut the time by 50%, without changing the algorithms.

Turns out, I do understand the complex interplay of simulated recursive code. A couple years back (darn, I guess it was about seven years ago) I made a LEGO robot that can play Connect Four. Complete with variable depth searching.

Thanks for giving me something to think about. I won't bother you with other suggestions.

Steve

[spillerrec]

Looks nice.
(Just when I was about to try to access Google translate with a proxy to get a different Google server, it started working...)

I look forward to when you get it working together with the robot. Would have been nice if the robot too had been done only using Lego though.


I thought you would be using a custom stack to create variable depth recursion, but I do see the point of not doing it when you only need three levels. Would have been cool though.


You can easily optimize the code above by just combining the if statements. While it is pretty easy I wouldn't be surprised if it gave a 10-20% speedup for that section of the code. Here it is for white pieces:

Code: Select all

if (b&8){
	if(pv<0)
		WiK=true;
	else{
		pwi+=pv;
		if ((pv==1)&&(n<8)) swi+=16;	//Can't happen if pv<0
	}
	
	switch( piece ){
		case 1:
				if( n<72 ){
					swi+=0.5;
					
					if( n<23 ) //Does not happen unless n<72
						swi+=1;
					else	//n must be either 67 or 68, i.e. it lies between less than 72 and bigger or eqaul 23
						if( ( ( (n==68)&& (!board[67]))||( (n==67)&&(!board[68]) ) )&&(board[97]&32)&&(board[98]&32)&&(board[101]&32)&&(board[102]&32))
							swi+=2;
				}
			break;
		
		case 3:	if( (n<112)&&(n>8) ) ++swi; break;
		
		default:
			//The following only does something if piece is 4 or 6, so don't check b%32 unless it might be one of these two
			if( b&32 ){
				switch( piece ){
					case 4: swi+=1; break;
					case 6: swi+=0.6; break;
				}
			}
	}
}

Try to get used to do these small optimizations, since they do not depend on your algorithm, but can have an significant effect on performance. If you get used to this you will do it without thinking about it when you initially write the code, avoiding potential bottlenecks.

Anyway, what code does actually cause the slowdown?

[HaWe]

thx for your suggestion. I'll try it ASAP. it might be 20% indeed I guess, but it will effect probably only <1% speed up over all. On the other hand, this function is only in a beta state, there will several conditions surely be changed or deleted or additionally inserted; writing all behind each other make this easier to test and debug.
There are many functions involved, actually all you can read going through the source: e.g., move generation itself, validity testing, see if put in check dircetly or by discovering, legally or illegally, considering anything like castling, or pawn double steps, or en-passant, or promotion, but no single function of mine claims to be speed-optimized:
Speed is not an issue for me, if it made it only 10-20% faster over-all. For 5000% faster (== 50 times as fast as now) would provide 1 extra deepening in the same time as currently.

Surely this score function will never be any "bottleneck" - but if you want to reprogram it all and want using a custom stack because you think it's "cool" to have one - feel free to do it and share yor code!
I took ft because I have a lot of it, it's far more stable because it got metal liftarms (up to 2m length in a whole), and metal axles (up to 1m, and even metal gears can be used), because it's far easier to handle, and because the ft robot arm construction is simply ingenious and brilliant, I love it since I purchased my first one in the '80s/'90s (maybe using Tetrix might have been an option, too). Only the ft and Tetrix controllers and encoder motors are far worse than those by Lego.
Anyhow this program now is the first approach to a functioning chess program (and a chess robot) - ever - running autonomously on a NXT, some things certainly will be constantly improved. You surely may try to do it even better... :mrgreen:

ps
the robot is already working too, as he is able to approach all 64 fields correctly and lift and put down any piece. Still to do: how to handle pawn promotion to up to 2*8 extra queens or rooks or bishops or knights (each or anything mixed) by the robot arm (where to be stored and taken all those pieces? E.g., my robot claw is not able to pick an out-taken rook, turn it 180° and put in on a square now other way round to transform/indicate it to be a Queen. Of course virtually on the screen this already can be achieved easily). And to do: enhancing the implementation of castling and the FIDE 50-moves rule and the 3-repetitions rule.