New Chess Engine

[Roy van Rijn]

Hi everybody,

I'd like to introduce myself to this forum.

Roy van Rijn, website: http://www.redcode.nl/

Most of my free time up to now has been spend on Corewar programming and RecMath/Al Zimmermann's programming contests. During those contests I stumbled across bitboards and chess engines. So this weekend I decided it was time for me to write my own chess engine!

I've started out in Java (might translate it later on) and I'm now working on implementing all the rules (of course using bitboards). I haven't implemented en-passant/castling and promotion rules yet, here is what I have right now:

Perft:

Nodes: 20 (perft 1)
Captures: 0
Checks: 0
Mates: 0
---- 0ms

Nodes: 400 (perft 2)
Captures: 0
Checks: 0
Mates: 0
---- 10ms

Nodes: 8902 (perft 3)
Captures: 34
Checks: 12
Mates: 0
---- 160ms

Nodes: 197281 (perft 4)
Captures: 1576
Checks: 469
Mates: 8
---- 580ms

Nodes: 4865351 (perft 5)
Captures: 82461
Checks: 27351
Mates: 347
---- 3100ms

I think this works like it is used to, without the en-passant rule that is.

The speed isn't very good at the moment (I think?) but that is probably due to my costly 'check/pin'-checking (no xray yet) and the Kogge-Stone algorithm. That is why I'm now investigating magic bitboards (everybody seems to be using that right now). But I don't fully understand it yet (it'll come). The basic idea is clear, but the details are still a bit sketchy in my head, I'll probably need to implement it and see for myself. Maybe somebody has a more visual explaination? (those tend to work best for me). http://chessprogramming.wikispaces.com/Magic+Bitboards didn't yet do the trick.

I'm planning on making it interface with WinBoard eventually and create a fully working (open source) Java Chess Engine. Then the fun part starts, implementing search logic and tactics

[Olivier Deville]

Hello Roy

Welcome to our crazy hobby, and good luck developing your engine

As soon as Winboard protocol is implemented, it will be tested here.

Olivier

[Andres Valverde]

Hi Roy,

Welcome to WB forum. You will get any help you demand here.

Note that this is an extremely adictive hobby, take care!

[Graham Banks]

Note that this is an extremely adictive hobby

Sure is!

[Roy van Rijn]

Just a small update:

Nodes: 4865351 (5)
Captures: 82461
Checks: 27351
Mates: 347
---- 1635ms

Improvement of almost 50% here. When not counting mates/checks/captures the numbers are:

Nodes: 20 (1)
---- 0ms
Nodes: 400 (2)
---- 1ms
Nodes: 8902 (3)
---- 20ms
Nodes: 197281 (4)
---- 316ms
Nodes: 4865351 (5)
---- 436ms
Nodes: 119048429 (6)
---- 6939ms

How are these numbers compared to other engines? I don't have any clue... are there performance numbers/results posted anywhere?
I've seen perft-6 numbers as low as +/-1.5 seconds.

[Andres Valverde]

Just a small update:

Nodes: 4865351 (5)
Captures: 82461
Checks: 27351
Mates: 347
---- 1635ms

Improvement of almost 50% here. When not counting mates/checks/captures the numbers are:

Nodes: 20 (1)
---- 0ms
Nodes: 400 (2)
---- 1ms
Nodes: 8902 (3)
---- 20ms
Nodes: 197281 (4)
---- 316ms
Nodes: 4865351 (5)
---- 436ms
Nodes: 119048429 (6)
---- 6939ms

How are these numbers compared to other engines? I don't have any clue... are there performance numbers/results posted anywhere?
I've seen perft-6 numbers as low as +/-1.5 seconds.

You perft seems pretty fast, Dirty has a fast movegen and gets the numbers below. However your perft 5 and 6 give a wrong node number. As it it initial position i guess it is related to en passant captures , i.e : 1.e4 d5 2.e5 f5 3.exf6 e.p. (note that it takes place at ply 5).

perft 1
20 legal moves
perft 2

Perft 2
Time: 0 ms
Leaf Nodes: 400
perft 3

Perft 3
Time: 0 ms
Leaf Nodes: 8902
perft 4

Perft 4
Time: 0 ms
Leaf Nodes: 197281
perft 5

Perft 5
Time: 125 ms
Leaf Nodes: 4865609
perft 6

Perft 6
Time: 3031 ms
Leaf Nodes: 119060324

[Roy van Rijn]

Yes, I should have mentioned, no en-passant and castling yet

[H.G.Muller]

The speed is not bad (although different to compare if we don't know your hardware). On a 1.3GHz Celeron-M qperft gets:

Code: Select all

$ ./qperft 6
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - r n b q k b n r - -
 - - p p p p p p p p - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - P P P P P P P P - -
 - - R N B Q K B N R - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes

perft(1)=20 ( 0.000 sec)

perft(2)=400 ( 0.000 sec)

perft(3)=8902 ( 0.000 sec)

perft(4)=197281 ( 0.010 sec)

perft(5)=4865609 ( 0.360 sec)

perft(6)=119060324 ( 9.173 sec)


So that is a bit slower than yours. The numbers are different, though, but that is probably due to missinng e.p. captures.

[Roy van Rijn]

Ok, thanks guys! For a starting engine (* in Java *) a week old it seems to be pretty good. Time to shift the focus onto e.p. and castling, I keep getting distracted with small optimization-opportunities.

My machine is a Dell M4500 laptop, Core i7 Q840 (1.87 quad core). Very happy with the quadcore with hyperthreading, but my engine is just a single thread heh.

What is the best way to make chess engine's work in a multi-core environment, just copy the whole board and let two seperate processes search from different startingpoints?

[Andres Valverde]

Yes, I should have mentioned, no en-passant and castling yet

Well, I should mentioned the hardware : Q6600 2.4Mhz

[Dann Corbit]

Ok, thanks guys! For a starting engine (* in Java *) a week old it seems to be pretty good. Time to shift the focus onto e.p. and castling, I keep getting distracted with small optimization-opportunities.

My machine is a Dell M4500 laptop, Core i7 Q840 (1.87 quad core). Very happy with the quadcore with hyperthreading, but my engine is just a single thread heh.

What is the best way to make chess engine's work in a multi-core environment, just copy the whole board and let two seperate processes search from different startingpoints?

There are many different SMP algorithms. Dr. Hyatt has a nice article on it:
http://www.cis.uab.edu/hyatt/search.html

Viper is a learning engine that is SMP:
http://www.glaurungchess.com/viper/

Scorpio uses both SMP and also machine clustering and is open source:
https://github.com/dshawul/Scorpio

There are some chess programming papers here:
http://cap.connx.com/chess-papers/
including multi-cpu work.

[Roy van Rijn]

This is better, now including the freshly implemented en-passant moves:

Nodes: 4865609 (5)
Captures: 82719
En passant: 258
Castling: 0
Promotions: 0
Checks: 27351
Mates: 347
---- 1794ms

Nodes: 119060292 (6)
Captures: 2812008
En passant: 5248
Castling: 0
Promotions: 0
Checks: 809095
Mates: 10828
---- 44323ms

The only problem now is finding the bug I still have, perft-6 is off by 12 nodes, 4 checks... I guess it is now time to download a perft-tool and try to implement divide to search for the bug.
(or does anybody here have a clue what might cause this tiny 12-nodes bug?)

[H.G.Muller]

It seems more like 32 nodes to me...

Always hard to say. Best is to either use divided perft and zoom in on the error by starting from positions along the faulty branch, (but this sometimes makes the error go away), or do multiple split perft limited to a selected branch.

I noticed that your times went up dramatically: 44 sec in stead of 7 for perft(6)...

[Roy van Rijn]

I noticed that your times went up dramatically: 44 sec in stead of 7 for perft(6)...

That is the way I measure them, in the first (fast) example I went to the node, didn't check for check/mate/stalemate/captures that final node, I just enumerated the node-count. The second time (to get more information) I did check every end-node, the step to perft-7 is then almost already made.

And yes:
119060324 - 2812008 - 5248 - 0 - 0 - 809099 - 10828 (http://chessprogramming.wikispaces.com/Perft+Results)
119060292 - 2812008 - 5248 - 0 - 0 - 809095 - 10828 (me)
--------------------------------------------------------------
000000032 - 0000000 - 0000 - 0 - 0 - 000004 - 00000 (close, but no cigar)

Update:
Found them, thanks to ROCE and its divide function, two stupid bugs (aren't they all?):

Nodes: 119060324 (6)
Captures: 2812008
En passant: 5248
Castling: 0
Promotions: 0
Checks: 809099
Mates: 10828
---- 46971ms

Only castling is in my way now... the last hurdle before I have a working chess engine/move generator!

[Fritz Reul]

Hi
I am planning to port my Loop engine to Java, too. But as far as I know Java does not implement any unsigned 64-bit build-in type - is this correct?
Fritz

[Gerd Isenberg]

Hi
I am planning to port my Loop engine to Java, too. But as far as I know Java does not implement any unsigned 64-bit build-in type - is this correct?
Fritz

Hi Fritz,
yes, Java has only signed integers, char 8, short 16, int 32 and long 64 bit. To avoid right shifts with the sign bit, it has the >>> unsigned shift operator, always shifting in zeros (opposed to signed shift >>).

Gerd

[Fritz Reul]

Hi
I am planning to port my Loop engine to Java, too. But as far as I know Java does not implement any unsigned 64-bit build-in type - is this correct?
Fritz

Hi Fritz,
yes, Java has only signed integers, char 8, short 16, int 32 and long 64 bit. To avoid right shifts with the sign bit, it has the >>> unsigned shift operator, always shifting in zeros (opposed to signed shift >>).

Gerd

Hi Gerd!
You are right, the unsigned right shift is an interesting operator. The motivation of translating Loop to you Java is my new Android mobile phone. I am balancing pros & cons for the translation into Java and a remote engine similar to Tords GlaurungServer. I suppose both would be much fun but my knowledge in networks, sockets etc. is quite limited
Fritz

[abik]

The motivation of translating Loop to you Java is my new Android mobile phone.

If your engine supports the UCI protocol, and has been written in C/C++ in a portable way (viz. compiles well for Linux), have you considered simply compiling it for Android (ARMv5TE) with the appropriate compiler tool chain and importing it into Chess for Android?

See http://www.aartbik.com/MISC/uchess.html for more details.