4

I want to implement a simple chess bot so I have been reading about this algorithm a lot. I can say I understand the basic idea of the algorithm but I can't clearly see how am I supposed to apply it on the board. Let's say it's white turn, do i have to apply minimax on every possible move of all the white pieces ? And let's suppose the depth is greater than 1. Let's suppose I'm going to apply the algorithm on a pawn. As far as i understand I need to generate all the possible legal moves of my pawn, and for each move I'm going to apply (recursively) minimax again for the black side, at this point do I need to apply it on every single legal move of the black side? Is my understanding correct? If not would you please explain how is it supposed to work with an example?

4 Answers 4

1

Let's say you wanted your engine to calculate 10 moves ahead. To do this, you must look at each different combination of 10 moves from the current position, and evaluate each of the final positions that you get from doing this. Then, you apply minimax by working backwards and assigning evaluations to the previous positions up the tree.

You are correct in thinking that you look at each move for each of your pieces, and then in each of the resulting positions do this from Black's side, and then from White's, etc. Keep doing this until reaching your depth limit (how far ahead you want the computer to calculate). If the depth limit is 10 moves, recursively do this until reaching 10 moves ahead. Then, evaluate the final positions (using an evaluation function you would write), and back-propagate.

It's hard to explain minimax just using text, so I'm going to post some resources below. These were extremely helpful, and allowed me to understand minimax and the algorithms associated with it (such as alpha-beta pruning, which significantly reduces the run-time of the minimax algorithm by pruning branches that are guaranteed to not affect the evaluation):

Minimax with alpha-beta pruning: https://www.youtube.com/watch?v=zp3VMe0Jpf8

Summary of minimax, with links to more resources/papers: https://chessprogramming.wikispaces.com/Minimax

1

Short answer: Yes with minimax you have to search every move.

Minimax is not used due to the exponentially growing search which quickly becomes too big to be useful. Think O(n2) sort functions. Many concepts are used to help reduce the number of nodes the search function. Transposition Tables, fail-safe, branch pruning...

https://web.archive.org/web/20071026090003/http://www.brucemo.com/compchess/programming/index.htm is the Gerbil chess engine with good explanations.

https://chessprogramming.wikispaces.com/Home is more general and discusses other algorithms, but is more technical and is closing soon.

1

Yes, you'll have to search all moves in minimax as it's a framework for determining the evaluation score.

In alpha-beta, you might skip some moves by pruning.

0

You can't use minimax properly with this sort of problem. The problem is that you cannot see far enough and evaluate that position accurately enough to know.

You will need to make assumptions and do pruning to be able to compute enough into the future to have a reasonable assessment, and then you have to hope that your pruning was good enough that there are no nasty surprises.

It works well for the majority of positions but you cannot guarantee you have the absolute best answer.

Your Answer

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

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