Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-04T11:58:56.150Z
Answers.Text: Is this list ordered?
Answers.UserDisplayName: Federico Poloni
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-04T13:41:06.367Z
Answers.Text: @FedericoPoloni No, I'll add a note in for that.
Answers.UserDisplayName: Inertial Ignorance
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-04T18:36:33.437Z
Answers.Text: I should have posted [my comment below](https://chess.stackexchange.com/questions/40917/comparative-advantage-of-engine-improvements#comment66767_40922) as a response to you here instead, but alas. Just to reiterate, [I was told](https://www.reddit.com/r/ComputerChess/comments/yln9ef/comment/iv1pky1/?utm_source=share&utm_medium=web2x&context=3) 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)?
Answers.UserDisplayName: zack-overflow
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-04T18:46:56.373Z
Answers.Text: @zack-overflow From my experience, basically all you need is a hashing function (zobrist hashing: https://www.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.
Answers.UserDisplayName: Inertial Ignorance
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-04T18:51:00.003Z
Answers.Text: 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.
Answers.UserDisplayName: Inertial Ignorance
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-05T04:54:07.720Z
Answers.Text: @InertialIgnorance I think I understand it a little better now--the idea is that it is relatively "easy" to generate hashes (still not a small feat), but prohibitively difficult to generate hashes in a way that is _perfectly efficient_ since the optimal apparently requires taking the hash of the previous board state and doing some bitwise operations to get the new hash instead of generating it from scratch. Does that seem right?
Answers.UserDisplayName: zack-overflow
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-05T16:57:47.213Z
Answers.Text: @zack-overflow Yes from my recollection that sounds about right.
Answers.UserDisplayName: Inertial Ignorance
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-04T06:50:48.733Z
Answers.LastActivityDate: 2022-11-04T13:41:25.770Z
Answers.LastEditDate: 2022-11-04T13:41:25.770Z
Answers.UserDisplayName: Inertial Ignorance
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-03T16:42:20.463Z
Answers.Text: What is the probability that 5x-10x exceeds the speedup from, e.g., a transposition table or better move ordering?
Answers.UserDisplayName: zack-overflow
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-04T06:37:51.560Z
Answers.Text: @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.
Answers.UserDisplayName: Inertial Ignorance
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-04T14:34:53.280Z
Answers.Text: 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.
Answers.UserDisplayName: Hauke Reddmann
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-04T18:28:04.923Z
Answers.Text: @HaukeReddmann Amazing speedup--wish I knew FORTRAN. Would it be possible for you to elaborate on the "relatively straightforward" nature of extending to c++. Something I forgot to include is that there is a requirement that the program has an external interface written in python so that it can play other engines (also written in python). I am somewhat experienced with python/C, but still a student. Is it still "straightforward" to have a project with some C or C++ and some python? What is the best way to call the C++ functions if the board is stored as a python object?
Answers.UserDisplayName: zack-overflow
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-04T18:32:19.090Z
Answers.Text: @InertialIgnorance I also posted a similar question in r/computerchess on Reddit and was actually told (to my surprise) that it is extremely difficult to implement a TT because of the need to efficiently calculate changes in board Zobrist hash values--maybe that's something I want to avoid. Do you know of well-regarded packages/public code that does this? Would calculating the hashes from scratch every time instead of monitoring the incremental changes be worse than having no TT at all?
Answers.UserDisplayName: zack-overflow
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-04T21:19:06.893Z
Answers.Text: @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: https://cplusplus.com/forum/general/284690/
Answers.UserDisplayName: Hauke Reddmann
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-04T21:24:22.877Z
Answers.Text: @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: https://fortran-lang.discourse.group/t/translating-python-to-fortran-with-pyccel/503
Answers.UserDisplayName: Hauke Reddmann
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-03T16:15:23.263Z
Answers.LastActivityDate: 2022-11-03T16:15:23.263Z
Answers.UserDisplayName: Kevin Wang
Body: <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>
  
Tags: <engines><programming>
Title: Comparative Advantage of Engine Improvements
ThreadText: # Comparative Advantage of Engine Improvements
  
  (Asked by: username_0 on 2022-11-03)
  
  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!
  
  **Tags:** engines, programming
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2022-11-04. Score: 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.
  
  > **Comments:**
  > **username_2**: Is this list ordered?  
  > **username_1**: @FedericoPoloni No, I'll add a note in for that.  
  > **username_0**: I should have posted [my comment below](https://chess.stackexchange.com/questions/40917/comparative-advantage-of-engine-improvements#comment66767_40922) as a response to you here instead, but alas. Just to reiterate, [I was told](https://www.reddit.com/r/ComputerChess/comments/yln9ef/comment/iv1pky1/?utm_source=share&utm_medium=web2x&context=3) 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)?  
  > **username_1**: @username_0 From my experience, basically all you need is a hashing function (zobrist hashing: https://www.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.  
  > **username_1**: 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.  
  > **username_0**: @InertialIgnorance I think I understand it a little better now--the idea is that it is relatively "easy" to generate hashes (still not a small feat), but prohibitively difficult to generate hashes in a way that is _perfectly efficient_ since the optimal apparently requires taking the hash of the previous board state and doing some bitwise operations to get the new hash instead of generating it from scratch. Does that seem right?  
  > **username_1**: @username_0 Yes from my recollection that sounds about right.  
  
  ---
  
  ### Answer by username_3 on 2022-11-03. Score: 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++.
  
  > **Comments:**
  > **username_0**: What is the probability that 5x-10x exceeds the speedup from, e.g., a transposition table or better move ordering?  
  > **username_1**: @username_0 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.  
  > **username_4**: 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.  
  > **username_0**: @HaukeReddmann Amazing speedup--wish I knew FORTRAN. Would it be possible for you to elaborate on the "relatively straightforward" nature of extending to c++. Something I forgot to include is that there is a requirement that the program has an external interface written in python so that it can play other engines (also written in python). I am somewhat experienced with python/C, but still a student. Is it still "straightforward" to have a project with some C or C++ and some python? What is the best way to call the C++ functions if the board is stored as a python object?  
  > **username_0**: @InertialIgnorance I also posted a similar question in r/computerchess on Reddit and was actually told (to my surprise) that it is extremely difficult to implement a TT because of the need to efficiently calculate changes in board Zobrist hash values--maybe that's something I want to avoid. Do you know of well-regarded packages/public code that does this? Would calculating the hashes from scratch every time instead of monitoring the incremental changes be worse than having no TT at all?  
  > **username_4**: @username_0: 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: https://cplusplus.com/forum/general/284690/  
  > **username_4**: @username_0: 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: https://fortran-lang.discourse.group/t/translating-python-to-fortran-with-pyccel/503  
  
  ---
  
  