2

If we created a very powerful supercomputer (as powerful as the current most powerful supercomputers) which was only designed to find forced mates, how many positions could it calculate per second?

I only need an approximation. And remember, the computer doesn't waste time evaluating every single positions (like normal engines do); it just calculates as far as he can until he finds a forced mate (if there is any).

I tried to find the answer to the question myself, but I'm not sure at all if my conclusion is correct. So what follows may be wrong.

  • I found that the supercomputer Deep Blue "was capable of evaluating 200 million positions per second" (from Wikipedia).
  • But Deep Blue was old, supercomputers have became much more powerful since 1997, and Deep Blue wasted time evaluating every positions.
  • Therefore 200 million is only a lower bound for the answer to this question.

Since Deep Blue had a performance of 11.38 GFLOPS, and the current most powerful supercomputer (Tianhe-2) has a performance of 33.86 PFLOPS = 33 860 000 GFLOPS, we could estimate that the answer would be closer to 200 000 000 * 33 900 000 / 11.38 = 6 * 10^14 = 600 trillion positions per second. That seems like a lot, but taking into account that in average a position has around 35 legal moves, given 3 minutes such a computer would only be able to calculate every single positions up to a depth of 11 plies. Since Deep Blue wasted time evaluating every single of those 200 million positions per second, I believe Deep Blue should have been able to calculate approximately a billion positions per second if it didn't have to evaluate them.

So the true answer to the question is probably closer to 3 * 10^15 = 3 quadrillion positions per second. That's still not much: given 30 seconds it would just be able to calculate everything up to a depth of 11 plies. Even given an entire year it would only be able to calculate every positions up to a depth of 15 plies.

  • So the question is "how many positions can a supercomputer generate per second"? What about transpositions; do those count? Even without doing any evaluation, it's likely somewhat dependent on how many pieces are on the "starting" board: does it start from the beginning position, or something else? I think this question would benefit from some rewording; I'm not totally sure what it is that you're asking. – Henry Keiter Dec 16 '14 at 17:59
  • @Henry Keiter: I don't think the answer really depends on the "starting board". But we could say that the starting board is some position in the middlegame around move 20. As for transpositions, yes they do count obviously (remember that the supercomputer in the question doesn't evaluate the positions, so no time is lost evaluating positions which are just transpositions of some other positions already previously evaluated). – Fate Dec 16 '14 at 18:19
  • @Petrosian If the goal is to find a forced mate, then every position does not have to be searched - you can use alpha-beta to reduce the tree. Transpositions are not only about evaluating single positions: if you are searching 10 plies deep starting from the initial position, and you have searched the position after 1.a3 a6 2.b3 seven plies deep, then searching the position after 1.b3 a6 2.a3 7 plies deep would repeat previously done work. – JiK Dec 16 '14 at 18:34
  • Also, when using alpha-beta, evaluating positions might improve move-ordering when depth is high enough, and thus decrease the time needed for finding a mate in N moves from a given position. – JiK Dec 16 '14 at 18:36
  • 1
    Chess programs do not use floating point operations, so any comparison based on FLOPS (floating point operations) is meaningless. – RemcoGerlich Dec 16 '14 at 19:46
5

To answer the question in the title: In chess programming, perft is used for debugging move generators and testing their performance: the goal is simply to calculate the number of possible ways the game could continue until a mate or a stalemate for the next N moves. Modern engines give around 10-100 million nodes per second using one core of a modern processor. This program apparently searches 20 billion nodes per second using a modern GPU instead of a CPU.


However, as I said in the comments, searching for a mate in N moves is very different than searching all possible moves until that depth. The following observation is the heart of alpha-beta pruning: for example, if you have found that after 6.Nc3 Qxb4 7.Nd3 white can mate, there's no need to see what happens after 6.Nc3 Qxb4 7.a4.

Another, perhaps more likely example: You have found that the position after 5.e3 is drawn, and then find out that 5.e4 Qc7 gives a draw, too. Now we already know that the position before 5.e4 is at least a draw for white, and find out that the position after 5.e4 cannot be a win for white. Because it does not matter whether white draws or loses after 5.e4, we don't have to see what happens after 5.e4 Qb6.

As you probably can see, move ordering is critical here: it is beneficial to search best moves first. In fact, with perfect move-ordering, alpha-beta can reduce the number of searched nodes to approximately square root of the original value. So with perfect move-ordering, the number of positions needed to search for mate in 10 plies would be 35^5, not 35^10. But to get a good move ordering, one needs to do something else than just generate moves: perhaps evaluate the intermediate positions to get a good hint of the values of the moves. Of course, for the search of mate in, say, 20 plies, the best evaluator function would probably be different than what is used in engines designed to play a full game of chess.

  • I think the statement that alpha-beta related to forced mate is wrong. You DO have to continue search once you've found the mate. I don't have space here to elaborate as a comment, but please read talkchess.com/forum/… , in particular what Hyatt wrote. – SmallChess Dec 17 '14 at 5:31
  • @StudentT That occurs when using hash tables and other extensions which cause the actual search depth of different branches of the tree to vary; we are not doing them here. – JiK Dec 17 '14 at 7:03
0

Since another user already commented on alpha-beta and the importance of good heuristics for move ordering, I will focus on a different aspect of your question.

You specifically asked about forced mates rather than general board position evaluation, which makes the question somewhat easier to answer because it does not depend on the strength and cost of some evaluation function heuristic.

There is a family of related tree search algorithms collectively known as PN or proof number search (distant cousins of the general alpha-beta pruned search) which are particularly efficient at solving binary subproblems in computer games, such as whether or not there is a forced mate in <=N moves in chess (rather than the more abstract question of which board position is "better"). The algorithm proceeds by visiting each node and trying to either prove or disprove the initial query by checking which conditions must be satisfied for that branch to contain a solution (or a countersolution) and evaluating them in a "good" order such that proof failures can be detected early. The search quits as soon as it finds the first solution to the query (unlike ab- search, which keeps going until it finds the optimal minimax sequence).

https://en.wikipedia.org/wiki/Proof-number_search

In general, the "deepest" searching algorithms based on PN combine two searches, the "top" half running some PN variant sped up by transposition tables, and after some critical depth which depends on the amount of memory available for the tables, a second search algorithm without TT is launched, for some maximum depth of plies. It is the case that large enough searches will far exceed in number of nodes any reasonable amount of memory, so the TT can only help skip redundant branches at the lowest depths.

If we assume we can build a TT in memory with something like 10^9 positions (for a memory in the order of several Gb), we will in theory fill it with the surviving search candidates from a search in theory twice as deep (10^18 positions), the vast majority of which will have been ruled out by the algorithm without further analysis. Stockfish can run in the order of 70 million plies per second on a high-end computer, which means a "regular" computer can fill the top half of the search in the order of 10s of seconds to a few minutes. This top part of the search roughly corresponds to 11.6 plies already.

The expensive work however is to launch a search at each one of the leaves, which can fortunately be done in parallel using as much hardware as you can throw at it. The point here is not so much how many "computations" can be done per second but whether or not you want to check the table (memory accesses are costly, but narrow the search), build a local TT of just a few Mb to speed up purely the local search, or just use CPU power as means of tree exploration.

Tianhe-2 has something like 10^7 cores, so we are talking about assigning ~100 subproblems to each for maximum parallelism. So two minutes of thinking time will roughly translate into 1 second of unbounded exploration for each of the 10^9 leafs. Now assume each core visits 5 million (pruned) positions in this second and we get in theory an extra 8.7 plies of depth for a total of 20.3 plies of depth.

HOWEVER, the true number will be much higher because we ignored the effect of transpositions. Since we are considering ALL legal moves each turn, we can approximate the number of transpositions as roughly (M!^2) with M=2P the number of moves. This is because most moves outside of a strategy do not interfere with other legal moves elsewhere on the board.

So visiting 10^9 nodes in the first half actually implies solving 30 ^ P = (10^9)^2 (P/2)!^2, which gives a (possibly too optimistic) bound of P~24, and similarly the bottom half gives P~14 for a total depth of 38 plies.

Now of course in reality moves will end up not commuting, and the children nodes are not always visited in optimal order, but on the other hand we are using all legal moves as branching factor, which is a very pessimistic selection choice .

-1

I am unable to comment so im commenting here. Do you assume the computer starts calculating from the very beginning of the game or from a middle-endgame position? From the very beginning it would be impossible to find a forced mate because if both sides were to play their best lines it would be a draw. Lets say for example that out of the infinite chess mate positions possible it comes up with the fools mate first. If your computer were to calculate to find the first available mate it would find that. The question would be better asked if you have a move min or max to help centralize the math.

Potentially super computer in the future will have unimaginable processing rates and they will progress in their ability until infinity would we conclude then computers could calculate infinite amount of moves in a second? It was good you defined your parameters in the beginning by keeping the processing power limited to today's limits.

As refered to in the first comment the question should be how many positions a comp can generate in a second. To analyse a move and its infinite amount of possible positions would take infinitely long.

I might be rambling on at this point but i just wanted to ask a few questions to help refine your questions.

  • The math could be affected by what positions it considers first. It may find the fastest mate 1st or it might not find it until later – theeppright Dec 16 '14 at 18:22
  • 2
    Just a couple of observations: (1) "From the very beginning it would be impossible to find a forced mate because if both sides were to play their best lines it would be a draw." We don't know that. (2) "... out of the infinite chess mate positions ..." There are only finitely many chess positions period, as there are only finitely many pieces and finitely many places to put them. – ETD Dec 17 '14 at 0:08

protected by Phonon Mar 28 at 2:48

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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