Chess Engine Woes
Author
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.
Author
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. :)
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. :)
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.
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.
move ordering is very important. in my engine disabling move ordering can increase time by a factor 30x and sometimes even more.
check this tread.
check this tread.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement