Making program run faster?

Question

I m trying to write a chess engine on Python for fun, but a major problem I ve run across is how slow the program runs. I d like to get my program to look further ahead than one move, but the number of possible combinations is so huge that it would be impossible given how slow my program runs just looking ahead one move. The best chess engines seem to look ahead many moves almost instantaneously.

I ve tried to make some optimizations by lowering read/write memory accesses, and I ve noticed that my program runs A LOT faster on my desktop computer than my laptop, but it s still taking a long time.

What are some good general ideas for how to make my program run faster? Thanks.

Answer 1

Most chess programs or similar have a database to look up data. But it also depends on how you are storing the data of existing moves.

Answer 2

It will need more optimization, not just in input/output but also in your chess engine algorithm! Or another reason can be laptop's processor and RAM!

Answer 3

You could use Minimax Algorithm with Alpha-Beta Pruning to help move things along.

Recognize how many possible moves can be made in a given configuration and evaluate only those moves in a way that 'worse options' can be ignored entirely with the AB-Pruning.



Some positions may allow for only 4 or so moves whereas others may go as high as 100+ possible moves depending on the state of the game. Chess is interesting because it has such a varying branching factor.



If you also have a timer for a 'max time to make a move' and use a clever implementation then depending on your luck it should be able to look ahead 5-8 turns though worst case behavior will trend towards 2-3.



The asymptotic behavior kicks in extremely quickly so you might get 1-2 extra moves with a compiled language.



Of course I immediately think of this as an AI problem so you'll have to excuse me if you want to avoid that sort of approach. : >

Answer 4

It's hard for us to know what you can do if we don't know what you are doing. We can't see your code.



Writing it in something other than Python might help, yes. Java is normally faster than Python, and C is normally faster than Java.



The order of certain operations can be important. You don't want to evaluate the position after Ne5, and then when that is done find out that Ne5 is illegal because it puts your own king in check. It's way more efficient to first calculate the legal moves, and then evaluate the position of only those moves. That example is fairly obvious, but there might be similar less-obvious code bits that you can rearrange.



Take a hard look at anything that runs in a loop, and especially in a nested loop, to see if it can be simplified. If there's anything that you're doing inside a loop that can instead be done outside the loop, you can save a lot of processing.

Answer 5

Most chess programs or similar have a database to look up data. But it also depends on how you are storing the data of existing moves.

Answer 6

You should choose a language other than python to do this in. A Script based language is not the best for this type of program.



They use Supercomputers with tetra flops (and even peta flops) to do this type of thing and using a highly optimized code (http://chess.stackexchange.com/questions/8117/how-many-positions-per-second-can-a-modern-supercomputer-calculate) so the code/language is the issue and not the computer.



Good luck with your 'fun' project.