Author: Andrew Williams
Date: 04:34:16 11/21/05
Go up one level in this thread
On November 21, 2005 at 06:21:23, John Haugeland wrote: >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. > Hi, Personally, I don't think it makes much difference [*], but I don't think it's the right question at the beginning anyway. I would suggest implementing a simple alpha-beta search with iterative deepening. Once you've done that you can get aspiration searching done. First of all get that working and debugged. Decide what you want to do about advanced search control later... >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.) > Suppose you and I are playing a game of chess. We're in the middle game and it's my turn. Suppose I say, "OK John, I'm winning so I'll pass and let you have another go": this means that you get two consecutive moves and it ought to give you a huge advantage. However, if you take your second move and you still can't hurt me, my position must be absolutely overwhelming, mustn't it? This is what we do with null move, EXCEPT that once we have "passed", we don't search as deeply for the other player (normally we reduce the depth by 2 or more [*]). So we pass, then do a limited search for the other player - if they can't hurt us, we assume that the position is overwhelmingly good for us and therefore that our opponent will prevent us from reaching this position by making a different choice higher up the tree. Don't worry too much about zugzwang until you've got null move working. I simply switch it off if there's not much material left, but you can experiment with other approaches. >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? > I would strongly recommend choosing a board representation that amuses you, or which you think will be easy to work with. It won't make much difference overall to the strength of your engine [*]. The history heuristic is very easy to do, so why not start with that? >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 Good luck, and get your engine working with winboard/xboard ASAP for extra fun from this hobby. Andrew [*] Warning! Other people may see this differently.
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.