Jump to content
  • Advertisement
Sign in to follow this  
Sagar_Indurkhya

Chess Engine Woes

This topic is 5406 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am having trouble with my chess engine. It can play chess, but I set it to look 7 moves deep, and it takes ~6min per turn. I am using Alpha Beta. It is in C++, and is pretty optimized. The moves it plays aren't so bad, it is just that it takes too long. I am not using a transposition table though. Does anyone know whether this is due to my engine flaw, or just bad optimization? The only data structures I store in my chessboard object is a 12x12 array of pointers to the 12 different types of chesspieces(I have true object orientation in here). I haven't used any move ordering, and have noticed that certain moves are faster than others. That proves that the alpha beta is working. Any suggestions are welcome! PS: I don't use bit boards.

Share this post


Link to post
Share on other sites
Advertisement
I just realized that I am such a dumbass! Ok, here is how I have been doing alpha beta:

0000_|_0000
000_|_|_000
00_3_2_1_00
00|0|0|0|00
00404040400

First I search all of 3. Then off the same branch, I search 3, 2, and 1. I don't think this is alpha beta. :)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
To control the time correctly, use iterative deepening (search depth 1, then 2, then 3... until you run out of time).

Some other things you should do (in order of importance):
- Use a quiescence search at the leaves.
- Order the captures in the quiescence search (try to capture big pieces first).
- Use some heuristics to sort the moves in the regular search: killer move, captures before non-captures, history heuristic.
- Implement transposition tables. They help a lot in the endgame, and they provide a good first move to try in many nodes.

Share this post


Link to post
Share on other sites
You need to improve your algorithms, not micro-optimize. The efficiency of the alpha-beta algorithm is very dependant upon move ordering and other enhancements such as the use of a transposition table, forward pruning, and so on.

Consider these (approximate, on average) cases.

A program using minimax will need to search over 64 billion nodes to complete a 7-ply search.

A program that uses alpha beta with random move ordering (which sounds like your situation) will need to search just over 16 million nodes to complete a 7-ply search.

A program with near perfect move ordering will need to search less than 300,000 nodes to complete a 7-ply search.

A program using a well enhanced algorithm (alpha beta based search, very good move ordering, transposition table, forward pruning, etc.) will need to search about 2200 nodes to perform a seven ply search.

In other words, it doesn't really matter how fast your program searches if it doesn't search efficiently. If I use a good algorithm and you use alpha beta with random move ordering, my program can be 7,000 times slower than your program and mine will still finish a 7-ply search before yours. Even if you could optimize your program to run 100 times faster than it currently does, it doesn't amount to a hill of beans if you don't search efficiently. Now do you think you can optimize your program to run 100 times faster? I doubt it, so focus on searching efficiently.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!