3

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!
Improve this question

2 Answers 2

Reset to default
3

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.
Improve this answer
7
  • 1
    Is this list ordered?
    – Federico Poloni
    Nov 4, 2022 at 11:58
  • @FedericoPoloni No, I'll add a note in for that.
    – Inertial Ignorance
    Nov 4, 2022 at 13:41
  • I should have posted my comment below as a response to you here instead, but alas. Just to reiterate, I was told on r/computerchess that transposition tables are very hard. What leads you to disagree (in the sense of saying they are "one of the easiest" things on the list)?
    – zack-overflow
    Nov 4, 2022 at 18:36
  • @zack-overflow From my experience, basically all you need is a hashing function (zobrist hashing: chessprogramming.org/Zobrist_Hashing). After you've done that, you can store each position in a hash table. Then it's just a matter of looking it up in the table for each node, to see if there's already a duplicate node that's been searched at a >= depth. Again though I only have experience implementing this for connect four, but in principle I don't see this being way harder to do in chess. Certainly easier compared to something like making an evaluation function for chess.
    – Inertial Ignorance
    Nov 4, 2022 at 18:46
  • Comparatively, move generation is one example of something that's way harder in chess compared to connect four. Still not really hard, but in connect four it's trivial. But as far as hashing goes, I don't see the properties of chess adding too much extra difficulty.
    – Inertial Ignorance
    Nov 4, 2022 at 18:51
2

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++.

Improve this answer
7
  • 3
    What is the probability that 5x-10x exceeds the speedup from, e.g., a transposition table or better move ordering?
    – zack-overflow
    Nov 3, 2022 at 16:42
  • 1
    @zack-overflow That speedup sounds somewhat comparable to the speedup a TT would give you. 5x-10x is probably more, I'd estimate a TT helps somewhere in the range of 2-5x. However, I'd imagine it would be easier for you to implement a TT than to switch languages.
    – Inertial Ignorance
    Nov 4, 2022 at 6:37
  • The big advantage of the suggestion is that this is relative straightforward to do (programs for that already exist) without even looking at the code. BTW, I rewrote some (smallish) scientific code handishly from Python to FORTRAN, which gave 20x-30x speedup.
    – Hauke Reddmann
    Nov 4, 2022 at 14:34
  • 1
    @zack-overflow: It might not be so straightforward after all when you need a computer-to-computer interface too (my code was standalone anyway). I don't speak C++ anyway. This might be helpful: cplusplus.com/forum/general/284690
    – Hauke Reddmann
    Nov 4, 2022 at 21:19
  • 1
    @zack-overflow: BTW, a conversion to FORTRAN seems more "natural" (Python has more similarities with it...if you program more imperative than object-oriented style, that is, my 30 years of FORTRAN show :-) and here is a GitHub project: fortran-lang.discourse.group/t/…
    – Hauke Reddmann
    Nov 4, 2022 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.