Author: John Haugeland
Date: 03:21:23 11/21/05
So, I'm about to attempt my first chess engine. Actually, it'll be my first computer game opponent engine, with some trivial exceptions (tic tac toe and that ilk.) There are a few questions I have, which I'd like to ask, since my admittedly somewhat superficial research has turned up either contrarian answers or a complete lack thereof. The three which are foremost for me right now: 1) Is there a good way to choose between Negascout and mtd(f) ? Right now I'm leaning towards mtd(f), because though the Aske Plaat example code is broken, I do have a working private version already. If Negascout is significantly better I'll implement that instead, but if they're neck and neck I'll stick with what I've got. 2) Okay, this is going to sound dumb. Why is null move pruning a good thing? I mean, from my admittedly relatively naive standpoint, it seems like it would be counterproductive to evaluate move positions which will never actually exist. Is it that the benefit of lookahead on a similar two-step expansion without paying for the extra ply and branching step outweighs the detriment of working with not-real boards, or is there some deeper issue afoot which I don't yet understand? And, how do I know when zugzwang is afoot, and therefore when to stop null-move pruning? How much of a difference does null-move actually make, anyway? Can I get away without implementing it at all, or is it a major and important tool that I'd be a moron to skip? (Actually, reading the wikipedia definition of null-move pruning, I'm not convinced that I understand the technique; I believe it to be just evaluating positions as if the opponent was allowed to pass, for which the only justification I can see is the reduced tree size for opponent position, and some possible cutoff effects that I currently only vaguely grasp. The latter seems the more likely reason ATM, but I'm not entirely clear on lexicon; the only way I understand this at all is from having reimplemented a tree culler by hand, so I see this purely as a height toggled best position search on a tree right now, and I might be missing something due to a relatively impenetrable jargon.) 3) Which techniques, besides tree search algorithms, null move pruning, board representations (particularly bitboards and 0x88 boards are all I know about right now,) killer move heuristics, memory heuristics and iterative depth searching do I need to research? Thanks in advance for answers which don't assume I'm at all familiar with the terminology of either chess players or game opponent authors; I'm generally not. I'm doing this out of parallel interest from another field entirely; I'm not even really much good at chess. I'm a go player. Heh. Chess just provides a much better workspace than go does for the interest that's bringing me to writing a game opponent. (I suppose that'll ring some alarms, as I'm told that go is considered by far the more difficult problem for opponent authors right now, but then I'm dealing with a different set of interests and motivating factors than I suspect are typical for this crowd.) And before anyone says it, yes I'm aware of the naming coincidence, and no, I'm not the professor. I am not an AI professional. I'm just an engineer with a side interest. But, nonetheless, it's really my name. - John
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.