Chess programming, help please!

[Pravesh Koirala]

So I've been writing this small chess program for my college project with my friends. And I am pretty much finished with other tasks like move generation and minimax. And the game runs fine too. But I've limited the search to depth of two. So now when I increase its depth to 4 (or even 3), the game really slows down.

For depth = 2, time = 1s
For depth = 3, time = 10s
For depth = 4, time = 25s
For depth = 5, Stopped observing after time = 3 min
and lets not talk for depth = 6.

I HAVE IMPLEMENTED THE APLHA BETA PRUNING!
I haven't read about it in detail, but I do have a general idea. So, I've implemented this psuedocode from wikipedia.
http://en.wikipedia.org/wiki/Alpha-beta_pruning#Pseudocode
.
I'm fairly new to chess programming. So I wanted to know if the taken time is normal for a program running on an i5 system, or the psuedocode is lacking (highly unlikely), or my code sucks. My Evaluation function is EXTREMELY basic, just assigning weights to the pieces and returning the final sum.
.
Any advice will be appreciated.

[liquidfuzz]

How about timing different steps in your algorithm..? If you do, it would be interesting to know what bottle necks you found.

[Pravesh Koirala]

Hmm.. timing you say. Well okay. So I think I will do that. I'm thinking of timing move generation and evaluation function. Any other recommendations?

[therockon7throw]

What do indicate depth and time? Why do you need a second param, time ?

[Pravesh Koirala]

therockon7throw, I didn't understand what you said, what I said is that I'm thinking of recording time taken for move generation and evaluation function.

[Pravesh Koirala]

Here are some findings for depth = 3. Here are the time taken by computer for two different moves. (With ALPHA BETA)

Entering GetScore function
Start time = 2680
Evaluation function took total of 63 ms
Move Generation function took total of 12487 ms
End time = 15262
Total time taken = 12582

Entering GetScore function
Start time = 17841
Evaluation function took total of 62 ms
Move Generation function took total of 15604 ms
End time = 33536
Total time taken = 15695


Here are findings for the same moves. This time WITHOUT Alpha beta

Entering GetScore function
Start time = 3166
Evaluation function took total of 215 ms
Move Generation function took total of 21343 ms
End time = 24809
Total time taken = 21643

Entering GetScore function
Start time = 27854
Evaluation function took total of 227 ms
Move Generation function took total of 26484 ms
End time = 54664
Total time taken = 26810

Hmm.. So alpha beta IS doing its work. But the move generation's still bottlenecking the system. Hmm..


EDIT:
So after finding out that the problem was with my Move Generation system. I edited my code and made it clean and these are the new results (with ALPHA BETA,, oh wait, WITHOUT ALPHA BETA?!?!?) AND ON DEPTH 5!!

Entering GetScore function
Start time = 3355
Evaluation function took total of 149 ms
Move Generation function took total of 650 ms
End time = 4234
Total time taken = 879

Entering GetScore function
Start time = 7385
Evaluation function took total of 194 ms
Move Generation function took total of 833 ms
End time = 8502
Total time taken = 1117

EDIT:
Oops, in my excitation, I saw it wrong. The result above was for depth 3. Sorry! But its still a huge improvement over 13 seconds. But I still need some more power.

[therockon7throw]

I've not programmed any chess game yet, however I would not tell the computer to find the best move in a pre-defined time-line. Instead I would tell the Computer to find the best move in all possible n next movement.

In other words, let the depth be 6, so I would tell the Computer to find the best move by computing all possible next 6 movements, it does not matter how much it takes the Computer to find the move. It is just my way :-)

[Gaminic]

The only thing I remember from chess algorithms is the Killer Heuristic for pruning search trees. No idea if it's useful for you, but it's simple enough to give it a try.

http://en.wikipedia.org/wiki/Killer_heuristic

[Pravesh Koirala]

@therockon7throw, well that's what most of us do. Since you mentioned that you haven't yet programmed chess, I suggest you do so. You'll have fun doing so, trust me. And in addition, you'll learn lots of things about game trees, minimax, move generation and etcs.

EDIT:
But the time really increases once you start to go up the depth. No one can search more than say 15 or 20 depths with even advanced heuristics. You don't want someone to wait 1 years for his turn now, do you?

[therockon7throw]

@Pravesh Koirala
I may try it, not in C++, but in Java, because it is easier and faster to develop such things :-)

[Pravesh Koirala]

@therockon7throw
Good luck then!

@gaminic
well, seems good I will try looking at it.

[liquidfuzz]

I don't follow your time tracking... Easiest way:
startTime
function()
endTime

executionTime = endTime - startTime;

Time every little thing, if you find it hard to see what might case lag.
bad calculations
communication
$-loss

If you're sure it's moveGeneration() that is messing about, time stuff in it. Different runs/different params.

[b2ee]

Which platform are you in? If possible, try to use gprof to evaluate the timing. The result would be more accurate and specific.

b2ee

[Gaminic]

@therockon7throw: I've never done it, but someone I trust on the matter suggests against traversing decision trees in Java.

http://strawberrycowbear.blogspot.com/2011/02/why-java-sucks-for-game-development.html