Author: Dan Newman
Date: 13:26:23 11/19/99
Go up one level in this thread
On November 19, 1999 at 11:37:50, Ratko V Tomic wrote: >>> instruction (which are more expensive than straight fall through). >>> In assembly language one can easily code this so that >>> (piece,source_square) pair of values retreives a pointer to a code >>> label which has the right number of directions and steps each direction >>> coded to execute without jumps or loops and to change the direction >>> (on default end of direction), all in a single block of a fall through >> >code. >> >> I think you can as well do this in C with the good old goto? > >C doesn't have a FORTRAN style "computed goto." The closest thing it has is a >switch statement, but its shortcomings vs the assembly labguage are: > >1) You have to code each "case" as separate statement. What do you do if you >have, say, 12*64=768 labels (or even more than 12 piece types if you add castle >capable & ep subtypes)? Type several thousands by hand? In assembler you make an >iterating (by count) macros of the handful basic types (12 or so) and the >dispatch table which allows jumping into the right place inside the repeated >macro block which ahs no explicit labels. > I've tried this sort of thing (several times), and what I usually do is write a C program that generates the code--if it's simple enough. The last two times I tried something like this, I broke the compiler--or rather, compilers. In one case I generated a module with several thousand functions (each would handle making a move between fixed square coordinates). I've forgotten what happened exactly, but I think the compiler simply crashed. The other case (a move generator) was either a gigantic switch statement or a huge chunk of nested if's. This one broke both Watcom and DJGPP (IIRC). [snip] >5) If one needs to separate captures from non-captures (as one normally does), >the move generator is the most natural and economical place to do it. In that >case the assembly code wouldn't need the two pointers for the two output lists >(thus wasting an extra register variable, assuming it can even get to the point >where it would pick these pointers for register variables), but could push one >type of the moves on the stack (using single instruction PUSH ECX) and the other >type into an array (via single isntruction STOSW or STOSD). They could be >processed there (on the stack), if stack was temporarily redirected into the >right array, or in the worst case, they could be bulk-copied (which is quick) to >the final destinaton, before the stack gets reset. > I once tried generating the moves into two lists, but now I just have two entirely separate move generating functions. The last time I profiled this I got 17% of the cpu time consumed by the capture generator and 2% by the non-capture generator. IIRC, the capture generator got called about 8x as much as the non-capture. In other words, what you save by doing captures and non-captures together (not duplicating a bunch of operations) might well be lost, because most of the time you don't even need the non-captures. >6) Since the entire "dispatch to the next piece" assembly code is quite short, 2 > assembly instructions, one could place dispatch to next at the end of each >(piece,square) routine, reducing the extra jump to common dispatch point for >each (piece,square) item. C switch can't do that at all (i.e. one would need to >replicate the entire switch inside each "case" statement just to avoid this >extra jump for one (piece,square) item from the list, then after the 2nd item it >would have to take the extra jump to the top level switch). > > >Overall, for this kind of task, a good assembly code would be 4-5 times faster >than the best C code/compiler could do, it would be much easier to code (less >repetitive and error prone, due to the hundreds manually entered "case" labels >in C) and it would be more portable across the compilers and languages on the >same CPU type (like the dominant Intel CPUs, with the dominant Win32 DLL API). > > >> Anyway I finally became convinced that the importancy of the speed of >> the movegenerator is modest, unless you want to make a Fritz. > It took me a while to figure this out. I think some of the books I read on computer chess implied that move generation was about the most time consuming part of a chess program, so that is what I tended to concentrate on... But what I found out was that in-check/attack detection, SEE, and eval took even more time, and that one should probably select basic data structures and so forth to help make these fast too. Improving move ordering even a tiny bit helps more than small tweekings of move generator speed which provide only a linear improvement. >Well, it could benefit in another extreme, too, at the opposite end of the >spectrum from Fritz. E.g. a design where a program uses two levels of search >tree (similar to Botvinik's Pioneer scheme), one high level tree guided by the >chess knowledge and plans, which is a sparse & deep human-like tree, and the >numerous other low level trees produced by a fast alpha-beta searcher to "hop," >as it were, between the nodes of the high level tree (the low level seracher is >additionally constrained in each such "bridging" search by the specific >goals/targets set by the higher level code for that high level node serving as >the root of that low level search). I guess what one would really like is a chess program that reasons. Actually, the alpha-beta search performs a sort of reasoning: if I make this move and he makes that move, etc. And this is just the sort of reasoning which ought to be done in many positions. But in many others you wish the program could "look" at the whole board and "see" what needs to be done--the sort of thing at which humans seem to be better. I guess the idea would be to identify some goal, then perhaps a network of subgoals, some of which must be passed through to reach the goal, and finally do some small searches to verify that the subgoals along a path to the goal can be reached (that the plan will work). My ideas on this are fairly vague, and I suspect that it might be very difficult to program such a thing... -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.