Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Chess Programing: Request for Code Review.


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
14 replies to this topic

#1 ashish123   Members   -  Reputation: 166

Like
0Likes
Like

Posted 22 December 2012 - 03:05 AM

Hi all,

 

I have written a chess program using bit boards in C# and almost done with move generation(Castling still incomplete).

 

I have also written a PERFT function which gives me  the following statistics for the starting position on the chess board:

  1. 20 Nodes ---> 10 ms  --->  2 kN/s
  2. 400 Nodes --->11 ms  --->  36 kN/s
  3. 8902 Nodes ---> 18 ms  ---> 494.56 kN/s
  4. 197281 Nodes  --->477 ms. ---> 413.59 kN/s
  5. 4865609 Nodes ---> 4372 ms   --->  1112.9 kN/s
  6. 119060324 Nodes ---> 307920  ---> 386.56 kN/s

 

 

This is my very first bit-boards chess engine so don't know much about the speed, however when compared to my previous 0x88 chess stats this is definitely a winner.

 

When I compared these stats with Sharper (amazing chess program), I realized that it is much more faster than this, It computed Perft(6) in 132 ms without hash tables.

 

So I would request some one with experience in chess programming or in c# to review my code and let me know where I am going wrong or what can be done to optimize it.

 

I shall post my code if any one is ready to review the same.

Please note, that there are no visible bugs.

 

Also if any one is aware, kindly post some kind of profiling tool which will help me to understand the coding efficiency better.

 

I am using Visual Studio 2010 as my IDE and C# as the language.

 

Thanks.

 

 



Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 13662

Like
0Likes
Like

Posted 22 December 2012 - 08:54 AM

I have experience in chess programming, but not in C#. The purpose of perft is to verify correctness of the move generation and functions to make and undo moves. As a proxy for the performance of the code in a real chess game, it's not very useful. It does make sense that the time it takes your program to complete perft 6 shouldn't be orders of magnitude more than other programs.
 
You say that Sharp (I am not familiar with this program) can finished perft 6 in 132 milliseconds without hash tables. If you are using a 3GHz CPU, that means it takes it less than 4 cycles to visit a position. I don't think I believe that claim.
 


#3 ashish123   Members   -  Reputation: 166

Like
0Likes
Like

Posted 22 December 2012 - 09:24 AM

Thanks alvaro for the reply,

 

I didnot calculate that but yes it seems impossible, however it is what my system shows.

Can you please comment on the speed my program is giving

My machine configuration is 

Intel i3 core,

4.00GB RAM

2.40 GHz.

 

Also it would be helpful if you agree review my code, it uses nothing C# specific. (My program contains everything static even arrays and other stuff).

Getting my code reviewed from an experienced and expert like you would also help me be a better programmer.

 

Kindly help.

 

Thank you.



#4 Álvaro   Crossbones+   -  Reputation: 13662

Like
0Likes
Like

Posted 22 December 2012 - 09:32 AM

You can show me your code, but I can't promise I will find the time to look at it in detail. Hopefully C# is easy to read.



#5 ashish123   Members   -  Reputation: 166

Like
0Likes
Like

Posted 22 December 2012 - 10:15 AM

 
I hope my code is readable.
 
Basically I think that MoveExtractor and moveGeneration Methods are what should be analyzed.
 
MoveExtractor is method which will extract the moves from logical grouping using appropriate bitShifts and bitMasks. 
MoveGeneration is as usual.
 
Above are three main classes and heart of my code.
 
 


#6 ashish123   Members   -  Reputation: 166

Like
0Likes
Like

Posted 30 December 2012 - 02:50 AM

Hi again,

I have completed my move generation logic including the castling and promotions and have verified with the Perft Suite and found now defect in it.

Since you haven't replied back I assume that you are busy and didn't find time to review my code, however if there is any other reason like the code quality was not up to the mark or code was difficult to understand, please let me know so that I can make it the way it is easier for you to review and hence wont take much of your time.

 

This is a log that has been generated to give an idea how much time has been consumed in order to generate moves and so on.

http://pastebin.com/fJeFxuuh

 

Thanks.



#7 Álvaro   Crossbones+   -  Reputation: 13662

Like
0Likes
Like

Posted 30 December 2012 - 05:39 AM

I took a very brief look at it the day you posted it, and the only thing that I thought was odd is that you had code that checked the type of the captured piece by successively querying each bitboard to see if it is there. It would be better to have an array with the content of the board and keep it in parallel to the bitboard structure (see the "Hybrid Solutions" section here).

 

I find that semi-interpreted languages like C# make it harder to guess where the bottlenecks of performance are, and this is specially true for me, since I don't have any experience with the language.



#8 Álvaro   Crossbones+   -  Reputation: 13662

Like
0Likes
Like

Posted 30 December 2012 - 05:58 AM

One more thing: You can find many chess-programming experts in a more specialized forum, like this one. I point you there reluctantly, though, because a lot of the participants in that forum lack social skills and you often end up with strange wars that look more like intellectual pissing contests than legitimate attempts at helping people.



#9 ashish123   Members   -  Reputation: 166

Like
0Likes
Like

Posted 01 January 2013 - 12:44 AM

Hi thanks for replying. I have read great deal of high quality posts from that forum however as you pointed out, I have also read many more posts that turn off mood. Recently, I ran a profiler on code, where it highlights some hot-spots which take time. One of the major concern is while validating the moves. As per my code, I turn it into a super king and check if can capture opponents piece, this would mean that opponenet would be able to capture my king, hence a check. But since It involves all the regeneration again, it takes up lot of time. So I am working on this. I read on In-Between Look up on chessprograming wiki. But cannot imagine how the array or the way to think on it. Can you guide me on this. Is there any better way? One more important reason about me posting here is that you reply in simple language at a level which I can understand. However I am waiting for my membership to get approved there.

#10 Paradigm Shifter   Crossbones+   -  Reputation: 5410

Like
0Likes
Like

Posted 01 January 2013 - 09:44 AM

Have you not got a bit board of squares attacked by each side? You can use that to check squares that would cause your King to be in check.
"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#11 ashish123   Members   -  Reputation: 166

Like
0Likes
Like

Posted 01 January 2013 - 01:01 PM

Hi Paradigm Shifter,
Thanks for reply.

I planned to keep one say like WHITE_ATTACK_MAPS and so on.
and then update(OR them) the MAPS on move generation as they are the same.
now on second thought, I dont know how to update(XOR) them on make move method and update them back on unmake move.

I consider this scenario
5zcnq6e1n4lp.png
fen=4k3/8/8/5B2/6Q1/8/8/4K3

now g6 square is attacked by Bishop as well as Queen, so even if Queen or bishop moves(one at a time),g6 still remains under threat. So my plan to make or unmake the move fails. So I thought I might keep 12 bit boards and since I know the piece moving, I can just update that single bit board and so on...

would like to know whether this would give me speed up or not.

You can refer to the source code given in above links so that you can give more suggestions.

Thanks.

#12 Álvaro   Crossbones+   -  Reputation: 13662

Like
0Likes
Like

Posted 01 January 2013 - 05:10 PM

If you have never written a chess engine before, I think you should stop obsessing about performance at this stage and go on building your engine. Perft is a lousy proxy for engine performance anyway. You don't want to use a data structure that does great at perft but makes evaluation slow.

To first order, all questions about whether some technique will give you a speed up or not can only be answered by testing on your engine.

#13 ashish123   Members   -  Reputation: 166

Like
0Likes
Like

Posted 02 January 2013 - 09:37 AM

@Alvaro: Thanks for replying.

I have written two chess engines when I first began to code about year ago. 

Both were 0x88 based and I wasnt pleased with the performance I got from them (4 plys in about 4-5 mins).

The first one was horrible, it took 3 hours just to generate moves for 6 plys. later on I found that the bottle neck was the dynamic memory allocation.

The second one was quiet good but then my disk crashed and I lost the source. 

This is the third one, but my first one using bit boards.

 

My idea beyond making a fast perft was some thing like, "If I can get around 2MNPS in perft, they would trim down to 1.5 or 1 MNPS with the evaluation and decision making.

So the faster my perft is, it will help my program be faster."

 

So from your post I think I am heading the wrong way and attack boards would make my evaluation slow (but I cant see how)

 

please reply.

Thanks.



#14 Álvaro   Crossbones+   -  Reputation: 13662

Like
0Likes
Like

Posted 02 January 2013 - 10:20 AM

I have written two chess engines when I first began to code about year ago.

Both were 0x88 based and I wasnt pleased with the performance I got from them (4 plys in about 4-5 mins).

So you were getting 4 plys in 4 or 5 minutes, when it should have taken a fraction of a second. Then you must have decided that the problem was the board representation, but this is not correct. You can make 0x88-based engines that are really fast.
So from your post I think I am heading the wrong way and attack boards would make my evaluation slow (but I cant see how)
You are reading too much into my post. I was just pointing out that you are going about this the wrong way, and you shouldn't try to optimize the speed of perft. You should find out why your engine was taking minutes to reach 4 plys. Dynamic memory allocation is an obvious thing to get rid of, but I guess you were doing something else completely wrong.

#15 ashish123   Members   -  Reputation: 166

Like
0Likes
Like

Posted 02 January 2013 - 10:33 AM

I have written two chess engines when I first began to code about year ago.

Both were 0x88 based and I wasnt pleased with the performance I got from them (4 plys in about 4-5 mins).

So you were getting 4 plys in 4 or 5 minutes, when it should have taken a fraction of a second. Then you must have decided that the problem was the board representation, but this is not correct. You can make 0x88-based engines that are really fast.
So from your post I think I am heading the wrong way and attack boards would make my evaluation slow (but I cant see how)
You are reading too much into my post. I was just pointing out that you are going about this the wrong way, and you shouldn't try to optimize the speed of perft. You should find out why your engine was taking minutes to reach 4 plys. Dynamic memory allocation is an obvious thing to get rid of, but I guess you were doing something else completely wrong.

 

Yes, its just that I have lost the code, so as it is I was trying to code something new. I have never felt or mentioned that 0x88 engines are slow or something like that.

The main reason of shifting to bitboards was the thrill. The thrill in representing entire chess board in just one unsigned long. Another reason for myt 0x88 engine was slow because I scanned for material (looped the board) everytime, rather I could just keep count and so on.. 0x88 is an excellent scheme for representation (at first I was pleasantly surprised with the idea alone of sq&0x88.)

Ok then I think I should go on writing this as complete chess engine and then come back for optimization. 

 

PS: Its just that I am not schooled formally in computer, I developed liking for computers and studied through books like Introduction to Algorithms during spare time.

So there might me some issues with the way I think. I hope I am not asking too much.

 

Thanks.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS