Author: Dan Newman
Date: 13:58:09 12/10/97
Go up one level in this thread
On December 10, 1997 at 09:28:48, Jari Huikari wrote: > <snip> >I'm going to allow more pieces than these: maximum number 9 for >every kind except kings... (Positions with no empty squares at >board if someone wanted to create them...) > >Maximum 500 for possible moves was sure too pessimistic. :-) > >300 _must_ be enough... > >In my program I only save list of _first_ moves. Generating moves >and searching nodes in further plies are done simultaneosly. > <snip> Ah-ha, now I see why 500 moves was no problem, and with all the extra pieces (>16 per side) there may be some way of exceeding, say, 300 (though I doubt it). (You might want to go to a maximum of 10 each of rooks, knights, and bishops since you start with 2 of those and *could* have 8 pawn promotions :)). I've never tried searching each move immediately after it is generated--I supposed that it was a lot easier or more straight forward to generate_moves -> order_moves -> search. But (I think it was in one of Levy's books) it has been suggested that a move generator might be constructed that produced moves in some reasonable order to start off with. Certainly one could produce capture moves ahead of non-capture moves and moves by less valuable pieces before more valuable ones--which might do well enough (especially if you try null moves, killers, transposition table moves, and so on, ahead of doing move generation). Good move ordering is of course a *very* big win since it can give orders of magnitude better performance than random move ordering. >I have only two tables: one for 300 moves and another for their >scores. My 386SX can visit 7000 positions per second. But it >doesn't see yet much in one, only material points and some small >bonuses e.g. whether a knight is at the edge of board etc. Looks like you're further ahead on eval than I am :). I've tried out numerous different move generation schemes and managed to write 2 or perhaps 3 more-or-less complete chess engines--complete in the sense that they can play legal games--but I usually get so hung up tweaking the move generator and other low level stuff that I've never really gone much beyond material eval. I've developed a theory that one should spend one's time on developing data structures and code that speed up the portion(s) of the code that will *later* consume the most time. The problem is, when you start out writing a chess program, you're likely to write the move generator first--it being the most straight forward (and apparently necessary) part to write, and then perhaps make/undo, etc. At first it's the move generator, in-check detection, attack table maintenance (if you have one), bitboard updating (if you use them), and so forth that takes the most cpu time, but later it is likely such things as SEE, quiescence nodes, and (principally) evaluation that consume the most. It's quite possible that the early choices made in an attempt to make a very fast move generator (for instance) will then hinder the later work on the evaluation. (There are also those fortuitous choices that actually help of course.) My difficulty is putting theory into practice :). It is far too tempting to try to break the NPS barrier (say 250 knps on a P6). (Actually this is easy, just toss out move ordering (and alpha-beta) and the node rate will soar :).) -Dan.
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.