Minmax algorithm and mate/stalemate

Post Reply
evert823
Posts: 5
Joined: Sat Mar 31, 2018 11:54 am

Minmax algorithm and mate/stalemate

Post by evert823 » Sun Jul 26, 2020 8:50 pm

Suppose I was writing an engine for Chess variants, then I would have to implement a minmax algorithm. It would more or less work like this:
It searches the tree of subsequent moves for white/black up to a depth of a given number of plies. At the deepest level it would stop looking into more lines of moves, but just evaluate a position.

In FIDE chess we have the concepts of check, mate and stalemate. To evaluate these concepts in a given position, is not possible in a static way.

- An engine can only know that a King is in check, by looking one ply deeper, and check all potential moves, and see if one player could capture the King on the next move.
- An engine can only know that a King is mated or stalemated, by looking two plies deeper, and find a certainty that one of the Kings ends up off the board.

Piece activity, pawn structure, development, and many more aspects can perhaps be evaluated for a given position, without opening up the next tree of moves. But check, mate and stalemate cannot.

While writing a Chu Shogi engine, this aspect should be easier: a position is absolutely won if one King is off the board. But this does not work for FIDE chess.

I would like to understand how I can approach this, having to deal with check, mate and stalemate.

musketeerchess
Posts: 129
Joined: Sat Dec 31, 2016 1:28 pm
Location: Paris
Contact:

Re: Minmax algorithm and mate/stalemate

Post by musketeerchess » Sun Aug 02, 2020 5:15 pm

Hi
I’m not certainly the right person that could answer your question. I suggest you ask HG Muller a more skilled programmer that masters minimax use with his Minimax engine.

evert823
Posts: 5
Joined: Sat Mar 31, 2018 11:54 am

Re: Minmax algorithm and mate/stalemate

Post by evert823 » Mon Aug 03, 2020 10:10 pm

I hope HGMuller is also reading this forum, otherwise i have his email address. But actually my question is more an observation.

I installed Visula Studio C#, and just started with a wild attempt to implement chess with weird pieces, the Witch to start with, and the purpose is to be very flexible when more weird pieces should come in.

At this moment, I implemented a lot of XML import and export functionality for all kind of primary and derived information about a position. My code can already validate input very precisely, know which squares are attacked and if the King is in check or not. I am now working on generating a list of legal moves from a given position.

I think that writing the code for a game is not the hardest thing to do. What may be much harder is to have a very good performance. When I'm done with my code, I will let it calculate 4 plies deep and 3 weeks later it will display an answer on my screen. Making that faster requires crazy optimization techniques currently beyond my abilities.

evert823
Posts: 5
Joined: Sat Mar 31, 2018 11:54 am

Re: Minmax algorithm and mate/stalemate

Post by evert823 » Mon Aug 10, 2020 11:12 pm

This new program now solves a mate in two within 20 seconds.
I'm happy that the mate in two is solved. I'm less happy with the 20 seconds, because that will grow exponentially when we talk about mate in 3 / 4 / 5.
Further updates on this here:
https://www.chess.com/clubs/forum/view/ ... -the-witch

musketeerchess
Posts: 129
Joined: Sat Dec 31, 2016 1:28 pm
Location: Paris
Contact:

Re: Minmax algorithm and mate/stalemate

Post by musketeerchess » Tue Aug 11, 2020 3:01 am

This looks good.

Post Reply