user33582: I am implementing a chess engine in Python for the first time. Right now, my engine uses a standard alpha-beta search with fixed depth and a simple evaluation function that uses the weighted average of material for both sides. I have access to multiple cores, but I have not implemented any parallelization yet. I unfortunately have a limited time (just over a week) to make improvements before high stakes matches against a human and other engines. I've done a fair amount of research on engines, but I am not sure where to start in terms of making changes that actually improve the engine's strength. Which set of the following improvements might give me the best return on investment?

Smarter move ordering for alpha-beta based on iterative deepening; this is pretty much a given
Better evaluation function (piece-square table, time, other positional considerations)
Naive parallelization (running minimax where each parallel search explore one path from the root at a time--this would not allow alpha-beta pruning)
Search improvements (simple iterative deepening/aspiration windows, killer moves)
Different search algorithm (PVS, MTD, Lazy SMP, YBW)
Managing time and determining search depth dynamically (the game will be a blitz game)
Transposition table
Using opening books
Porting the python code to c++
Something else!


user21424: If your code is doing the bulk of its work in python, you can probably get a 5x or 10x speedup by porting to C++.

user12873: Caveat: my experience with minimax engines involves coding a Connect Four engine over a few years, and working a bit with Stockfish (partly as a user, partly with the code). I haven't actually coded a chess engine by myself. That said, I'd recommend the following (not in any particular order, though some features enable others):

As Kevin said, C++ should give you a big speedup.
A transposition table seems like one of the easiest things to do on your list, and it should give you a good speedup.
Managing time definitely seems good, especially if it will be a blitz game.
For determining the search depth, I'd recommend iterative deepening search. This will help you with a few things:

Dynamic time/search depth management (after each iterative deepening step, you can just check if a certain time has been exceeded; if so, stop searching and make a move).
Move ordering. The data you get from a depth n search can then inform your engine on which moves to consider first in the depth n+1 search. For this, the transposition table would be helpful and needed. For the info you store in the TT for each node, you could also store (in addition to the evaluation) which moves the engine currently thinks are best, in order. This can be used and updated by future nodes at higher iterative deepening stages.




33582: <p>I am implementing a chess engine in Python for the first time. Right now, my engine uses a standard alpha-beta search with fixed depth and a simple evaluation function that uses the weighted average of material for both sides. I have access to multiple cores, but I have not implemented any parallelization yet. I unfortunately have a limited time (just over a week) to make improvements before high stakes matches against a human and other engines. I've done a fair amount of research on engines, but I am not sure where to start in terms of making changes that actually improve the engine's strength. Which set of the following improvements might give me the best return on investment?</p>
<ul>
<li>Smarter move ordering for alpha-beta based on iterative deepening; <em>this is pretty much a given</em></li>
<li>Better evaluation function (piece-square table, time, other positional considerations)</li>
<li>Naive parallelization (running minimax where each parallel search explore one path from the root at a time--this would not allow alpha-beta pruning)</li>
<li>Search improvements (simple iterative deepening/aspiration windows, killer moves)</li>
<li>Different search algorithm (PVS, MTD, Lazy SMP, YBW)</li>
<li>Managing time and determining search depth dynamically (the game will be a blitz game)</li>
<li>Transposition table</li>
<li>Using opening books</li>
<li>Porting the python code to c++</li>
<li>Something else!</li>
</ul>
 21424: <p>If your code is doing the bulk of its work in python, you can probably get a 5x or 10x speedup by porting to C++.</p>
 12873: <p>Caveat: my experience with minimax engines involves coding a Connect Four engine over a few years, and working a bit with Stockfish (partly as a user, partly with the code). I haven't actually coded a chess engine by myself. That said, I'd recommend the following (not in any particular order, though some features enable others):</p>
<ul>
<li>As Kevin said, C++ should give you a big speedup.</li>
<li>A transposition table seems like one of the easiest things to do on your list, and it should give you a good speedup.</li>
<li>Managing time definitely seems good, especially if it will be a blitz game.</li>
<li>For determining the search depth, I'd recommend iterative deepening search. This will help you with a few things:
<ul>
<li>Dynamic time/search depth management (after each iterative deepening step, you can just check if a certain time has been exceeded; if so, stop searching and make a move).</li>
<li>Move ordering. The data you get from a depth n search can then inform your engine on which moves to consider first in the depth n+1 search. For this, the transposition table would be helpful and needed. For the info you store in the TT for each node, you could also store (in addition to the evaluation) which moves the engine currently thinks are best, in order. This can be used and updated by future nodes at higher iterative deepening stages.</li>
</ul>
</li>
</ul>
