TalkChess.com

Posted: **Wed Jul 27, 2011 12:59 am**

Hello, i'm back again

. I would like to write a new engine, focused in AI despite than in speed. Because all of my previous software were in assembly, this one will be in another language (maybe C++ or ObjectiveC, i have to test both, for chess).

I don't want to loose my previous work, so i post what i think could be the most interesting part: the move generator. I hope that somebody can have some idea from this. In fact, i want to talk just about the heart of this function. As all of you know, in C it is hard to use cpu status flags but in assembly this is natural. so i've found a way to test for validity of a move in very few assembly lines of code:

I "call" a macro that test the content of destination square of a move and some bit flags in eax. The bit flags contains this bits:

E.......WB

the White/Black bits can be everywhere, in eax, while the bit to know if a square is empty (E) is the upper most (most significant bit). To simplify, suppose to use just 8 bits and to test white moves. I set bits E/W both to 1:

eax = 10000010

any piece in the board is saved with its color bit.

If you test eax (test is a non destructive and) with a square content:

10000010 color flags in eax
00000001 black piece
00000000
and => z set => valid capture

10000010 color flags in eax
00000010 white piece
00000010
g set => invalid move (g is "greater than zero" bit)

10000010 color flags in eax
10000000 empty square
10000000
s set => move in empty square (s is "sign" bit)

10000010 color flags in eax
00000011 illegal square (both W/B set)
00000010
g set => illegal

So, with just one test command you can find three different results:

Code: Select all


TESTM macro delta, finedir
; eax&#58; color flags
; ecx&#58; piece index
; edx&#58; square index
; and bit color      z&#58; preso pezzo ---\___legale
;                    s&#58; vuota       ---/
;                    g&#58; illegale
test eax, &#91;edx+delta&#93;
jg finedir ; invalid move
PUSHM delta ; store pseudo-legal move for capture or empty square &#40;PUSHM is another macro&#41;
jns finedir ; capture so for sliding pieces, this is the last move
; here we follow calling the macro again, for sliding pieces
endm

As you can see, this could give you fast performance to generates moves and can be usefull even to implement a very fast perft function, with some changes.

Sample of calling this macro:

Code: Select all


TEST_DIR macro delta
  local @m_finedir
  TESTM delta*1,@m_finedir
  TESTM delta*2,@m_finedir
  TESTM delta*3,@m_finedir
  TESTM delta*4,@m_finedir
  TESTM delta*5,@m_finedir
  TESTM delta*6,@m_finedir
  TESTM delta*7,@m_finedir
@m_finedir&#58;
endm

TEST_DIR4 macro delta1,delta2,delta3,delta4
  TEST_DIR delta1
  TEST_DIR delta2
  TEST_DIR delta3
  TEST_DIR delta4
endm

MuoviDonna proc ; move queen
  TEST_DIR4 N,S,E,W
  TEST_DIR4 NE,SE,NW,SW
  ret
endp

I can explain better, if you ask me some detail.

Hoping this could help somebody. Please, let me know if you use this in your own program.

Posted: **Wed Jul 27, 2011 2:05 am**

Interesting algorithm, thanks. One downside is that the complexity of PUSHM is limited by not being able to clobber the flags register. I would guess adding an extra cmp after the PUSHM would not slow down the code much at all.

But the same basic algorithm could be used even in C--I'm not aware of anyone doing this.

Posted: **Wed Jul 27, 2011 1:27 pm**

In fact in PUSHM i have only instructions that doesn't change flags. I use other simplified TEST macros, when i know that i don't want to make captures (pawn moves, for sample) and so on.

The idea can be used even in C, obviously:

int b = board[base+delta] & flags;
if(b<0) ...illegal...
else if(b==0) ... pseudolegal...
else ...capture...

Me too, i think that nobody in the world use this idea, since now

Stefano

Posted: **Wed Jul 27, 2011 2:02 pm**

I have always used bit tests like that in my engines. In qperft (which is the move generator of Joker), for example, I use:

Code: Select all

/* board codes &#40;32 per side&#58; each 16 Pieces, 16 Pawns&#41; */
#define WHITE  0x20
#define BLACK  0x40
#define COLOR  &#40;BLACK|WHITE&#41;
#define GUARD  &#40;COLOR|0x80&#41;
#define DUMMY  &#40;WHITE-1+0x80&#41;
#define PAWNS  0x10

where GUARD thus tests as belonging to both black and white, so that neither color can capture it. DUMMY is the value used for empty squares, and the GUARDs also test as empty because of the 0x80 bit,which was useful to speed up testing validity of Pawn captures, by ANDing with (0x80|ownColor), a mask prepared outside the loop over Pawns. So only if((mask & board[toSqr]) == 0) a Pawn capture is valid. The WHITE-1 bits served to map empty squares to an unused location in the piece list, so that board[toSqr] could always be used as a valid piece number (e.g. for setting square[victim] = CAPTURED).

For the decoding of special moves in Spartacus, I use:

Code: Select all

if&#40;&#40;victim = board&#91;toSqr&#93;) == GUARD&#41; &#123;
  // special move&#58; perform special part
  if&#40;&#40;promoPiece = promoTab&#91;toSqr&#93;) == 0&#41; &#123;
    // common case&#58; handle pawn double-pushes by setting e.p. rights and key
   ...
  &#125; else if&#40;promoPiece < 0&#41; &#123;
    // handle castling by moving Rook
    ...
  &#125; else &#123;
    // promotion; promoPiece indicates the piece to promote to
    ...
  &#125;
  toSqr = fromSqr + step&#91;toSqr&#93;;
  victim = board&#91;toSqr&#93;;
&#125;

Posted: **Thu Jul 28, 2011 11:22 am**

In fact, this is very similar to my bit structure, except for the GUARD bit that assume even some other interesting meaning, in your code. The use itself of the bit flags are instead different, do to difference in the language used. In C obviously you should use if() and repeat the test some time, to handle move/capture/illegal, while in assembly you only test once and then jump conditionally when needed. Maybe the compiler is smart enough to generate the same assembly code (this have to be verifyed) i don't know.

Posted: **Thu Jul 28, 2011 11:47 am**

Indeed, a good optimizer will recognize when tests can be merged. E.g. gcc+Cygwin:

Code: Select all

main&#40;)
&#123;
	char c=getchar&#40;), d='0', e='0';
	if&#40;c>0&#41; d = '+'; else
	if&#40;c<0&#41; d = '-'; else e = '*';
	printf&#40;"%c %c\n",d,e&#41;;
&#125;

translates with gcc -O2 -S to:

Code: Select all

        .file   "opt.c"
        .def    ___main;        .scl    2;      .type   32;     .endef
        .section .rdata,"dr"
LC0&#58;
        .ascii "%c %c\12\0"
        .text
        .p2align 4,,15
.globl _main
        .def    _main;  .scl    2;      .type   32;     .endef
_main&#58;
        pushl   %ebp
        movl    $16, %eax
        movl    %esp, %ebp
        subl    $24, %esp
        andl    $-16, %esp
        call    __alloca
        call    ___main
        call    _getchar
        testb   %al, %al
        movb    $48, %dl
        movb    $48, %cl
        jle     L2
        movb    $43, %dl
L3&#58;
        movl    $LC0, (%esp&#41;
        movsbl  %cl,%eax
        movl    %eax, 8&#40;%esp&#41;
        movsbl  %dl,%eax
        movl    %eax, 4&#40;%esp&#41;
        call    _printf
        leave
        ret
        .p2align 4,,7
L2&#58;
        jl      L7
        movl    $LC0, (%esp&#41;
        movb    $42, %cl
        movsbl  %cl,%eax
        movl    %eax, 8&#40;%esp&#41;
        movsbl  %dl,%eax
        movl    %eax, 4&#40;%esp&#41;
        call    _printf
        leave
        ret
L7&#58;
        movb    $45, %dl
        jmp     L3
        .def    _printf;        .scl    3;      .type   32;     .endef
        .def    _getchar;       .scl    3;      .type   32;     .endef

You can see that both the jl and jle depend on the condition codes from thesame testb instruction.

TalkChess.com

Assembly move generation in Freccia

Assembly move generation in Freccia

Re: Assembly move generation in Freccia

Re: Assembly move generation in Freccia

Re: Assembly move generation in Freccia

Re: Assembly move generation in Freccia

Re: Assembly move generation in Freccia