Body: <p>I have developed a chess engine with these features:</p>
  <ul>
  <li>alpha beta</li>
  <li>transposition tables</li>
  <li>iterative deepening</li>
  <li>use any prev result from transposition table as first move if the result cannot be used directly, e.g cutoffs or not deep enough.</li>
  </ul>
  <p>The alpha beta algorithm is implemented so that check if calculated in each new node, then the legal moves are calculated progressively so that a cutoff will end new legal moves from being calculated. If no legal moves are found, it is either checkmate or stalemate depending on the previously calculated check.</p>
  <p>The algorithm work logic wise as confirmed by letting it play against itself on different depths. Deeper versions bet more shallow ones at least 95% of the time, otherwise it's draw.</p>
  <p>The problem is speed. On a standard computer I get these times per move (in seconds) for different depths:</p>
  <p>{1: 0.0034837227599999986,
  2: 0.013043862759999995,
  3: 0.24758806587999999,
  4: 1.7778337413599996,
  5: 17.16384055096,
  6: 70.89946676716}</p>
  <p>I know that in ideal cases this grows as n**(d/2) where d is the depth and n is nr moves. Worst case is n**d.</p>
  <p>So I fit a curve to match t+1=n**(alpha*d) where alpha is unknown. This gives alpha 0.17 which is less than 0.5 and not expected. Probably the number of values are too small to give an accurate estimate. But it's already taking more than a minute on depth 6!
  Should this be the case? I was expecting to be able to run to at least a depth of 10-15..</p>
  <p><strong>UPDATE</strong></p>
  <p>Here is data showing the performance of 3 different settings of the engine:</p>
  <p>1.Plain alpha beta. No transpositions nor any move ordering</p>
  <p>['depth', 'nstates', 'time/state', 'hits']<br />
  [5, 634505, 0.00032971293255529906, 0]</p>
  <p>['depth', 'hits', 'cutoffs']<br />
  [1, 0, 43]<br />
  [2, 0, 135]<br />
  [3, 0, 6077]<br />
  [4, 0, 22345]<br />
  [5, 0, 0]</p>
  <p>2.Alpha beta with transpositions</p>
  <p>['depth', 'nstates', 'time/state', 'hits']<br />
  [5, 508015, 0.00017707277515624539, 159165]</p>
  <p>['depth', 'hits', 'cutoffs']<br />
  [1, 0, 43]<br />
  [2, 0, 135]<br />
  [3, 1164, 4915]<br />
  [4, 2880, 18179]<br />
  [5, 155121, 0]</p>
  <p>3.Alpha beta with transpositions and use best move in transpositions as first move</p>
  <p>['depth', 'nstates', 'time/state', 'hits']<br />
  [5, 507076, 0.00020099950737759227, 158794]</p>
  <p>['depth', 'hits', 'cutoffs']<br />
  [1, 0, 43]<br />
  [2, 0, 135]<br />
  [3, 1150, 4910]<br />
  [4, 2868, 18123]<br />
  [5, 154776, 0]</p>
  <p>*nstates is the number of nodes traversed
  *time/state is the average time in seconds spent in each node</p>
  <p>So start counting depth at 0 for the single top node, the fastest version above (3) takes over a minute on depth 5. I tried to run for depth 6 and it took about 10 times longer. Is this normal? Are the values above normal?</p>
  <p>Observe, I'm not using bitboards yet! Not sure how much faster that will make it, but I'm in doubts.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-08-17T20:04:56.843Z
Comments.Text: Can you post for reference how fast your plain alpha beta algorithm is? And maybe also not just times but node counts as well.
  A well implemented basic engine with these features should certainly be able to reach depth 8 or 9 within a minute, not just depth 6.
Comments.UserDisplayName: koedem
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-05T07:45:39.173Z
Comments.Text: @koedem please see update above with performance data
Comments.UserDisplayName: user2908112
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-05T09:09:23.607Z
Comments.Text: Is this for the start position? I think the node counts look a bit high for that, but that might be due to no move ordering. One thing that is definitely slow is the time/state (usually states are called nodes in graph algorithm contexts like chess) or rather the more commonly used inverse nodes/second. Those are less than 10k/second if I read this right? Usually you would expect that in the millions, but maybe you are using a language like python or similar?
Comments.UserDisplayName: koedem
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-05T09:13:11.207Z
Comments.Text: I am also a bit confused about the cutoffs column. Why are there 43 cutoffs at depth 1 already but none at depth 5? Possibly the values are misaligned by one row?
Comments.UserDisplayName: koedem
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-06T10:51:22.887Z
Comments.Text: @koedem At depth 5 there are no child nodes, they are leaf nodes, why there are no cutoffs. The cutoffs are shown for the nodes that break the loop of their child nodes.
Comments.UserDisplayName: user2908112
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-06T10:56:16.837Z
Comments.Text: @koedem You are right, this is not the starting position, it's as random position in the middle of a game, with fen "rn2kb1r/pp3ppp/2ppbn2/1N3q2/3P1p2/3QPNPB/PPP4P/R1B1K2R w KQkq - 0 10".
Comments.UserDisplayName: user2908112
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-06T10:58:34.547Z
Comments.Text: @koedem You are right, it's just less than 10K/s. I use Python, but I try to write it in an effective way. Would it really be 100 times faster with another language?
Comments.UserDisplayName: user2908112
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-06T21:29:50.193Z
Comments.Text: I don't use Python so take this with a grain of salt, but I wouldn't be surprised. Python is interpreted so for stuff like this it can definitely be orders of magnitude slower. A state of the art chess engine with a minimal evaluation function can probably get around 10 MN/s, so a factor 1000 faster. A "basic" chess engine that doesn't use any fancy tricks can probably get 1-2 MN/s when written in C++.
Comments.UserDisplayName: koedem
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-06T21:31:27.780Z
Comments.Text: With this in mind, I think the performance is not unreasonable. You can of course try to make things more efficient but I don't think there's necessarily a "bug" or anything like that, holding back performance. But there is a reason why almost no chess engines are written in Python and the big majority are written in a C based language.
Comments.UserDisplayName: koedem
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-17T09:57:27.870Z
Comments.Text: @koedem Thanks for that. I've read a bit about this now and I realize that Python is probably the biggest cause to the problem. I'll try to make it as fast as possible for python, then probably shift to C.
Comments.UserDisplayName: user2908112
Tags: <transpositions><performance>
Title: Iterative deepening speed expectation
ThreadText: # Iterative deepening speed expectation
  
  (Asked by: username_0 on 2023-06-01)
  
  I have developed a chess engine with these features:
  
  * alpha beta
  * transposition tables
  * iterative deepening
  * use any prev result from transposition table as first move if the result cannot be used directly, e.g cutoffs or not deep enough.
  
  The alpha beta algorithm is implemented so that check if calculated in each new node, then the legal moves are calculated progressively so that a cutoff will end new legal moves from being calculated. If no legal moves are found, it is either checkmate or stalemate depending on the previously calculated check.
  
  The algorithm work logic wise as confirmed by letting it play against itself on different depths. Deeper versions bet more shallow ones at least 95% of the time, otherwise it's draw.
  
  The problem is speed. On a standard computer I get these times per move (in seconds) for different depths:
  
  {1: 0.0034837227599999986,
  2: 0.013043862759999995,
  3: 0.24758806587999999,
  4: 1.7778337413599996,
  5: 17.16384055096,
  6: 70.89946676716}
  
  I know that in ideal cases this grows as n\*\*(d/2) where d is the depth and n is nr moves. Worst case is n\*\*d.
  
  So I fit a curve to match t+1=n\*\*(alpha\*d) where alpha is unknown. This gives alpha 0.17 which is less than 0.5 and not expected. Probably the number of values are too small to give an accurate estimate. But it's already taking more than a minute on depth 6!
  Should this be the case? I was expecting to be able to run to at least a depth of 10-15..
  
  **UPDATE**
  
  Here is data showing the performance of 3 different settings of the engine:
  
  1.Plain alpha beta. No transpositions nor any move ordering
  
  ['depth', 'nstates', 'time/state', 'hits']  
  [5, 634505, 0.00032971293255529906, 0]
  
  ['depth', 'hits', 'cutoffs']  
  [1, 0, 43]  
  [2, 0, 135]  
  [3, 0, 6077]  
  [4, 0, 22345]  
  [5, 0, 0]
  
  2.Alpha beta with transpositions
  
  ['depth', 'nstates', 'time/state', 'hits']  
  [5, 508015, 0.00017707277515624539, 159165]
  
  ['depth', 'hits', 'cutoffs']  
  [1, 0, 43]  
  [2, 0, 135]  
  [3, 1164, 4915]  
  [4, 2880, 18179]  
  [5, 155121, 0]
  
  3.Alpha beta with transpositions and use best move in transpositions as first move
  
  ['depth', 'nstates', 'time/state', 'hits']  
  [5, 507076, 0.00020099950737759227, 158794]
  
  ['depth', 'hits', 'cutoffs']  
  [1, 0, 43]  
  [2, 0, 135]  
  [3, 1150, 4910]  
  [4, 2868, 18123]  
  [5, 154776, 0]
  
  \*nstates is the number of nodes traversed
  \*time/state is the average time in seconds spent in each node
  
  So start counting depth at 0 for the single top node, the fastest version above (3) takes over a minute on depth 5. I tried to run for depth 6 and it took about 10 times longer. Is this normal? Are the values above normal?
  
  Observe, I'm not using bitboards yet! Not sure how much faster that will make it, but I'm in doubts.
  
  **Tags:** transpositions, performance
  
  > **Comments:**
  > **username_1**: Can you post for reference how fast your plain alpha beta algorithm is? And maybe also not just times but node counts as well. A well implemented basic engine with these features should certainly be able to reach depth 8 or 9 within a minute, not just depth 6.  
  > **username_0**: @username_1 please see update above with performance data  
  > **username_1**: Is this for the start position? I think the node counts look a bit high for that, but that might be due to no move ordering. One thing that is definitely slow is the time/state (usually states are called nodes in graph algorithm contexts like chess) or rather the more commonly used inverse nodes/second. Those are less than 10k/second if I read this right? Usually you would expect that in the millions, but maybe you are using a language like python or similar?  
  > **username_1**: I am also a bit confused about the cutoffs column. Why are there 43 cutoffs at depth 1 already but none at depth 5? Possibly the values are misaligned by one row?  
  > **username_0**: @username_1 At depth 5 there are no child nodes, they are leaf nodes, why there are no cutoffs. The cutoffs are shown for the nodes that break the loop of their child nodes.  
  > **username_0**: @username_1 You are right, this is not the starting position, it's as random position in the middle of a game, with fen "rn2kb1r/pp3ppp/2ppbn2/1N3q2/3P1p2/3QPNPB/PPP4P/R1B1K2R w KQkq - 0 10".  
  > **username_0**: @username_1 You are right, it's just less than 10K/s. I use Python, but I try to write it in an effective way. Would it really be 100 times faster with another language?  
  > **username_1**: I don't use Python so take this with a grain of salt, but I wouldn't be surprised. Python is interpreted so for stuff like this it can definitely be orders of magnitude slower. A state of the art chess engine with a minimal evaluation function can probably get around 10 MN/s, so a factor 1000 faster. A "basic" chess engine that doesn't use any fancy tricks can probably get 1-2 MN/s when written in C++.  
  > **username_1**: With this in mind, I think the performance is not unreasonable. You can of course try to make things more efficient but I don't think there's necessarily a "bug" or anything like that, holding back performance. But there is a reason why almost no chess engines are written in Python and the big majority are written in a C based language.  
  > **username_0**: @username_1 Thanks for that. I've read a bit about this now and I realize that Python is probably the biggest cause to the problem. I'll try to make it as fast as possible for python, then probably shift to C.  
  
  ---
  
  ## 0 answers
  
  