Author: Bas Hamstra
Date: 18:27:53 11/19/99
Go up one level in this thread
On November 19, 1999 at 18:15:17, Ratko V Tomic wrote:
>>> 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).
>>
>
>I have done it in MASM 6.1 few years ago for an NT screen magnifier (called
>MAGIC). The assembler auto-repeat macros generated thousands of cases of back-to
>back pixel replications with bit-boundaries handling varying between steps and
>the tables that for each magnification coordinate pair dispatches to the right
>spot in the block of asm instructions, so that a loop is done once per scan
>line. It speeded up the original C+ASM code by factor 5. In C one couldn't do
>that kind of thing at all. The C preprocessor is quite crude compared to the
>macro-assemblers.
>
>
>>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.
>
>
>Wouldn't a more complicated incrementally updated linked list type structure
>handle the captures-only cases better? When a piece moves, its attacks change,
>plus attacks on/through the source and destination squares (destination changes
>also if something was captured there). The attack info would not only have to
>carry attack-by-who, but also the sliding direction for a sliding piece attacks.
> One would probably want to keep info on defense by own pieces, not only to
>facilitate SEE operation, but since that can turn into uncovered attack, when
>piece moves.
>
>I would guess it would be tricky to get such incremental scheme working right,
>but it seems it might work much faster where it counts (since the captures are
>normally small part of legal moves, pieces mostly strike into empty squares or
>into their own color).
I do incremental pseudo attacks. Which (I think) is faster and easier to code.
For each square it is known by which pieces of both colors it is attacked. Since
there can be no more than 32 pieces, this info fits in a 32 bits integer.
When a piece moves, all squares that are now "pseudo-unattacked" by the move I
undo the attacks, by XORing them.
Attack[X] & 1 means attacked by black pawn no 16. Attacks[X] & (1ul << 31)
means attacked by the white king.
Attacks[X] & PAWNMASK means pawnattacked
Attacks[X] & ROOKMASK & WHITE, well you get the idea
For SEE all attacks are ready, sorted and well.
if(!Attacks[King] & BLACK) return NotInCheck;
else
{ if(Attacks[King] & NONSLIDERS & BLACK) return InCheck;
else return Maybe;
}
Regards,
Bas Hamstra.
>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...
>>
>
>Botvinik has worked out, at least conceptually, what kind of reasoning is
>involved in chess planning in as close to an algorithmic form as one can get,
>and in more depth than anyone else. He had also introduced multilevel tree
>scheme to divide the work between the low level search from the reasoning. They
>never got it working as a playing program while he was alive (given their
>hardware and software tools in the USSR, not that surprising).
>
>The kind of common sense reasoning, which current programs lack, include idea of
>localization and mobilization of force toward a smaller local region. Absent
>short term tactical gain, they'll aimlessly shift resources around the board,
>optimizing this or that positional term in ther eval function, which randomly
>changes from move to move, doing and undoing each other. Thus they lack the
>longer term coherence of play, the ability to add small gains over a longer term
>in a focused direction, so they can amount to something usable.
>A plan allows such coherence, since with a plan one gives preference to one kind
>of gains (those which fit the plan objectives the best) instead of the crosseyed
>indecisevness of a program (in the absence of near tactical gain) shifting its
>attention between the variety of unrelated 0.1 pawn positional terms gains
>(which are well within the noise band of the evaluation function applied at the
>larger depths). That's why they have trouble either seeing or initiating the
>slow unfolding king-side attacks, or generally any longer mobilization maneuvers
>(especially if other minor contingencies are interposed within them).
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.