3

If we use the most basic approach to a chess engine (for example, for a codegolf): minimax to a fixed depth with the material count as static evaluation, then how strong is this algorithm?

This of course depends on the search depth, but since such engines have been implemented tens of thousands of times, I hope there are some resources that can say something about the strength as a function of the search depth. I haven't been able to find any so far.

It also depends on the material values, which are not always the same.

2

If we use the most basic approach to a chess engine (for example, for a codegolf): minimax to a fixed depth with the material count as static evaluation, then how strong is this algorithm?

Not very strong.

Even though the material value is a significant factor in evaluation. There are many more factors that you need to consider to build a strong evaluation function.

  • Mobility
  • Center Control
  • Pawn structure
  • King Safety
  • Blocked pieces
  • Tempo

These are just the key points, there are in-fact many more factors you can add.

Now, coming back to the question which is the relation of depth to the strength of the engine

  • Short answer: The greater the depth, the stronger the chess engine is. With experience, I can say that the engine you described in your question would be quite weak, and could be defeated by any amateur chess player.

  • Long Answer:

I would say that it has a significant impact.

The problem is that depth doesn't necessarily denote the number of moves you have searched. This is because modern chess engines apply something called pruning which is reducing the number of moves it evaluates. It cuts down on a huge number of moves that seem bad during the beginning of the search, which can cut down a huge branch of moves. Due to this engines like Stockfish can reach depths of more than 15!

If you use a basic algorithm like minimax that applies no pruning, depth 6 with a reasonably fast generator function will already be slow. Anything after depth 7 would just take forever.

If there are an average of 20 moves in a position, this is how many moves you would be evaluating approximately when the depth increase

depth 1 = 20
depth 2 = 400
depth 3 = 8,000
depth 4 = 160,000
depth 5 = 3,200,000
depth 6 = 64,000,000
depth 7 = 1,280,000,000

1.2 trillion moves. That is a LOT of moves. And chess engines today search moves NOWHERE NEAR that number.

I gave ethereal about 7 seconds to search for moves in this position for black

n

Using arena I could see the details of this search, and to my surprise, it had gone to a depth of 22! Does this mean it evaluated 134217730000000000000000000000000000 positions?

No, it evaluated only 9,799,1101 positions. Again, because of pruning.

It did go to a depth of 22 but it did not evaluate all the variations.

Using a simpler search algorithm like minimax which applies no pruning, you will be seeing the same number of moves at depth 4-6 but those moves have very little meaning. Because a huge part of them could start with you hanging one of your pieces.

So your evaluation function is weak as it only considers material balance, and your search algorithm isn't great either, you can understand why this engine will be weak.

EDIT: As I said earlier the greater the depth of the search, the stronger the move it picks.

At greater depths, the difference will only become greater because a single increment in the depth could result in searching millions of more nodes. There is no simple relation between the elo and the depth of an engine because as I also mentioned earlier depth is one factor amongst a hundred others.

If you see the top engines today, all of them search to a similar depth, but some are very clearly stronger than the other. Which just proves my point.

3
  • Thank you for your elaborate answer, however, it doesn't answer the question. To be more clear: when I say basic minimax I mean the value that it returns, not the way it does so. So if I have an efficient search algorithm (alphabeta pruning with good move ordering, transposition table, maybe more) then I will be able to search much deeper than the situation you talk about. Then it starts to get interesting how strong it will be. How far can you go be simply searching deeper, without changing the heuristic? – Jens Renders Jan 8 at 0:34
  • Maybe I hinted in the question at an implementation that cannot search deep by saying "for example for a codegolf" but I am looking for the influence of depth on Elo regardless. Imagine that we can search very deep. Should it be the case that searching so far that the engine gets relatively strong requires pruning based on a more elaborate heuristic, please inform me :) – Jens Renders Jan 8 at 0:36
  • @JensRenders Sorry about that, i misunderstood the question. I've added an edit and you an let me know whether its fine now – Aryan Parekh Jan 8 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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