Mate search in Fritz

8/7/2004 – Fritz' Mate engine is a useful tool for solving the "mate in x" problems that we find in chess books and magazines. Today we take a closer look at the Mate engine and answer a nagging question that some users occasionally ask: "Why does Mate analyze so slowly?" ChessBase Workshop...

ChessBase 14 Download ChessBase 14 Download

Everyone uses ChessBase, from the World Champion to the amateur next door. Start your personal success story with ChessBase 14 and enjoy your chess even more!


Along with the ChessBase 14 program you can access the Live Database of 8 million games, and receive three months of free ChesssBase Account Premium membership and all of our online apps! Have a look today!

More...

MATE SEARCH IN FRITZ

by Steve Lopez

I frequently see questions about the Mate engine in Fritz appear on Interrant message boards and occasionally in my e-mail box. The most frequent question is "Why does it take so long to analyze a position?" That's what we're going to examine in this ChessBase Workshop. But we'll take a quick detour first for those folks who aren't familiar with the Mate engine.

The Mate engine isn't a "playing" engine that does double-duty as an analysis tool as is the case with almost all other chess engines. Mate is strictly an analysis tool (you can't play games against it) and, furthermore, it's an analysis tool with a specific purpose: to find forced checkmating lines. Mate is used to solve those "White to move and mate in x" problems that we see in countless chess books and magazines.

To use the Mate engine, you set up the position, then go to the Tools menu, select "Analysis", and then "Mate search" from the submenu. You'll see the folllowing dialogue appear:

You'll see a scrollable box which shows you the engines that can be used for this feature. The specific engines will vary depending on which of the Fritz "family" of playing programs you own as well as your operating system (Windows XP users won't see any versions of Fritz prior to 5.32, as these are 16-bit engines and thus can't be used under XP).

If you choose one of the Mate engines, you'll also be allowed to choose one of three types of mate problems:

  • Classical -- this refers to standard "mate in x" problems which follow the regular rules of chess;
  • Helpmate -- a special kind of chess composition in which the side to be mated is expected to make the worst possible moves, i.e. ones which "help" the other side to mate him;
  • Selfmate -- another specialized mate composition in which the moving side is expected to help the opponent mate him (instead of the non-moving side being mated, as in "Helpmate").

See the Fritz Help file under "chess problems" for more on the specialized forms of mate problems. Checking "Last move" determines whether the last move of the solution (i.e. the mating move) will be displayed. There are additional engine parameters which can be accessed by clicking the "Parameters" button and these, too, are described in the Help file.

Choose the option which applies to the particular problem you want the engine to solve. Then click "OK" and you're on your way.

So much for the detour. Now back to the original question: why does the Mate engine take so long to analyze a problem and display the solution?

To answer this, we need to first understand how a "regular" chess engine analyzes a position. Every chess position has a set number of legal moves for the moving side. Each of these moves can be answered by x number of replies, and each of these can be answered x number of ways. Let me bore you with some math. Let's say that a certain chess position has twenty-five legal moves. To keep it simple, we'll say that there are twenty-five replies to each of these moves, and that the side moving first has twenty-five replies to each of those moves, etc. Here's how many positions must be evaluated at each step along the way:

  • After White's first move: 25
  • After Black's first move: 625
  • After White's second move: 15625
  • After Black's second move: 390625
  • After White's third move: 9765625
etc. It's easy to see that the number of positions multiplies in a near-exponential manner (I say "near" exponential because it's rare that you'll find a series of positions in which the moving side always has the same number of moves). Chess engines are greasy fast, but even the fastest engines can't cope with this explosion of positions. So chess engines use a feature called "pruning" to limit the amount of analysis they need to perform. Moves which "go nowhere" (such as, say, a Queen for pawn exchange that just leaves the moving side mucho material behind with no advantage gained) are eliminated from the search in the early going. This drastically cuts down the number of positions which must be evaluated at deeper ply levels.

This brings us to why the Mate engine is so different from other chess engines: it has no "pruning" function. Mate will always evaluate every position it comes across in its search, ignoring nothing. And that's precisely why the engine appears to be so slow. It's not actually any "slower" than a regular chess engine (it's still evaluating approximately the same number of positions per second as a normal chess engine) -- it just looks slower because it's not cutting out any candidate moves, so it takes much longer for Mate to reach a particular search depth.

This makes the Mate engine a really swell tool for solving those "mate in x" problems. But there are limitations, based on hardware and the length of the solution. If you feed Mate a "mate in two" problem, it will bust out with the answer almost instantly. But if you give it a "mate in twenty" to solve, it will take a lot longer to crank out a solution; the exact time required will vary with the speed of your computer's processor (and please don't write to me asking for some "master grid" which cross-indexes various problem lengths with processor speeds; there's no such chart. You'll have to try this feature on your own machine to see how fast it solves longer problems. What constitutes an acceptable length of time is obviously going to vary from user to user; I use my computer for a lot of other things besides chess, so I'm not willing to let Mate chew on a problem for days on end).

And this brings us to a last point about Mate. I've sometimes seen messages in which a user writes something like "I had Mate analyze a mate in ten problem for 743 hours and it didn't come up with a solution! What's wrong?"

I'm willing to bet dollars to donuts that the problem lies with the (chess) problem itself, at least in the vast majority of cases. Mate is looking for forced mates. No force, no solution. Chess problems are created by humans -- and when humans are involved, mistakes get made. I once spent all of my free time during slow moments at work over a couple of days trying to dope out the solution to a "simple" mate in three problem -- only to come up dry. I finally gave up and looked at the solution. While playing over it, I confirmed an obvious mistake (at least it was obvious to me): Black could squirm out of mate with an alternative second move, which I'd seen while trying to solve the problem. I'd "cooked" the chess problem -- there was no forced mate, and that's why I'd spent part of two days looking for a solution that didn't exist.

Mate is no different. If there's no forced mate. then the engine obviously won't find one. So if Mate's search has gone many plies beyond the limit given in the definition of the problem (and remember to double the problem's number of moves to get the number of plies) and it still hasn't found a solution, it's likely that Mate has "cooked" the chess problem. Throw that problem out and try another.

Until next week, have fun!


© 2004, Steven A. Lopez. All rights reserved.


Topics f8
Discussion and Feedback Join the public discussion or submit your feedback to the editors


Discuss

Rules for reader comments

 
 

Not registered yet? Register