Author: Tord Romstad
Date: 05:46:40 11/21/05
Go up one level in this thread
Hi John! On November 21, 2005 at 06:21:23, John Haugeland wrote: >So, I'm about to attempt my first chess engine. Another Norwegian chess engine? Cool! :-) (I am guessing that you are Norwegian based on your name, I could be wrong). >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. PVS has the practical advantage that it is by far the most common algorithm, which means that most of the code snippets you find here and elsewhere assumes a PVS search. Adopting the techniques you see described to an MTD(f) search will sometimes be non-trivial. On the other hand, being forced to do some independent thinking is not necessarily a bad thing. I think both algorithms will do fine. Choose whatever you prefer. >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? There are no deep issues here at all. Null move pruning is based on the observation that zugzwang is a very rare phenomenon in chess, nothing more. If you can allow your opponent to move twice in a row and still have the advantage, your position is probably very good. Whether the idea is really as good as is commonly believed is another question, of course. More about this below. >And, how do I know when zugzwang is afoot, and therefore when to >stop null-move pruning? Several techniques exist. The most common is to disable null move pruning when the side to move has very little material left, and in pawn endgames. Some programs also avoid null moves when the side to move has low safe mobility. There are also search-based methods. You can do a reduced-depth verification search after the null move search, or allow two (but never three) null moves in a row. In my experience, zugzwang isn't the most serious problem with null move pruning. The really big problem is that it tends to prune away long, quiet lines where there are no short-term tactical or positional threats along the way, and the point only becomes clear at the end of the line. >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? No, not using recursive null-move pruning does not make you a moron. Some of the world's strongest chess programs (most notably Chess Tiger and Junior) do not use null move pruning. At least in the case of Chess Tiger, the author seems to firmly believe that whatever he is doing works better than null move. >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? You probably want to have a look at transposition tables and static exchange evaluation. Good luck, and have fun! Tord
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.