Thursday, May 8, 2008

Killer Heuristic

I gravitate toward pacifism. The day I start spewing ad hominem attacks at people, deserved or not, is the day I ask, "Where is the body-snatching pod that took away the real me?" However, I'm not above criticizing, likely more than I praise, but I try to keep the criticism on the object before me rather than on the person who produced it. Blue Devil Knight used the term "ad rem" which I only learned today is the opposite of "ad hominem." Latin is still fun to use when you want to talk over people's heads. This discussion reminds me of a favorite short story "Love is a Fallacy" by Max Shulman.

The title of this post sounds like a slasher movie or at least a Heuristic ALgorithm that becomes a killer. The fact that a lot of my posts are titled with violent words or warlike themes, however, tells me that conflict is not altogether a bad thing. Conflict sells advertising spots on the news and tickets at the theater. The two main contenders for this year's Academy Award for Best Picture were "There Will Be Blood" and "No Country For Old Men". I have seen neither, but from the trailers, they seem to have a heftier than usual helping of conflict. There is a lot to be discovered in the crucible of conflict as long as you don't lose too much of yourself. What is chess but a conflict between two people abstracted into a game? I tend to focus on the self-preserving first part of Nietzsche's quote (Conan the Barbarian translation) "That which does not kill us, makes us stronger." while the meat of the quote is the self-improvement second part.

A few years back, one of my projects was trying to program my own chess computer engine. I did it out of the challenge of the thing, and the fact that it married my two favorite pastimes. I had these grand schemes of having the program spar with computer programs I have at home and even releasing it from captivity into the wild and wooly world of FICS or ICC. But I didn't get very far because my perfectionist side began nagging at me before I got far enough to implement the things it was suggesting. "Have you considered taking advantage of the MMX? Why don't you optimize your slow algorithm? Bitboards or no bitboards?" I managed to make a program that could play legal, 1 to 2-ply chess, but it was still close to playing giveaway chess. The slow algorithm started to implement beta cutoff, but I never got around to implementing killer heuristic.

At temposchlucker's great blog, he's exploring the mysterious workings of the mind in the context of tactical ability and trying in the formalized manner of a methodical researcher to discover a new method of training the stagnant chess player. Currently he's elucidating and formalizing the step of "scanning" or finding targets, training his mind to use the method, and seeing where the research leads. Andres Hortillosa is supposed to give us some tips on analysis at his Monroi blog. So far it seems big on framework, but skimpy on detail of scanning improvement. While I wait, I think I will begin to construct my own scanning method, of course plagiarizing from the best so that I can stand on the shoulders of the giants.

I couldn’t find any particular chess personality who coined this phrase, but apparently some chess teachers tell their students to "listen to the pieces." Basically ask, "What's out there?" Scanning and target recognition are important because as many of us who Fritz our games know, many combinations lurk beneath the surface, obscured by features of the chess board, hiding in our blind spots. A saying I made up a long time ago is "Somewhere on the chess board, hidden among inaccuracies, weak moves, and outright blunders, the best move is waiting." I think I was single when I made that up.

One idea I suggested which temposchlucker either didn't see or dismissed without comment was the idea of the killer heuristic. It might be improper to put it in the scanning stage, but in the context of tempo's frustrating 1.5 hour-long search, I thought killer heuristic could lead to faster analysis. Many years ago, I wrote out my move selection method. At the top on the list was "Can I checkmate him?" Working my way down the priorities, next came "Can he checkmate me?" and "Can I win decisive material from him?" and its reciprocal. The two recent examples of problems that temposchlucker gave had the common element that high priority checking moves (Qxg7+ and Bxe4+) could be used as guidewires to find the key move of the combination.

Years later, I lumped my steps into "Forcing Moves First". From Googling this phrase, I see now that there is a book I was unaware of by FM Charles Hertan called Forcing Chess Moves. I'm not sure I'm even going to read this book, since the gist seems to be summed up in the reviews. Hertan recommends "use computer eyes and always look at forcing moves first," no matter how silly those moves look to our human bias. Kassa Korley remarked that GM Hikaru Nakamura calculates very similar to a computer. After seeing what he can do, I believe it. Kotov's tree method is similar to the computer's thinking method, adapted for us mere mortals. Arguments for and against Kotov's method seem to boil down to whether it's too hard for humans to apply. Despite anti-computer sentiment (and perhaps envy), I would not be unhappy if I "suddenly got good" and found that I could calculate like Fritz does.

It was only recently I began to equate the efficiencies gained from "Forcing Moves First" to the concept of the "Killer Heuristic". The computer algorithm employing the killer heuristic will keep one or two moves in memory to check first because the move contained the features of a very violent and decisive resolution to the chess position. If the killer move proves strong, all subsequent moves will achieve more efficient beta cutoff (computer jargon for "Stop looking, there's no contest between this move and the other one") leading to a quicker evaluation that doesn't suffer too much in terms of accuracy compared with full-width-depth brute force minimax.

What is a forcing move? In my estimation, the pecking order of moves is:
Moves that checkmate or threaten to checkmate
Moves that check or threaten to check
Moves that win or threaten oodles of material
Moves that win or threaten a little material

Toward the bottom of this list of priority are all the positional attributes that bounce upward like quantum irregularities and are rather difficult to constantly and accurately balance against the material. But evaluate we must because most of the time, at least in my games, the positions seem rather quiet and there isn't a forcing continuation at the head of the line.

For the same reasons as the Killer Heuristic, computer chess algorithms sort the remaining moves they consider by certain characteristics, probably by the material they win and the capturing piece value (e.g. pxQ ahead of QxN ahead of quiet moves). This is done at every node, because the time cost of sorting reaps downstream benefits in the efficiency of the overall algorithm. Prioritization leads to time savings and efficiency.

I'm sure I have only scratched the surface of this one, but likely I'll come back when I draft my scanning list.


Chessaholic said...

Very interesting post.

Just a little aside regarding your first paragraph: "ad rem" is not really the opposite of "ad hominem". Talking ad rem just means talking on a subject/argument at hand, while talking ad hominem means talking about the person making the argument. ("rem" comes from "res", meaning "thing" or "matter" in latin). OK ok, I'll stop being so pedantic now :)

Soapstone said...

All these Latin phrases triggered an ancient memory of a beloved short story "Love is a Fallacy" which I added to the body of the blog entry. I admit I don't understand the nuance of Latin, but it seemed that legitimate versus illegitimate argument is pretty close to what they mean, especially argument classes produced by the Flamethrowers of Cyberspace.

es_trick said...

I loved the short story by Shulman.

Thanks for sharing that.

Temposchlucker said...

I don't think the problem is in the heuristic. Nor is the problem in the pattern recognition. There are two problems:
1) The guidance of your eyes. You cannot recognize a pattern when your eyes are ignoring a certain part of the board or ignoring a certain candidate move. This ignoring happens unconscious.
2) The stalling of the mind when there are too many impressions due to short term memory overload.

Renko has a CD called intensive course tactics part II where every move is a check. In opposition to what one is inclined to think, that doesn't make the problems easier at all.

ADH said...

Have you read Part 1 and Part 2 of On Mastering Tactics? I am curious to know your thoughts on them.

Andres Hortillosa