How to implement negamax search + eval using unsigned integers only?

[maksimKorzh]

Hi Guys, it's been a while since my last visit to this forum,
it's cool to see a whole lot of updates)

I'm now working on a prototype of a chess program I'm gonna port into 6502 assembly to run on my KIM-1 emulator:
https://github.com/maksimKorzh/KIM-1

Here's the working draft that plays a game against itself and results in a mate:

Code: Select all

/******************************\
 ==============================

  6502 chess program for KIM-1
       (prototype in C) 

 ==============================
\******************************/

// libraries
#include <stdio.h>
#include <stdint.h> 

/******************************\
 ==============================

         Chess program

 ==============================
\******************************/

uint8_t board[128] = {
  0x16, 0x14, 0x15, 0x17, 0x13, 0x15, 0x14, 0x16,   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  0x12, 0x12, 0x12, 0x12, 0x12, 0x12, 0x12, 0x12,   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,   0x00, 0x00, 0x03, 0x03, 0x03, 0x03, 0x00, 0x00,
  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,   0x00, 0x00, 0x03, 0x05, 0x05, 0x03, 0x00, 0x00,
  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,   0x00, 0x00, 0x03, 0x05, 0x05, 0x03, 0x00, 0x00,
  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,   0x00, 0x00, 0x03, 0x03, 0x03, 0x03, 0x00, 0x00,
  0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  0x0E, 0x0C, 0x0D, 0x0F, 0x0B, 0x0D, 0x0C, 0x0E,   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
};

uint8_t move_offsets[] = {
   0x00, 0x0F,  0x10, 0x11, 0x00,                             // white pawns
   0x8F, 0x90,  0x91, 0x00,                                   // black pawns
   0x01, 0x10,  0x81, 0x90, 0x00,                             // rooks
   0x01, 0x10,  0x81, 0x90, 0x0F, 0x8F, 0x11, 0x91,  0x00,    // queens, kings and bishops
   0x0E, 0x8E,  0x12, 0x92, 0x1F, 0x9F, 0x21, 0xA1,  0x00,    // knights
   0x04, 0x00,  0x0D, 0x16, 0x11, 0x08, 0x0D                  // starting indexes
};

uint8_t piece_weights[] = { 0x00, 0x0E, 0x0E, 0x00, 0x2A, 0x2F, 0x46, 0x7F, 0x00};
int mat_score = 0x00, pos_score = 0x00, eval = 0x00;
int score;
uint8_t best_src, best_dst;
uint8_t side = 0x08;

int Search(uint8_t depth) {
  int best_score = -0x7F;
  uint8_t temp_src = 0x00, temp_dst = 0x00;
  uint8_t src_square, dst_square, piece, type, captured_piece, directions, step_vector;
  
  if (depth == 0x00) {
    mat_score = 0x00, pos_score = 0x00, eval = 0x00;
    
    int mat_white = 0, mat_black = 0, pos_white = 0, pos_black = 0;
    
    for(src_square = 0; src_square < 0x80; src_square++) {
      if(!(src_square & 0x88)) {
        if(board[src_square]) {          
          if (board[src_square] & 0x08) mat_white += piece_weights[board[src_square] & 0x07];
          else mat_black += piece_weights[board[src_square] & 0x07];
          if (board[src_square] & 0x08) pos_white += board[src_square + 0x08];
          else pos_black += board[src_square + 0x08];
        }
      }
    }

    mat_score = mat_white - mat_black;
    pos_score = pos_white - pos_black;
    eval = mat_score + pos_score;
    return (side == 0x08) ? eval : -eval;
  }
   
  for(src_square = 0x00; src_square < 0x80; src_square++) {
    if(!(src_square & 0x88)) {
      piece = board[src_square];
      if(piece & side) {
        type = piece & 0x07;
        directions = move_offsets[type + 0x1F];
        while(step_vector = move_offsets[++directions]) {
          dst_square = src_square;
          do {
            if (step_vector & 0x80) dst_square -= (step_vector & 0x7F);
            else dst_square += (step_vector & 0x7F);
            if(dst_square & 0x88) break;
            captured_piece = board[dst_square];
            if(captured_piece & side) break;
            if(type < 0x03 && !(step_vector & 0x07) != !captured_piece) break;
            if((captured_piece & 0x07) == 0x03)  return 0x7F;
            board[dst_square] = piece;
            board[src_square] = 0x00;
            side = 0x18 - side;
            //PrintBoard(); getchar();
            score = -Search(depth - 0x01);
            board[dst_square] = captured_piece;
            board[src_square] = piece;
            side = 0x18 - side;
            //PrintBoard(); getchar();
            if (score > best_score) {
              best_score = score;
              temp_src = src_square;
              temp_dst = dst_square;
            }

            captured_piece += type < 0x05;
            if(type < 0x03 & 0x06*side + (dst_square & 0x70) == 0x80)captured_piece--;
          }
          while(!captured_piece);
        }
      }
    }
  }
  
  best_src = temp_src;
  best_dst = temp_dst;
  return best_score;  
}

/******************************\
 ==============================

           Debugging

 ==============================
\******************************/

char *pieces[] = {
	".", "-", "\u265F", "\u265A", "\u265E", "\u265D", "\u265C", "\u265B", 
	"-", "\u2659", "-", "\u2654", "\u2658", "\u2657", "\u2656", "\u2655"
};

void PrintBoard() {
    for(uint8_t sq = 0; sq < 128; sq++) {
      if(!(sq % 16)) printf(" %d  ", 8 - (sq / 16));
      printf(" %s", ((sq & 8) && (sq += 7)) ? "\n" : pieces[board[sq] & 15]);
    } printf("\n     a b c d e f g h\n");
}

/******************************\
 ==============================

          Test drive

 ==============================
\******************************/

int main () {
  PrintBoard();
  while(1) {
    int score = Search(0x03);
    board[best_dst] = board[best_src];
    board[best_src] = 0;
    side = 0x18 - side;
    PrintBoard(); getchar();
    if (score == -0x7F) break;
  }
  PrintBoard();
  printf("Checkmate!\n");
  return 0;
}

Please note that all the variables apart those related to scores are 8-bit unsigned integers.
Now while I managed to solve negative offsets issue by simply using highest bit to distinguish between + and - directions
it's not so trivial with the scores.

Can anyone please gimme a clue on how can I alter my code so that it relies only on 8-bit unsigned type integers?
THANKS IN ADVANCE!

[hgm]

There is no difference between signed and unsigned integer addition and subtraction. The only difference is in how the various bit patterns should be interpreted. This can have consequences for comparison, to determine what 'larger than' means. E.g. 0x88 > 0x7f when the bit patterns are interpreted as unsigned, but it would be smaller when signed. (Because it then represents a negative number.)

[maksimKorzh]

There is no difference between signed and unsigned integer addition and subtraction. The only difference is in how the various bit patterns should be interpreted. This can have consequences for comparison, to determine what 'larger than' means. E.g. 0x88 > 0x7f when the bit patterns are interpreted as unsigned, but it would be smaller when signed. (Because it then represents a negative number.)

Thank you Mr. Muller.
What I actually did so far is reduced material and positional score values so that the don't exceed 0x7F.
Then I Have FF as -infinity and 0x7F as +infinity.
I've got rid of all but one signed variable so far via trial end error method.
I think it would work eventually.
I use 1000 0000 this bit to represent a sign and the rest for a value.
There's pretty enough room for scores after I've adjusted the values to minimal ones.

So far I have this:

Code: Select all

/******************************\
 ==============================

  6502 chess program for KIM-1
       (prototype in C) 

 ==============================
\******************************/

// libraries
#include <stdio.h>
#include <stdint.h> 
#include <stdlib.h>

/******************************\
 ==============================

         Chess program

 ==============================
\******************************/

uint8_t board[128] = {
  0x16, 0x14, 0x15, 0x17, 0x13, 0x15, 0x14, 0x16,   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  0x12, 0x12, 0x12, 0x12, 0x12, 0x12, 0x12, 0x12,   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,   0x00, 0x00, 0x01, 0x01, 0x01, 0x01, 0x00, 0x00,
  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,   0x00, 0x00, 0x01, 0x02, 0x02, 0x01, 0x00, 0x00,
  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,   0x00, 0x00, 0x01, 0x02, 0x02, 0x01, 0x00, 0x00,
  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,   0x00, 0x00, 0x01, 0x01, 0x01, 0x01, 0x00, 0x00,
  0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  0x0E, 0x0C, 0x0D, 0x0F, 0x0B, 0x0D, 0x0C, 0x0E,   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
};

uint8_t move_offsets[] = {
   0x00, 0x0F,  0x10, 0x11, 0x00,                             // white pawns
   0x8F, 0x90,  0x91, 0x00,                                   // black pawns
   0x01, 0x10,  0x81, 0x90, 0x00,                             // rooks
   0x01, 0x10,  0x81, 0x90, 0x0F, 0x8F, 0x11, 0x91,  0x00,    // queens, kings and bishops
   0x0E, 0x8E,  0x12, 0x92, 0x1F, 0x9F, 0x21, 0xA1,  0x00,    // knights
   0x04, 0x00,  0x0D, 0x16, 0x11, 0x08, 0x0D                  // starting indexes
};

uint8_t piece_weights[] = { 0x00, 0x03, 0x03, 0x00, 0x09, 0x09, 0x0F, 0x1B, 0x00};
uint8_t mat_score = 0x00, pos_score = 0x00;
uint8_t mat_white = 0, mat_black = 0, pos_white = 0, pos_black = 0;
int score;
uint8_t best_src, best_dst;
uint8_t side = 0x08;

int Search(uint8_t depth) {
  uint8_t best_score = 0xFF;
  uint8_t temp_src = 0x00, temp_dst = 0x00;
  uint8_t src_square, dst_square, piece, type, captured_piece, directions, step_vector;
  
  if (depth == 0x00) {
    mat_white = 0, mat_black = 0, pos_white = 0; pos_black = 0;
    
    for(src_square = 0; src_square < 0x80; src_square++) {
      if(!(src_square & 0x88)) {
        if(board[src_square]) {          
          if (board[src_square] & 0x08) mat_white += piece_weights[board[src_square] & 0x07];
          else mat_black += piece_weights[board[src_square] & 0x07];
          if (board[src_square] & 0x08) pos_white += board[src_square + 0x08];
          else pos_black += board[src_square + 0x08];
        }
      }
    }

    if ((mat_white - mat_black) >= 0) mat_score = mat_white - mat_black;
    else mat_score = (mat_black - mat_white) | 0x80;
    
    if ((pos_white - pos_black) >= 0) pos_score = pos_white - pos_black;
    else pos_score = (pos_black - pos_white) | 0x80;
    
    if ((mat_score & 0x80) && (pos_score & 0x80)) {
      mat_score &= 0x7F;
      pos_score &= 0x7F;
      return (side == 0x08) ? (mat_score + pos_score) | 0x80 : (mat_score + pos_score);
    }
    
    else if (mat_score & 0x80) {
      mat_score &= 0x7F;
      pos_score &= 0x7F;
      if (pos_score >= mat_score) return (side == 0x08) ? (pos_score - mat_score) : (pos_score - mat_score) | 0x80;
      else return (side == 0x08) ? (mat_score - pos_score) | 0x80 : (mat_score - pos_score);
    }
    
    else if (pos_score & 0x80) {
      mat_score &= 0x7F;
      pos_score &= 0x7F;
      if (mat_score >= pos_score) return (side == 0x08) ? (mat_score - pos_score) : (mat_score - pos_score) | 0x80;//eval = mat_score - pos_score;
      else return (side == 0x08) ? (pos_score - mat_score) | 0x80 : (pos_score - mat_score); // correct
    }
    
    else return (side == 0x08) ? (mat_score + pos_score) : (mat_score + pos_score) | 0x80;
  }
   
  for(src_square = 0x00; src_square < 0x80; src_square++) {
    if(!(src_square & 0x88)) {
      piece = board[src_square];
      if(piece & side) {
        type = piece & 0x07;
        directions = move_offsets[type + 0x1F];
        while(step_vector = move_offsets[++directions]) {
          dst_square = src_square;
          do {
            if (step_vector & 0x80) dst_square -= (step_vector & 0x7F);
            else dst_square += (step_vector & 0x7F);
            if(dst_square & 0x88) break;
            captured_piece = board[dst_square];
            if(captured_piece & side) break;
            if(type < 0x03 && !(step_vector & 0x07) != !captured_piece) break;
            if((captured_piece & 0x07) == 0x03)  return 0x7F;
            board[dst_square] = piece;
            board[src_square] = 0x00;
            side = 0x18 - side;
            //PrintBoard(); getchar();
            score = Search(depth - 0x01);
            
            
            if (abs(score) & 0x80) score = -(abs(score) & 0x7F);
            score = -score;

            board[dst_square] = captured_piece;
            board[src_square] = piece;
            side = 0x18 - side;
            //PrintBoard(); getchar();
                        
            if ( score > ((best_score & 0x80) ? -(int)(best_score & 0x7F) : best_score) ) { 
              best_score = (score < 0) ? (abs(score) | 0x80) : score;
              
              

              
              
              
              temp_src = src_square;
              temp_dst = dst_square;
            }

            captured_piece += type < 0x05;
            if(type < 0x03 & 0x06*side + (dst_square & 0x70) == 0x80)captured_piece--;
          }
          while(!captured_piece);
        }
      }
    }
  }
  
  best_src = temp_src;
  best_dst = temp_dst;
  return ((best_score & 0x80) ? -(int)(best_score & 0x7F) : best_score);
}

/******************************\
 ==============================

           Debugging

 ==============================
\******************************/

char *pieces[] = {
	".", "-", "\u265F", "\u265A", "\u265E", "\u265D", "\u265C", "\u265B", 
	"-", "\u2659", "-", "\u2654", "\u2658", "\u2657", "\u2656", "\u2655"
};

void PrintBoard() {
    for(uint8_t sq = 0; sq < 128; sq++) {
      if(!(sq % 16)) printf(" %d  ", 8 - (sq / 16));
      printf(" %s", ((sq & 8) && (sq += 7)) ? "\n" : pieces[board[sq] & 15]);
    } printf("\n     a b c d e f g h\n");
}

/******************************\
 ==============================

          Test drive

 ==============================
\******************************/

int main () {
  PrintBoard();
  while(1) {
    int score = Search(0x03);
    board[best_dst] = board[best_src];
    board[best_src] = 0;
    side = 0x18 - side;
    //PrintBoard(); getchar();
    if (score == -0x7F) break;
  }
  PrintBoard();
  printf("Checkmate!\n");
  return 0;
}

I know it looks ugly but at least now with this custom 'on the knee' signed arithmetic implementation
I can use it as guide to write the program in 6502 assembly.

[hgm]

I don't understand why you would shy away from using signed integers. It seems to me you are just creating problems for yourself that should not exist. My second chess program was for 6502, and I never noticed any problems with using signed integers (e.g. for the board steps).

[maksimKorzh]

I don't understand why you would shy away from using signed integers. It seems to me you are just creating problems for yourself that should not exist. My second chess program was for 6502, and I never noticed any problems with using signed integers (e.g. for the board steps).

Well, I'm gonna be running it on KIM-1 emulator I made: https://maksimkorzh.github.io/KIM-1/
Left most 4 digits stands for memory address,
Right most 2 digits is the value at that address.
The value can be from 0x00 to 0xFF.
If adding or subtracting with carry flag (actually there's no other way in 6502)
exceeding values in either positive or negative side would result in wrapping around (and setting the carry flag, and I guess negative flag as well)
So it doesn't have a signed math implementation in it's ROM, there are some third party ones but I wanna make it on my own, from scratch.
If I was originally writing in 6502 assembly probably I could just rely on carry and negative flags and be happy with that, but since I don't have an access
to these flags in C I can't replicate the program in C. Now why I want to have it in C is to male sure that the logic is working properly.
Debugging logic in 6502 straight ahead is too brutal for me, so I rather do these 'problems' which is more explicit hence simple way of doing things.
Because now even though my C code is ugly I can rewrite it in 6502 assembly.

[hgm]

Well, wrapping around is signed arithmetic. Because, as I said, signed and unsigned arithmetic is exactly the same, when you use a 2-complement enconding for the signed numbers. It is just that you have to beware what you consider overflow (= wrapping) and what not. The 6502 has the C and V flags for that. In C you have no access to the flags, but use if(a>b) to describe the setting of a flag by a compare instruction, together with the following branch that acts on it. Which flag will be used depends on how you have declared a and b (as signed or unsigned), or how you cast them.

Chess programs usually only need to branch on a comparison when the score is inolved; other branches are usually on bitwise logical operations, whether they result in 0 or not (e.g. to test whether you stray of board by ANDing with 0x88).

[maksimKorzh]

Well, wrapping around is signed arithmetic. Because, as I said, signed and unsigned arithmetic is exactly the same, when you use a 2-complement enconding for the signed numbers. It is just that you have to beware what you consider overflow (= wrapping) and what not. The 6502 has the C and V flags for that. In C you have no access to the flags, but use if(a>b) to describe the setting of a flag by a compare instruction, together with the following branch that acts on it. Which flag will be used depends on how you have declared a and b (as signed or unsigned), or how you cast them.

Chess programs usually only need to branch on a comparison when the score is inolved; other branches are usually on bitwise logical operations, whether they result in 0 or not (e.g. to test whether you stray of board by ANDing with 0x88).

Indirectly referencing flags via comparison is smart! How couldn't I come up with that on my own!?
But anyway, I've already managed to complete my solution with the highest bit representing negative sign,
without relying on 1's or 2's complements at all: https://github.com/maksimKorzh/6502-che ... rc/proto.c
What do you think of the above implementation?
Does it make sense?
At least now I can port it to 6502.

P.S. Btw the next challenge is how to keep track of stack frame variables (I mean those defined locally within a search)?
I should probably define them something like StackPointer - 1, StackPointer - 2, etc. ? (since in 6502 stack growth downwards)
Need to make sure not to overwrite return addresses

[hgm]

Well, you can of course represent numbers by bit patterns in any way you want. You could also use an encoding where 0x08 represents units, 0x10 the number 2, 0x012 the number 4, 0x02 the number 8, etc.. As long as there is a 1-to-1mapping of numbers to bitpatterns it will work. Of course you would need a rather complex piece of code to add two numbers and obtain the sum in that same representation, and it would be horribly slow.

It is the same here: using 0x80 as sign, and the 0x7f part as absolute value in the 'natural' representation, every addition requires you to treat cases with different sign separately, rather than just using the CPU's adder hardware. Note that you don't really need adding hardware to have a turing-complete processor; the ability to test and set individual bits, and branch on their value will enable you to implement addition.

[maksimKorzh]

Well, you can of course represent numbers by bit patterns in any way you want. You could also use an encoding where 0x08 represents units, 0x10 the number 2, 0x012 the number 4, 0x02 the number 8, etc.. As long as there is a 1-to-1mapping of numbers to bitpatterns it will work. Of course you would need a rather complex piece of code to add two numbers and obtain the sum in that same representation, and it would be horribly slow.

It is the same here: using 0x80 as sign, and the 0x7f part as absolute value in the 'natural' representation, every addition requires you to treat cases with different sign separately, rather than just using the CPU's adder hardware. Note that you don't really need adding hardware to have a turing-complete processor; the ability to test and set individual bits, and branch on their value will enable you to implement addition.

Mr. Muller, I completely agree with you. Thank you for taking time to have a look at my implementation.
This is a trade off. I lose the performance - that's very true, but I win the clarity.
Also now I don't need t think about design of the program and just be precise while porting.
I love doing things that I completely understand and can always check/test.
If I was intending developing it using assembler and memory dump print out (which I have embedded into my emulator)
then I would've gone your way (actually I did earlier but failed and lost interest), but since I'm going for
the most hardcore possible way of programming in machine codes on this:

having only 6502 opcodes list in front of me and KIM-1 ROM routines for I/O the biggest challenge is how
to debug the entire thing - that's very looong. So when I'll be debugging, thanksfully to my current implementation
in every single part of code I would be sure which value in what memory cell I will have to obtain to make sure it's bug free.
You might be arguing like why the heck to do this ever (well, it's rhetoric and it's just important for me and it's fun)
but if one actually considers this path then I think you agree that knowing the expected output of every tiny little part of
code upfront is immensely important because messing up a single byte would crash the program

[hgm]

If I recall correctly the KIM-1 is a very small machine, with only 1.125KB of RAM. It will be a real challenge to fit a chess program in such a small amount of memory. So using inefficent code seems a very bad idea.