Endgame solver project

Disclaimer

We do not have an endgame analysis software to distribute at the moment.

Video presentation of our prototype DupliMot

Download gcg files & links from the presentation.

Overview of what we have done

Our endgame solver will solve exactly and exhaustively any endgame, no matter if:

• Both players have seven tiles on their racks
• One or both players are stuck with letters that they can’t play
• The racks contain two blanks and thousands of moves are playable
• The optimal sequence is 25 moves long (this is the theoretical maximal depth*)
• The best move scores zero point
• The best move is passing
• Et cætera

* If both players pass successively then we end the game and subtract each player’s rack value from their total. The official rules of the game would require the players to pass six times in a row before ending the game, but it does not matter.

Given a board position and a rack, our solver will find the spread differential (i.e. the number of points to be gained or lost) of every move (excluding phonies, for obvious reasons) assuming optimal play by both players. For each move, the optimal sequences leading to the spread differential are given (some sequences might be omitted because they are equivalent to other ones up to permutations of independent moves).

We have spent quite some time optimizing the algorithm to make it quicker. For example, we make use of multithreading and experimented with caching to avoid analyzing identical situations multiple times in the search tree. With eight 1.60 Ghz logical processors and 8.00 GB of RAM, simple endgames can be solved completely in a matter of seconds or minutes. More complex endgames, typically those with blanks or unplayable tiles, can take multiple weeks to be solved completely. For this reason, we have three modes, some faster than others, that can be used depending on what kind of solution is sought. We describe them below.

Note that, for each of these modes, one can specify the depth of the search and the number of moves, from the highest scoring one to the lowest scoring one, to consider at each depth. The values of these two parameters might lead to uncertain answers, but the parameters are useful for complex endgames when one wants a quick idea of what is going on. Also, we make sure to show the partial results and update them as the analysis progresses. This is similar to chess engines that update their suggested lines as the search is advancing.

Spread mode: for each move, find if it leads to a win, a loss or a draw

This mode is by far the fastest one. Given the spread, it will find which moves win, lose and lead to a draw. This is useful when one is not interested in the final spread of the game; that is the case in most tournament finals.

Complete mode: find the exact spread value of each move, from the highest scoring move to the lowest scoring one

This mode is the fastest if you wish to solve an endgame completely. This is useful when one wishes to do statistics, since it gives the ranking of the moves from best to worse. However, in most cases, the bad moves are of little interest (unless one wants to compose problems where a player has to help his opponent to win the game, similar to helpmate puzzles in chess). The next and final mode was made to put the bad moves aside and to focus on the good ones.

Best first mode: find the exact spread value of each move, from the best move to the worse one

In this mode, the search is focused on the good (spread-wise) moves. The algorithm will find the moves in order, from the best one to the worse one. The best first mode is much faster than the complete mode if one is simply interested in the best moves in the position. Indeed, using the complete mode would require to wait for it to finish for the best moves to be known with certainty.

Return to home page

This site uses web cookies, click to learn more. Our privacy policy. © Ortograf Inc. Updated on 22 December 2021. Informations & Contacts.