1 /***********************************************************************/
3 /* A WinBoard engine for large (dropless) Shogi variants by H.G.Muller */
4 /* The engine is based on incremental updating of an attack map and */
5 /* mobility scores, since the effort in this only grows proportional */
6 /* to board edge length, rather than board area. */
7 /***********************************************************************/
10 // in GenCapts we do not generate jumps of more than two squares yet
11 // Chu rules for Lion capture
12 // promotions by pieces with Lion power stepping in & out the zone in same turn
13 // promotion on capture
28 #define TYPE (WHITE|BLACK|EDGE)
31 #define NPIECES 2000 /* length of piece list */
33 #define SQLEN 11 /* bits in square number */
34 #define SQUARE ((1<<SQLEN) - 1) /* mask for square in move */
35 #define DEFER (1<<2*SQLEN) /* deferral on zone entry */
36 #define PROMOTE (1<<2*SQLEN+1) /* promotion bit in move */
37 #define SPECIAL 1500 /* start of special moves */
38 #define STEP(X,Y) (BW*(X)+ (Y))
41 #define UPDATE_MOBILITY(X,Y)
45 #define CAN_PROMOTE 0x11
46 #define DONT_DEFER 0x22
47 #define CANT_DEFER 0x44
48 #define LAST_RANK 0x88
53 typedef unsigned int Move;
56 char *name, *promoted;
62 int from, to, piece, victim, new, booty, epSquare, epVictim, ep2Square, ep2Victim;
65 int stm, xstm, hashKeyH, hashKeyL, framePtr, msp, nonCapts, retMSP;
66 Move moveStack[10000];
68 #define X 36 /* slider */
69 #define J -1 /* jump */
70 #define N -2 /* Knight */
71 #define D -3 /* linear double move */
72 #define T -4 /* linear triple move */
73 #define L -5 /* true Lion move */
74 #define F -6 /* Lion + 3-step */
75 #define S -7 /* Lion + range */
76 #define H -9 /* hook move */
78 PieceDesc chuPieces[] = {
79 {"LN", "", 100, { L,L,L,L,L,L,L,L } }, // lion
80 {"FK", "", 60, { X,X,X,X,X,X,X,X } }, // free king
81 {"SE", "", 55, { X,D,X,X,X,X,X,D } }, // soaring eagle
82 {"HF", "", 50, { D,X,X,X,X,X,X,X } }, // horned falcon
83 {"FO", "", 40, { X,X,0,X,X,X,0,X } }, // flying ox
84 {"FB", "", 40, { 0,X,X,X,0,X,X,X } }, // free boar
85 {"DK", "SE", 40, { X,1,X,1,X,1,X,1 } }, // dragon king
86 {"DH", "HF", 35, { 1,X,1,X,1,X,1,X } }, // dragon horse
87 {"WH", "", 35, { X,X,0,0,X,0,0,X } }, // white horse
88 {"R", "DK", 30, { X,0,X,0,X,0,X,0 } }, // rook
89 {"FS", "", 30, { X,1,1,1,X,1,1,1 } }, // flying stag
90 {"WL", "", 25, { X,0,0,X,X,X,0,0 } }, // whale
91 {"K", "", 28, { 1,1,1,1,1,1,1,1 } }, // king
92 {"CP", "", 27, { 1,1,1,1,1,1,1,1 } }, // king
93 {"B", "DH", 25, { 0,X,0,X,0,X,0,X } }, // bishop
94 {"VM", "FO", 20, { X,0,1,0,X,0,1,0 } }, // vertical mover
95 {"SM", "FB", 20, { 1,0,X,0,1,0,X,0 } }, // side mover
96 {"DE", "CP", 20, { 1,1,1,1,0,1,1,1 } }, // drunk elephant
97 {"BT", "FS", 15, { 0,1,1,1,1,1,1,1 } }, // blind tiger
98 {"G", "R", 15, { 1,1,1,0,1,0,1,1 } }, // gold
99 {"FL", "B", 15, { 1,1,0,1,1,1,0,1 } }, // ferocious leopard
100 {"KN", "LN", 15, { J,1,J,1,J,1,J,1 } }, // kirin
101 {"PH", "FK", 15, { 1,J,1,J,1,J,1,J } }, // phoenix
102 {"RV", "WL", 15, { X,0,0,0,X,0,0,0 } }, // reverse chariot
103 {"L", "WH", 15, { X,0,0,0,0,0,0,0 } }, // lance
104 {"S", "VM", 10, { 1,1,0,1,0,1,0,1 } }, // silver
105 {"C", "SM", 10, { 1,1,0,0,1,0,0,1 } }, // copper
106 {"GB", "DE", 5, { 1,0,0,0,1,0,0,0 } }, // go between
107 {"P", "G", 4, { 1,0,0,0,0,0,0,0 } }, // pawn
111 PieceDesc daiPieces[] = {
112 {"FD", "G", 15, { 0,2,0,2,0,2,0,2 } }, // Flying Dragon
113 {"VO", "G", 20, { 2,0,2,0,2,0,2,0 } }, // Violent Ox
114 {"EW", "G", 8, { 1,1,1,0,0,0,1,1 } }, // Evil Wolf
115 {"CS", "G", 7, { 0,1,0,1,0,1,0,1 } }, // Cat Sword
116 {"AB", "G", 6, { 1,0,1,0,1,0,1,0 } }, // Angry Boar
117 {"I", "G", 8, { 1,1,0,0,0,0,0,1 } }, // Iron
118 {"N", "G", 6, { N,0,0,0,0,0,0,N } }, // Knight
119 {"ST", "G", 5, { 0,1,0,0,0,0,0,1 } }, // Stone
123 PieceDesc ddPieces[] = {
124 {"LO", "", 1, { 1,H,1,H,1,H,1,H } }, // Long-Nosed Goblin
125 {"OK", "LO", 1, { 2,1,2,0,2,0,2,1 } }, // Old Kite
126 {"PS", "HM", 1, { J,0,1,J,0,J,1,0 } }, // Poisonous Snake
127 {"GE", "", 1, { 3,3,5,5,3,5,5,3 } }, // Great Elephant
128 {"WB", "LD", 1, { 1,1,2,0,1,0,2,1 } }, // Western Barbarian
129 {"EA", "LN", 1, { 2,1,1,0,2,0,1,1 } }, // Eastern Barbarian
130 {"NO", "FE", 1, { 0,2,1,1,0,1,1,2 } }, // Northern Barbarian
131 {"S)", "WE", 1, { 0,1,1,2,0,2,1,1 } }, // Southern Barbarian
132 {"FE", "", 1, { 2,X,2,2,2,2,2,X } }, // Fragrant Elephant
133 {"WE", "", 1, { 2,2,2,X,2,X,2,2 } }, // White Elephant
134 {"FT", "", 1, { X,X,5,0,X,0,5,X } }, // Free Dream-Eater
135 {"FR", "", 1, { 5,X,X,0,5,0,X,X } }, // Free Demon
136 {"WB", "FT", 1, { 2,X,X,X,2,X,X,X } }, // Water Buffalo
137 {"RB", "FR", 1, { X,X,X,X,0,X,X,X } }, // Rushing Bird
138 {"SB", "", 1, { X,X,2,2,2,2,2,X } }, // Standard Bearer
139 {"FH", "FK", 1, { 1,2,1,0,1,0,1,2 } }, // Flying Horse
140 {"NK", "SB", 1, { 1,1,1,1,1,1,1,1 } }, // Neighbor King
141 {"BM", "MW", 1, { 0,1,1,1,0,1,1,1 } }, // Blind Monkey
142 {"DO", "", 1, { 2,X,2,X,2,X,2,X } }, // Dove
143 {"EB", "DO", 1, { 2,0,2,0,0,0,2,0 } }, // Enchanted Badger
144 {"EF", "SD", 1, { 0,2,0,0,2,0,0,2 } }, // Enchanted Fox
145 {"RA", "", 1, { X,0,X,1,X,1,X,0 } }, // Racing Chariot
146 {"SQ", "", 1, { X,1,X,0,X,0,X,1 } }, // Square Mover
147 {"PR", "SQ", 1, { 1,1,2,1,0,1,2,1 } }, // Prancing Stag
148 {"WT", "", 1, { X,1,2,0,X,0,2,X } }, // White Tiger
149 {"BD", "", 1, { 2,X,X,0,2,0,X,1 } }, // Blue Dragon
150 {"HD", "", 1, { X,0,0,0,1,0,0,0 } }, // Howling Dog
151 {"VB", "", 1, { 0,2,1,0,0,0,1,2 } }, // Violent Bear
152 {"SA", "", 1, { 2,1,0,0,2,0,0,1 } }, // Savage Tiger
153 {"W", "", 1, { 0,2,0,0,0,0,0,2 } }, // Wood
154 {"CS", "DH", 7, { 0,1,0,1,0,1,0,1 } }, // cat sword
155 {"FD", "DK", 15, { 0,2,0,2,0,2,0,2 } }, // flying dragon
156 {"KN", "GD", 15, { J,1,J,1,J,1,J,1 } }, // kirin
157 {"PH", "GB", 15, { 1,J,1,J,1,J,1,J } }, // phoenix
158 {"LN", "FF", 100, { L,L,L,L,L,L,L,L } }, // lion
159 {"LD", "GE", 1, { T,T,T,T,T,T,T,T } }, // Lion Dog
160 {"AB", "", 1, { 1,0,1,0,1,0,1,0 } }, // Angry Boar
161 {"B", "", 1, { 0,X,0,X,0,X,0,X } }, // Bishop
162 {"C", "", 1, { 1,1,0,0,1,0,0,1 } }, // Copper
163 {"DH", "", 1, { 1,X,1,X,1,X,1,X } }, // Dragon Horse
164 {"DK", "", 1, { X,1,X,1,X,1,X,1 } }, // Dragon King
165 {"FK", "", 1, { } }, //
166 {"EW", "", 1, { 1,1,1,0,0,0,1,1 } }, // Evil Wolf
167 {"FL", "", 1, { } }, //
168 {"", "", 1, { } }, //
169 {"", "", 1, { } }, //
170 {"", "", 1, { } }, //
171 {"", "", 1, { } }, //
175 PieceDesc makaPieces[] = {
176 {"DV", "", 1, { 0,1,0,1,0,0,1,1 } }, // Deva
177 {"DS", "", 1, { 0,1,1,0,0,1,0,1 } }, // Dark Spirit
178 {"T", "", 1, { 0,1,0,0,1,0,0,1 } }, // Tile
179 {"CS", "", 1, { 1,0,0,1,1,1,0,0 } }, // Coiled Serpent
180 {"RD", "", 1, { 1,0,1,1,1,1,1,0 } }, // Reclining Dragon
181 {"CC", "", 1, { 0,1,1,0,1,0,1,1 } }, // Chinese Cock
182 {"OM", "", 1, { 0,1,0,1,1,1,0,1 } }, // Old Monkey
183 {"BB", "", 1, { 0,1,0,1,X,1,0,1 } }, // Blind Bear
184 {"OR", "", 1, { 0,2,0,0,2,0,0,2 } }, // Old Rat
185 {"LD", "WS", 1, { T,T,T,T,T,T,T,T } }, // Lion Dog
186 {"WR", "", 1, { 0,3,1,3,0,3,1,3 } }, // Wrestler
187 {"GG", "", 1, { 3,1,3,0,3,0,3,1 } }, // Guardian of the Gods
188 {"BD", "", 1, { 0,3,1,0,1,0,1,3 } }, // Budhist Devil
189 {"SD", "", 1, { 5,2,5,2,5,2,5,2 } }, // She-Devil
190 {"DY", "", 1, { J,0,1,0,J,0,1,0 } }, // Donkey
191 {"CP", "", 1, { 0,H,0,2,0,2,0,H } }, // Capricorn
192 {"HM", "", 1, { H,0,H,0,H,0,H,0 } }, // Hook Mover
193 {"SF", "", 1, { 0,1,X,1,0,1,0,1 } }, // Side Flier
194 {"LC", "", 1, { X,0,0,X,1,0,0,X } }, // Left Chariot
195 {"RC", "", 1, { X,X,0,0,1,X,0,0 } }, // Right Chariot
196 {"FG", "", 1, { X,X,X,0,X,0,X,X } }, // Free Gold
197 {"FS", "", 1, { X,X,0,X,0,X,0,X } }, // Free Silver
198 {"FC", "", 1, { X,X,0,0,X,0,0,X } }, // Free Copper
199 {"FI", "", 1, { X,X,0,0,0,0,0,X } }, // Free Iron
200 {"FT", "", 1, { 0,X,0,0,X,0,0,X } }, // Free Tile
201 {"FN", "", 1, { 0,X,0,0,0,0,0,X } }, // Free Stone
202 {"FTg", "", 1, { 0,X,X,X,X,X,X,X } }, // Free Tiger
203 {"FLp", "", 1, { X,X,0,X,X,X,0,X } }, // Free Leopard (Free Boar?)
204 {"FSp", "", 1, { X,0,0,X,X,X,0,0 } }, // Free Serpent (Whale?)
205 {"FrD", "", 1, { X,0,X,X,X,X,X,0 } }, // Free Dragon
206 {"FC", "", 1, { 0,X,0,X,0,X,0,X } }, // Free Cat (Bishop?)
207 {"EM", "", 1, { } }, // Emperor
208 {"TK", "", 1, { } }, // Teaching King
209 {"BS", "", 1, { } }, // Budhist Spirit
210 {"WS", "", 1, { X,X,0,X,1,X,0,X } }, // Wizard Stork
211 {"MW", "", 1, { 1,X,0,X,X,X,0,X } }, // Mountain Witch
212 {"FF", "", 1, { } }, // Furious Fiend
213 {"GD", "", 1, { 2,3,X,3,2,3,X,3 } }, // Great Dragon
214 {"GB", "", 1, { X,3,2,3,X,3,2,3 } }, // Golden Bird
215 {"FrW", "", 1, { } }, // Free Wolf
216 {"FrB", "", 1, { } }, // Free Bear
217 {"BT", "", 1, { X,0,0,X,0,X,0,0 } }, // Bat
218 {"", "", 1, { } }, //
222 PieceDesc taiPieces[] = {
223 {"", "", 1, { } }, // Peacock
224 {"", "", 1, { } }, // Vermillion Sparrow
225 {"", "", 1, { } }, // Turtle Snake
226 {"", "", 1, { } }, // Silver Hare
227 {"", "", 1, { } }, // Golden Deer
228 {"", "", 1, { } }, //
229 {"", "", 1, { } }, //
230 {"", "", 1, { } }, //
234 PieceDesc taikyokuPieces[] = {
235 {"", "", 1, { } }, //
239 char chuArray[] = "L:FLCSGK:DEGSC:FLL/:RV.B.:BT:KN:PH:BT.B.:RV/:SM:VMR:DH:DK:LN:FK:DK:DHR:VM:SM/PPPPPPPPPPPP/...:GB....:GB..."
240 "/............/............/"
241 "...:gb....:gb.../pppppppppppp/:sm:vmr:dh:dk:fk:ln:dk:dhr:vm:sm/:rv.b.:bt:ph:kn:bt.b.:rv/l:flcsg:dekgsc:fll";
242 char daiArray[] = "LN:STICSGKGSCI:STNL/:RV.:CS.:FL.:BT:DE:BT.:FL.:CS.:RV/.:VO.:AB.:EW:KN:LN:PH:EW.:AB.:VO./R:FD:SM:VMB:DH:DK:FK:DK:DHB:VM:SM:FDR"
243 "/PPPPPPPPPPPPPPP/....:GB.....:GB..../.............../.............../.............../....:gb.....:gb..../ppppppppppppppp/"
244 "r:fd:sm:vmb:dh:dk:fk:dk:dhb:vm:sm:fdr/.:vo.:ab.:ew:ph:ln:kn:ew.:ab.:vo./:rv.:cs.:fl.:bt:de:bt.:fl.:cs.:rv/ln:sticsgkgsci:stnl";
247 int boardWidth, boardFiles, zoneDepth, boardRanks; // board sizes
248 char *name; // WinBoard name
249 char *array; // initial position
252 VariantDesc variants[] = {
253 { 24, 12, 12, 4, "chu", chuArray }, // Chu
254 { 30, 15, 15, 5, "dai", daiArray }, // Dai
255 { 32, 16, 16, 5, "tenjiku", chuArray }, // Tenjiku
256 { 34, 17, 17, 0, "dada", chuArray }, // Dai Dai
257 { 38, 19, 19, 0, "maka", chuArray }, // Maka Dai Dai
258 { 50, 25, 25, 0, "tai", chuArray }, // Tai
259 { 40, 36, 36, 0, "kyoku", chuArray } // Taikyoku
266 Vector direction[] = { // clockwise!
276 { 2, 1}, // Knight jumps
286 int epList[96], ep2List[96], toList[96]; // decoding tables for double and triple moves
287 int kingStep[10], knightStep[10]; // raw tables for step vectors (indexed as -1 .. 8)
288 #define kStep (kingStep+1)
289 #define nStep (knightStep+1)
291 int attackMask[8] = { // indicate which bits in attack-map item are used to count attacks from which direction
302 int rayMask[8] = { // indicate which bits in attack-map item are used to count attacks from which direction
313 int one[] = { // 1 in the bit fields for the various directions
322 0100000000 // marks knight jumps
325 // Main Data structures
328 // Interleaved lists for black and white, white taking the odd slots
329 // Pieces in general have two entries: one for the basic, and one for the promoted version
330 // The unused one gets its position set to the invalid square number ABSENT
331 // The list is sorted by piece value, most valuable pieces first
332 // When a piece is captured in the search, both its versions are marked ABSENT
333 // In the root the list is packed to eliminate all captured pieces
334 // The list contains a table for how far the piece moves in each direction
335 // Range encoding: -3 = full Lion, -2 = on-ray Lion, -1 = plain jump, 0 = none, 1 = step, >1 = (limited) range
337 // A table in board format, containing pairs of consecutive integers for each square (indexed as 2*sqr and 2*sqr+1)
338 // The first integer contains info on black attacks to the square, the second similarly for white attacks
339 // Each integer contains eight 3-bit fields, which count the number of attacks on it with moves in a particular direction
340 // (If there are attacks by range-jumpers, the 3-bit count is increased by 2 over the actual value)
342 // The board has twice as many files as actually used, in 0x88 fashion
343 // The used squares hold the piece numbers (for use as index in the piece list)
344 // Unused squares are set to the invalid piece number EDGE
345 // There are also 3 guard ranks of EDGE on each side
347 // Moves are encoded as 11-bit from-square and to-square numbers packed in the low bits of an int
348 // Special moves (like Lion double moves) are encoded by off-board to-squares above a certain value
349 // Promotions are indicated by bit 22
351 // Entries of 16 bytes, holding a 32-bit signature, 16-bit lower- and upper-bound scores,
352 // 8-bit draft of each of those scores, an age counter that stores the search number of the last access.
353 // The hash key is derived as the XOR of the products pieceKey[piece]*squareKey[square].
355 // the promoBoard contains one byte with flags for each square, to indicate for each side whether the square
356 // is in the promotion zone (twice), on the last two ranks, or on the last rank
357 // the promoFlag field in the piece list can select which bits of this are tested, to see if it
358 // (1) can promote (2) can defer when the to-square is on last rank, last two ranks, or anywhere.
359 // Pawns normally can't defer anywhere, but if the user defers with them, their promoFlag is set to promote on last rank only
367 signed char range[8];
372 } PieceInfo; // piece-list entry
374 int last[2], royal[2];
375 PieceInfo p[NPIECES]; // piece list
386 } HashEntry; // hash-table entry
388 int squareKey[BSIZE];
390 int rawBoard[BSIZE + 11*BW + 6];
391 int attacks[2*BSIZE]; // attack map
392 char distance[2*BSIZE]; // distance table
393 char promoBoard[BSIZE];
394 signed char PST[2*BSIZE];
396 #define board (rawBoard + 6*BW + 3)
397 #define dist (distance + BSIZE)
399 int LookUp(char *name, PieceDesc *list)
400 { // find piece of given name in list of descriptors
402 while(list->name && strcmp(name, list->name)) i++, list++;
403 return (list->name == NULL ? -1 : i);
408 { // remove piece number n from the mentioned side's piece list (and adapt the reference to the displaced pieces!)
410 for(i=stm+2; i<last[stm]; i+=2)
411 if(p[i].promo > n) p[i].promo -= 2;
412 for(i=n; i<last[stm]; i+=2) {
414 if(i+2 == royal[stm]) royal[stm] -= 2; // NB: squeezing out the King moves up Crown Prince to royal[stm]
421 { // determine if range a not upward compatible with b
423 if(a >= 0 && b >= 0) return a < b;
424 if(a >= 0) return 1; // a (limited) range can never do the same as a special move
426 case J: return b < J; // any special move is better than a plain jump
427 case D: return b > 2 || b < D;
428 case T: return b > 3 || b < T;
429 case L: return b > 2 || b < D;
430 case F: return b > 3 || b < F || b == T;
431 case S: return b == H || b == T;
432 case H: return b < 0;
433 default: return 1; // a >= 0, so b must be < 0 and can always do something a ranging move cannot do
439 IsUpwardCompatible (signed char *r, signed char *s)
443 if(Worse(r[i], s[i])) return 0;
449 Forward (signed char *r)
452 for(i=2; i<7; i++) if(r[i]) return 0;
458 { // remove pieces that are permanently gone (captured or promoted) from one side's piece list
460 for(i=stm+2; i<last[stm]; i+=2) { // first pass: unpromoted pieces
461 if((k = p[i].promo) >= 0 && p[i].pos == ABSENT) { // unpromoted piece no longer there
462 p[k].promo = -2; // orphan promoted version
466 for(i=stm+2; i<last[stm]; i+=2) { // second pass: promoted pieces
467 if((k = p[i].promo) == -2 && p[i].pos == ABSENT) { // orphaned promoted piece not present
474 AddPiece (int stm, int n, PieceDesc *list)
477 for(i=stm+2; i<=last[stm]; i += 2) {
478 if(p[i].value < list[n].value || p[i].value == list[n].value && (p[i].promo < 0)) break;
481 for(j=last[stm]; j>i; j-= 2) p[j] = p[j-2];
482 p[i].value = list[n].value;
483 for(j=0; j<8; j++) p[i].range[j] = list[n].range[j^4*(WHITE-stm)];
485 for(j=stm+2; j<= last[stm]; j+=2) {
486 if(p[j].promo >= i) p[j].promo += 2;
488 if(royal[stm] >= i) royal[stm] += 2;
489 if(p[i].value == 28) royal[stm] = i;
494 SetUp(char *array, PieceDesc *list)
496 int i, j, k, k2, n, m, nr, color;
498 last[WHITE] = 1; last[BLACK] = 0;
500 printf("next rank: %s\n", array);
501 for(j = BW*i; ; j++) {
502 c = name[0] = *array++;
504 if(c == '.') continue;
506 name[1] = name[2] = 0;
507 if(c == ':') name[0] = *array++, name[1] = *array++;
510 name[0] += 'A' - 'a';
511 if(name[1]) name[1] += 'A' - 'a';
512 } else color = WHITE;
513 k = LookUp(name, list);
514 n = AddPiece(color, k, list);
516 if(list[k].promoted[0]) {
517 k2 = LookUp(list[k].promoted, list);
518 m = AddPiece(color, k2, list);
521 p[n].promoFlag = IsUpwardCompatible(list[k2].range, list[k].range) * DONT_DEFER + CAN_PROMOTE;
522 if(Forward(list[k].range)) p[n].promoFlag |= LAST_RANK; // Pieces that only move forward can't defer on last rank
523 if(!strcmp(list[k].name, "N")) p[n].promoFlag |= CANT_DEFER; // Knights can't defer on last 2 ranks
524 p[n].promoFlag &= n&1 ? P_WHITE : P_BLACK;
527 } else p[n].promo = -1; // unpromotable piece
528 printf("piece = %c%-2s %d(%d) %d/%d\n", color ? 'w' : 'b', name, n, m, last[color], last[!color]);
532 for(i=0; i<BH; i++) for(j=0; j<BH; j++) board[BW*i+j] = EMPTY;
533 for(i=WHITE+2; i<=last[WHITE]; i+=2) board[p[i].pos] = i;
534 for(i=BLACK+2; i<=last[BLACK]; i+=2) board[p[i].pos] = i;
535 stm = WHITE; xstm = BLACK;
540 return rand() ^ rand()>>10 ^ rand() << 10 ^ rand() << 20;
548 for(i= -1; i<9; i++) { // board steps in linear coordinates
549 kStep[i] = STEP(direction[i&7].x, direction[i&7].y); // King
550 nStep[i] = STEP(direction[(i&7)+8].x, direction[(i&7)+8].y); // Knight
553 for(i=0; i<8; i++) { // Lion double-move decoding tables
555 epList[8*i+j] = kStep[i];
556 toList[8*i+j] = kStep[j] + kStep[i];
558 // Lion-Dog triple moves
559 toList[64+i] = 3*kStep[i]; epList[64+i] = kStep[i];
560 toList[72+i] = 3*kStep[i]; epList[72+i] = 2*kStep[i];
561 toList[80+i] = 3*kStep[i]; epList[80+i] = kStep[i]; ep2List[80+i] = 2*kStep[i];
562 toList[88+i] = kStep[i]; epList[88+i] = 2*kStep[i];
565 // fill distance table
566 for(i=0; i<BSIZE; i++) {
571 dist[j * kStep[i]] = j;
574 for(i=0; i<BSIZE; i++) squareKey[i] = ~(myRandom()*myRandom());
575 for(i=0; i<NPIECES; i++) p[i].pieceKey = ~(myRandom()*myRandom());
578 for(i=0; i<BSIZE + 11*BW + 6; i++) rawBoard[i] = EDGE;
581 for(i=0; i<BH; i++) for(j=0; j<BH; j++) {
583 if(i == 0) v |= LAST_RANK & P_BLACK;
584 if(i < 2) v |= CANT_DEFER & P_BLACK;
585 if(i < ZONE) v |= (CAN_PROMOTE | DONT_DEFER) & P_BLACK;
586 if(i >= BH-ZONE) v |= (CAN_PROMOTE | DONT_DEFER) & P_WHITE;
587 if(i >= BH-2) v |= CANT_DEFER & P_WHITE;
588 if(i == BH-1) v |= LAST_RANK & P_WHITE;
589 promoBoard[BW*i + j] = v;
595 AddMove (int i, int x, int y)
597 if(board[y] == EDGE) return 1;
598 if(board[y] == EMPTY) { // non-capt
599 if((flagBoard[x] | flagBoard[y]) & p[i].flags) { // promotion possible
600 moveStack[msp++] = moveStack[nonCapts];
601 moveStack[nonCapts++] |= PROMOTE | p[i].flags << 24;
602 if(!(p[i].flags & ALWAYS_PROMOTE))
603 moveStack[msp++] = x << SQLEN | y; // push deferral as well
604 else moveStack[msp++] = x << SQLEN | y; // normal move
607 if(((board[y] ^ i) & 1) return 1; // own
608 moveStack[msp++] = moveStack[nonCapts];
609 moveStack[nonCapts++] = moveStack[promotions];
610 moveStack[promotions++] = x << SQLEN | y;
611 if((flagBoard[x] | flagBoard[y]) & p[i].flags) { // promotion possible
613 if(!(p[i].flags & ALWAYS_PROMOTE)) {
614 moveStack[msp++] = moveStack[nonCapts];
615 moveStack[nonCapts++] = moveStack[promotions];
616 moveStack[promotions++] = moveStack[p-1];
618 moveStack[p-1] += PROMOTE | p[i].flags<<24;
620 return 1; // capture ends ray scan
627 NewNonCapture (int x, int y, int promoFlags)
629 if(board[y] != EMPTY) return 1; // edge, capture or own piece
630 if( (promoBoard[x] | promoBoard[y]) & promoFlags) { // piece can promote with this move
631 moveStack[msp++] = moveStack[nonCapts]; // create space for promotion
632 moveStack[nonCapts++] = x<<SQLEN | y | PROMOTE; // push promotion
633 if((promoFlags & promoBoard[y] & (CANT_DEFER | DONT_DEFER | LAST_RANK)) == 0) { // deferral could be a better alternative
634 moveStack[msp++] = x<<SQLEN | y; // push deferral
635 if( (promoBoard[x] & CAN_PROMOTE) == 0 ) { // enters zone
636 moveStack[msp-1] |= DEFER; // flag that promo-suppression takes place after this move
640 moveStack[msp++] = x<<SQLEN | y; // push normal move
645 NewCapture (int x, int y, int promoFlags)
647 if( (promoBoard[x] | promoBoard[y]) & promoFlags) { // piece can promote with this move
648 moveStack[msp++] = x<<SQLEN | y | PROMOTE; // push promotion
649 if((promoFlags & promoBoard[y] & (CANT_DEFER | DONT_DEFER | LAST_RANK)) == 0) { // deferral could be a better alternative
650 moveStack[msp++] = x<<SQLEN | y; // push deferral
651 if( (promoBoard[x] & CAN_PROMOTE) == 0 ) { // enters zone
652 moveStack[msp-1] |= DEFER; // flag that promo-suppression takes place after this move
656 moveStack[msp++] = x<<SQLEN | y; // push normal move
665 promotions = nonCapts = msp;
666 for(i=stm+2; i<=last[stm]; i+=2) {
668 if(x == ABSENT) continue;
670 int y, v = kStep[j], r = p[i].range[j];
671 if(r < 0) { // jumping piece, special treatment
672 if(r >= -3) { // in any case, do a jump of 2
673 if(board[x + 2*v] == EMPTY)
675 if(r < -1) { // Lion power, also single step
676 if(board[x + v] == EMPTY)
678 if(r == -3) { // true Lion, also Knight jump
680 if(board[x + v] == EMPTY)
689 if(board[y+=v] == GUARD) break; // off board
690 if((board[y] + i & 1) == 0) break; // same color
697 GenNonCapts (int promoSuppress)
700 for(i=stm+2; i<=last[stm]; i+=2) {
701 int x = p[i].pos, pFlag = p[i].promoFlag;
702 if(x == ABSENT) continue;
703 if(x == promoSuppress) pFlag = 0;
705 int y, v = kStep[j], r = p[i].range[j];
706 if(r < 0) { // jumping piece, special treatment
707 if(r >= S) { // in any case, do a jump of 2
708 NewNonCapture(x, x + 2*v, pFlag);
709 if(r < N) { // Lion power, also single step
710 NewNonCapture(x, x + v, pFlag);
711 if(r == L) { // true Lion, also Knight jump
713 NewNonCapture(x, x + v, pFlag);
721 if(NewNonCapture(x, y+=v, pFlag)) break;
727 report (int x, int y, int i)
732 MapOneColor (int start, int last, int *map)
735 for(i=start+2; i<=last; i+=2) {
736 if(p[i].pos == ABSENT) continue;
738 int x = p[i].pos, v = kStep[j], r = p[i].range[j];
739 if(r < 0) { // jumping piece, special treatment
740 if(r >= S) { // in any case, do a jump of 2
741 if(board[x + 2*v] != EMPTY && board[x + 2*v] != EDGE)
742 map[2*(x + 2*v) + start] += one[j];
743 if(r < J) { // Lion power, also single step
744 if(board[x + v] != EMPTY && board[x + v] != EDGE)
745 map[2*(x + v) + start] += one[j];
746 if(r == T) { // Lion Dog, also jump of 3
747 if(board[x + 3*v] != EMPTY && board[x + 3*v] != EDGE)
748 map[2*(x + 3*v) + start] += one[j];
750 if(r <= L) { // true Lion, also Knight jump
751 if(r < L) { // Lion plus (limited) range
753 r = (r == S ? 36 : 3);
755 if(board[y+=v] == EDGE) break;
756 if(board[y] != EMPTY) {
757 if(n > 2) map[2*y + start] += one[j]; // outside Lion range
763 if(board[x + v] != EMPTY && board[x + v] != EDGE)
764 map[2*(x + v) + start] += one[8];
771 if(board[x+=v] != EMPTY) {
772 if(board[x] != EDGE) map[2*x + start] += one[j];
781 MapFromScratch (int *map)
784 for(i=0; i<2*BSIZE; i++) map[i] = 0;
785 MapOneColor(0, last[BLACK], map);
786 MapOneColor(1, last[WHITE], map);
790 Connect (int sqr, int piece, int dir)
792 int x, step = kStep[dir], r1 = p[piece].range[dir], r2 = p[piece].range[dir+1], piece1, piece2;
795 if((attacks[2*sqr] + attacks[2*sqr+1]) & attackMask[dir]) { // there are incoming attack(s) from 'behind'
797 while(board[x-=step] == EMPTY); // in any case, scan to attacker, to see where / what it is
798 d1 = dist[x-sqr]; piece1 = board[x];
799 attacks[2*x + stm] -= -(d1 <= r2) & one[dir+4]; // remove our attack on it if in-range
800 if((attacks[2*sqr] + attacks[2*sqr+1]) & attackMask[dir+4]) { // there are also incoming attack(s) from 'ahead'
803 while(board[y+=step] == EMPTY); // also always scan to that one to see what it is
804 d2 = dist[y-sqr]; piece2 = board[y];
805 attacks[2*y+stm] -= -(d2 <= r1) & one[dir]; // remove our attack on it if in-range
806 // we have two pieces now shooting at each other. See how far they get.
807 if(d1 + d2 <= (r1 = p[piece1].range[dir])) { // 1 hits 2
808 attacks[2*y + (piece1 & WHITE)] += one[dir]; // count attack
809 UPDATE_MOBILITY(piece1, d2);
810 } else UPDATE_MOBILITY(piece1, r1 - d1); // does not connect, but could still gain mobility
811 if(d1 + d2 <= (r2 = p[piece2].range[dir])) { // 2 hits 1
812 attacks[2*x + (piece2 & WHITE)] += one[dir+4]; // count attack
813 UPDATE_MOBILITY(piece2, d1);
814 } else UPDATE_MOBILITY(piece2, r2 - d2); // does not connect, but could still gain mobility
816 } else { // we were only attacked from behind
818 r = (r2 = p[piece1].range[dir]) - d1;
819 if(r < 0 || c > one[dir+1]) { // Oops! This was not our attacker, or not the only one. There must be a jump attack from even further behind!
820 // for now, forget jumpers
824 if(board[y+=step] != EMPTY) {
825 d2 = dist[y-sqr]; piece2 = board[y];
826 if(piece2 != EDGE) { // extended move hits a piece
827 attacks[2*y + (piece1 & WHITE)] += one[dir]; // count attack
828 attacks[2*y + stm] -= -(d2 <= r1) & one[dir]; // remove our own attack on it, if in-range
830 UPDATE_MOBILITY(piece1, d2); // count extra mobility even if we hit edge
833 // we hit nothing with the extended move of the attacker behind us.
834 UPDATE_MOBILITY(piece1, r2 - d1);
835 r = r1 - r2; // extra squares covered by mover
837 if(board[y+=step] != EMPTY) {
838 d2 = dist[y-sqr]; piece2 = board[y];
839 if(piece2 != EDGE) { // extended move hits a piece
840 attacks[2*y + stm] -= one[dir]; // count attack
846 } else // no incoming attack from behind
847 if(c = (attacks[2*sqr] + attacks[2*sqr+1]) & attackMask[dir+4]) { // but incoming attack(s) from 'ahead'
849 y = sqr; while(board[y+=step]); // locate attacker
850 d2 = dist[y-sqr]; piece2 = board[y];
851 attacks[2*y + stm] -= -(d2 <= r1) & one[dir]; // remove our attack on it if in-range
852 r = (r1 = p[piece1].range[dir]) - d2;
853 if(r < 0 || c > one[dir]) { // Oops! This was not our attacker, or not the only one. There must be a jump attack from even further behind!
854 // for now, forget jumpers
858 if(board[x-=step] != EMPTY) {
859 d1 = dist[x-sqr]; piece1 = board[x];
860 if(piece1 != EDGE) { // extended move hits a piece
861 attacks[2*x + (piece2 & WHITE)] += one[dir+4]; // count attack
862 attacks[2*x + stm] -= -(d1 <= r2) & one[dir+4]; // remove our own attack on it, if in-range
864 UPDATE_MOBILITY(piece2, d1); // count extra mobility even if we hit edge
867 // we hit nothing with the extended move of the attacker behind us.
868 UPDATE_MOBILITY(piece2, r2 - d1);
869 r = r2 - r1; // extra squares covered by mover
871 if(board[x-=step] != EMPTY) {
872 d1 = dist[x-sqr]; piece1 = board[x];
873 if(piece1 != EDGE) { // extended move hits a piece
874 attacks[2*x + stm] -= one[dir+4]; // count attack
879 } else { // no incoming attacks from either side. Only delete attacks of mover on others
883 if(board[x+=step] != EMPTY) { // piece found that we attacked
884 attacks[2*x + stm] -= one[dir]; // decrement attacks along that direction
890 if(board[x-=step] != EMPTY) { // piece found that we attacked
891 attacks[2*x + stm] -= one[dir+4]; // decrement attacks along opposite direction
899 Disconnect (int sqr, int dir)
901 int x = sqr, step = kStep[dir], piece1, piece2, y;
902 while( board[x+=step] == EMPTY );
903 if(board[x] != EDGE) { // x has hit a piece
905 y = sqr; while( board[y-=step] == EMPTY );
906 if(board[y] != EDGE) { // both ends of the ray hit a piece
912 x = sqr; while( board[x-=step] == EMPTY );
913 if(board[x] == EDGE) return; // ray empty on both sides
915 // we only get here if one side hits a
921 { // determines attacks on square and blocking when a piece lands on an empty square
929 Evacuate (int sqr, int piece)
930 { // determines change in attacks on neighbors due to unblocking and mover when the mentioned piece vacates the given square
932 for(i=0; i<4; i++) Connect(sqr, piece, i);
936 MakeMove(Move m, UndoInfo *u)
938 int deferred = ABSENT;
939 // first execute move on board
940 u->from = m>>SQLEN & SQUARE;
942 u->piece = board[u->from];
943 board[u->from] = EMPTY;
945 if(m & (PROMOTE | DEFER)) {
950 p[u->piece].pos = ABSENT;
951 u->new = p[u->piece].promo;
953 } else u->new = u->piece;
955 u->booty = PST[p[u->new].pst + u->to] - PST[p[u->piece].pst + u->from];
957 if(u->to > SPECIAL) { // two-step Lion move
958 // take care of first e.p. victim
959 u->epSquare = u->from + epList[u->to - SPECIAL]; // decode
960 u->epVictim = board[u->epSquare]; // remember for takeback
961 board[u->epSquare] = EMPTY; // and remove
962 p[u->epVictim].pos = ABSENT;
963 // now take care of (optional) second e.p. victim
964 u->ep2Square = u->from + ep2List[u->to - SPECIAL]; // This is the (already evacuated) from-square when there is none!
965 u->ep2Victim = board[u->ep2Square]; // remember
966 board[u->ep2Square] = EMPTY; // and remove
967 p[u->ep2Victim].pos = ABSENT;
968 // decode the true to-square, and correct difEval and hash key for the e.p. captures
969 u->to = u->from + toList[u->to - SPECIAL];
970 u->booty += PST[p[u->epVictim].pst + u->epSquare] + PST[p[u->ep2Victim].pst + u->ep2Square];
971 hashKeyL ^= p[u->epVictim].pieceKey * squareKey[u->epSquare];
972 hashKeyH ^= p[u->epVictim].pieceKey * squareKey[u->epSquare+BW];
973 hashKeyL ^= p[u->ep2Victim].pieceKey * squareKey[u->ep2Square];
974 hashKeyH ^= p[u->ep2Victim].pieceKey * squareKey[u->ep2Square+BW];
975 } else u->epVictim = EMPTY;
977 u->victim = board[u->to];
978 p[u->victim].pos = ABSENT;
979 u->booty += PST[p[u->victim].pst + u->to];
981 p[u->new].pos = u->to;
982 board[u->to] = u->new;
984 hashKeyL ^= p[u->new].pieceKey * squareKey[u->to]
985 ^ p[u->piece].pieceKey * squareKey[u->from]
986 ^ p[u->victim].pieceKey * squareKey[u->to];
987 hashKeyH ^= p[u->new].pieceKey * squareKey[u->to+BW]
988 ^ p[u->piece].pieceKey * squareKey[u->from+BW]
989 ^ p[u->victim].pieceKey * squareKey[u->to+BW];
996 if(u->epVictim) { // put Lion victim of first leg back
997 p[u->ep2Victim].pos = u->ep2Square;
998 board[u->ep2Square] = u->ep2Victim;
999 p[u->epVictim].pos = u->epSquare;
1000 board[u->epSquare] = u->epVictim;
1003 p[u->victim].pos = u->to;
1004 board[u->to] = u->victim; // can be EMPTY
1006 p[u->new].pos = ABSENT;
1007 p[u->piece].pos = u->from; // this can be the same as above
1008 board[u->from] = u->piece;
1012 GenCapts(int sqr, int victimValue)
1013 { // generate all moves that capture the piece on the given square
1014 int i, range, att = attacks[2*sqr + stm];
1015 printf("GenCapts(%d,%d)\n",sqr,victimValue);
1016 for(i=0; i<8; i++) { // try all rays
1018 if(att & attackMask[i]) { // attacked by move in this direction
1019 v = -kStep[i]; x = sqr;
1020 while( board[x+=v] == EMPTY ); // scan towards source until we encounter a 'stop'
1021 printf("stop @ %c%d (dir %d)\n",x%BW+'a',x/BW,i);
1022 if((board[x] & TYPE) == stm) { // stop is ours
1023 int attacker = board[x], d = dist[x-sqr];
1024 printf("attacker %d, range %d, dist %d\n", attacker, p[attacker].range[i], d);
1025 if(p[attacker].range[i] >= d) { // it has a plain move in our direction that hits us
1026 NewCapture(x, sqr + victimValue - SORTKEY(attacker), p[attacker].promoFlag);
1028 if(p[attacker].range[i] < 0) { // stop has non-standard moves
1029 switch(p[attacker].range[i]) { // figure out what he can do (including multi-captures, which causes the complexity)
1032 case F: // Lion power + 3-step (as in FF)
1034 case S: // Lion power + ranging (as in BS)
1035 NewCapture(x, sqr + victimValue - SORTKEY(attacker), p[attacker].promoFlag);
1036 // now the multi-captures of designated victim together with lower-valued piece
1037 if(d == 2) { // primary victim on second ring; look for victims to take in passing
1038 if((board[sqr+v] & TYPE) == xstm && board[sqr+v] > board[sqr])
1039 NewCapture(x, SPECIAL + 9*i + victimValue - SORTKEY(attacker), p[attacker].promoFlag);
1040 if((i&1) == 0) { // orthogonal: two extra bent paths
1042 if((board[x+v] & TYPE) == xstm && board[x+v] > board[sqr])
1043 NewCapture(x, SPECIAL + 8*(i-1&7) + (i+1&7) + victimValue - SORTKEY(attacker), p[attacker].promoFlag);
1045 if((board[x+v] & TYPE) == xstm && board[x+v] > board[sqr])
1046 NewCapture(x, SPECIAL + 8*(i+1&7) + (i-1&7) + victimValue - SORTKEY(attacker), p[attacker].promoFlag);
1048 } else { // primary victim on first ring
1050 for(j=0; j<8; j++) { // we can go on in 8 directions after we captured it in passing
1052 if(sqr + v == x || board[sqr+v] == EMPTY) // hit & run; make sure we include igui (attacker is still at x!)
1053 NewCapture(x, SPECIAL + 8*i + j + victimValue, p[attacker].promoFlag);
1054 else if((board[sqr+v] & TYPE) == xstm && board[sqr+v] > board[sqr]) { // double capture
1055 NewCapture(x, SPECIAL + 8*i + j + victimValue, p[attacker].promoFlag); // other victim after primary
1056 if(dist[sqr+v-x] == 1) // other victim also on first ring; reverse order is possible
1057 NewCapture(x, SPECIAL + 8*j + i + victimValue, p[attacker].promoFlag);
1062 case D: // linear Lion move (as in HF, SE)
1064 NewCapture(x, sqr + victimValue - SORTKEY(attacker), p[attacker].promoFlag);
1065 if(d == 2) { // heck if we can take intermediate with it
1066 if((board[x+v] & TYPE) == xstm && board[x+v] > board[sqr])
1067 NewCapture(x, SPECIAL + 9*i + victimValue - SORTKEY(attacker), p[attacker].promoFlag); // e.p.
1068 } else { // d=1; can move on to second, or move back for igui
1069 NewCapture(x, SPECIAL + 8*i + (i^4) + victimValue, p[attacker].promoFlag); // igui
1070 if(board[sqr+v] == EMPTY || (board[sqr+v] & TYPE) == xstm && board[sqr+v] > board[sqr])
1071 NewCapture(x, SPECIAL + 9*i + victimValue - SORTKEY(attacker), p[attacker].promoFlag); // hit and run
1074 case J: // plain jump (as in KY, PH)
1076 NewCapture(x, sqr + victimValue - SORTKEY(attacker), p[attacker].promoFlag);
1080 if((att & attackMask[i]) == 0) continue; // no other attackers, so done with this direction
1082 // now we get to the hairy part: there are other attackers than the stop, apparently jumping over it
1083 jumper = board[x+v]; // immediately behind stop
1084 if((jumper & TYPE) == xstm && p[jumper].range[i] < 0) { // the piece behind the stop has a jump on us
1085 NewCapture(x+v, sqr + victimValue - SORTKEY(jumper), p[jumper].promoFlag);
1086 // for Chu/Dai, this can be all. With range-jumpers and Lion Dogs there could be attacks left from further upstream!
1091 if(att & attackMask[8]) { // Knight attack
1092 for(i=0; i<8; i++) { // scan all knight jumps to locate source
1093 int x = sqr - nStep[i], attacker = board[x];
1094 if((attacker & TYPE) != stm) continue;
1095 if(p[attacker].range[i] <= N && p[attacker].range[i] >= S) { // has Knight jump in our direction
1096 NewCapture(x, sqr + victimValue, p[attacker].promoFlag); // plain jump (as in N)
1097 if(p[attacker].range[i] < N) { // Lion power; generate double captures over two possible intermediates
1098 int v = kStep[i]; // leftish path
1099 if((board[x+v] & TYPE) == xstm && board[x+v] > board[sqr])
1100 NewCapture(x, SPECIAL + 8*i + (i+1&7) + victimValue, p[attacker].promoFlag);
1101 v = kStep[i+1]; // rightish path
1102 if((board[x+v] & TYPE) == xstm && board[x+v] > board[sqr])
1103 NewCapture(x, SPECIAL + 8*(i+1&7) + i + victimValue, p[attacker].promoFlag);
1117 int Search (int alpha, int beta, int difEval, int depth, int oldPromo, int promoSuppress)
1119 int i, j, k, firstMove, oldMSP = msp, curMove, sorted, bad, phase, king, iterDep, nextVictim, to, defer, dubious, bestMoveNr;
1120 int savHashL = hashKeyL, savHashH = hashKeyH;
1121 int score, bestScore, curEval;
1124 printf("search\n");fflush(stdout);
1126 MapFromScratch(attacks); // for as long as incremental update does not work.
1127 printf("map made\n");fflush(stdout);
1129 k = p[king=royal[xstm]].pos;
1131 if(attacks[2*k + stm]) {
1132 if( p[king + 2].pos == ABSENT ) return INF; // we have an attack on his only King
1134 } else { // he has no king! Test for attacks on Crown Prince
1135 k = p[king + 2].pos;
1136 if(attacks[2*k + stm]) return INF; // we have attack on Crown Prince
1138 printf("King safe\n");fflush(stdout);
1139 // EVALUATION & WINDOW SHIFT
1140 curEval = difEval + Evaluate();
1141 alpha -= (alpha < curEval);
1142 beta -= (beta <= curEval);
1145 firstMove = curMove = sorted = nonCapts = msp += 20; // leave 20 empty slots in front of move list
1147 for(iterDep=1; iterDep<= depth; iterDep++) {
1148 printf("iter %d\n", iterDep);fflush(stdout);
1150 for(curMove = firstMove; ; curMove++) { // loop over moves
1151 printf("phase=%d: first/curr/last = %d / %d / %d\n", phase, firstMove, curMove, msp);fflush(stdout);
1153 if(curMove >= msp) { // we ran out of moves; generate some new
1155 case 0: // null move
1158 bestScore = curEval;
1161 if(curEval >= beta) {
1163 score = -Search(-beta, -alpha, difEval, depth-3, ABSENT, ABSENT);
1165 if(score >= beta) { msp = oldMSP; return score + (score < curEval); }
1169 case 1: // hash move
1171 case 2: // capture-gen init
1174 case 3: // generate captures
1175 while(nextVictim < last[xstm]) { // more victims exist
1176 int group, to = p[nextVictim += 2].pos; // take next
1177 if(to == ABSENT) continue; // ignore if absent
1178 if(!attacks[2*to + stm]) continue; // skip if not attacked
1179 group = p[nextVictim].qval; // remember value of this found victime
1180 GenCapts(to, group<<28);
1181 while(nextVictim < last[xstm] && p[nextVictim+2].qval == group) { // more victims of same value exist
1182 to = p[nextVictim += 2].pos; // take next
1183 if(to == ABSENT) continue; // ignore if absent
1184 if(!attacks[2*to + stm]) continue; // skip if not attacked
1185 GenCapts(to, group<<28);
1187 printf("captures on %d generated, msp=%d\n", nextVictim, msp);
1190 phase = 4; // out of victims: all captures generated
1191 case 4: // dubious captures
1193 while( dubious < framePtr + 250 ) // add dubious captures back to move stack
1194 moveStack[msp++] = moveStack[dubious++];
1195 if(curMove != msp) break;
1200 case 6: // non-captures
1201 GenNonCapts(oldPromo);
1203 sorted = msp; // do not sort noncapts
1205 case 7: // bad captures
1214 if(curMove < sorted) {
1215 move = moveStack[sorted=j=curMove];
1216 for(i=curMove+1; i<msp; i++)
1217 if(moveStack[i] > move) move = moveStack[j=i]; // search move with highest priority
1218 moveStack[j] = moveStack[curMove]; moveStack[curMove] = move; // swap highest-priority move to front of remaining
1219 if(move == 0) { msp = curMove--; continue; } // all remaining moves must be 0; clip off move list
1221 move = moveStack[curMove];
1222 if(move == 0) continue; // skip invalidated move
1227 defer = MakeMove(moveStack[curMove], &tb);
1228 score = -Search(-beta, -alpha, -difEval - tb.booty, depth-1, promoSuppress, defer);
1230 hashKeyL = savHashL;
1231 hashKeyH = savHashH;
1238 if(score > bestScore) {
1239 bestScore = alpha; bestMoveNr = curMove;
1242 if(curMove < firstMove + 5) { // if not too much work, sort move to front
1244 for(i=curMove; i>firstMove; i--) {
1245 moveStack[i] = moveStack[i-1];
1247 moveStack[firstMove] = move;
1248 } else { // late move appended in front of list, and leaves hole in list
1249 moveStack[--firstMove] = move;
1250 moveStack[curMove] = 0;
1252 bestMoveNr = firstMove;
1253 if(score >= beta) { // beta cutoff
1267 return bestScore + (bestScore < curEval);
1275 for(i=0; i<182; i++) {
1276 printf("%3d. %3d %3d %4d %02x ", i, p[i].value, p[i].promo, p[i].pos, p[i].promoFlag&255);
1277 for(j=0; j<8; j++) printf(" %2d", p[i].range[j]);
1280 printf("last: %d / %d\nroyal %d / %d\n", last[WHITE], last[BLACK], royal[WHITE], royal[BLACK]);
1287 for(i=BH+2; i>-4; i--) {
1288 for(j=-3; j<BH+3; j++) printf("%4d", b[BW*i+j]);
1294 pbytes (unsigned char *b)
1297 for(i=BH-1; i>=0; i--) {
1298 for(j=0; j<BH; j++) printf("%3x", b[BW*i+j]);
1304 pmap (int *m, int col)
1307 for(i=BH-1; i>=0; i--) {
1308 for(j=0; j<BH; j++) printf("%10o", m[2*(BW*i+j)+col]);
1314 pmoves(int start, int end)
1317 for(i=start; i<end; i++) {
1319 f = m>>SQLEN & SQUARE;
1321 printf("%3d. %08x %3d-%3d %c%d%c%d%s\n", i, m, f, t, f%BW+'a', f/BW+1, t%BW+'a', t/BW+1, m & PROMOTE ? "+" : "");
1325 /********************************************************/
1326 /* Example of a WinBoard-protocol driver, by H.G.Muller */
1327 /********************************************************/
1331 // four different constants, with values for WHITE and BLACK that suit your engine
1335 // some value that cannot occur as a valid move
1338 // some parameter of your engine
1339 #define MAXMOVES 500 /* maximum game length */
1340 #define MAXPLY 60 /* maximum search depth */
1346 #define DEFAULT_FEN ""
1350 int moveNr; // part of game state; incremented by MakeMove
1351 MOVE gameMove[MAXMOVES]; // holds the game history
1353 // Some routines your engine should have to do the various essential things
1354 int MakeMove2(int stm, MOVE move); // performs move, and returns new side to move
1355 void UnMake2(MOVE move); // unmakes the move;
1356 int Setup2(char *fen); // sets up the position from the given FEN, and returns the new side to move
1357 void SetMemorySize(int n); // if n is different from last time, resize all tables to make memory usage below n MB
1358 char *MoveToText(MOVE move); // converts the move from your internal format to text like e2e2, e1g1, a7a8q.
1359 MOVE ParseMove(char *moveText); // converts a long-algebraic text move to your internal move format
1360 int SearchBestMove(int stm, int timeLeft, int mps, int timeControl, int inc, int timePerMove, MOVE *move, MOVE *ponderMove);
1361 void PonderUntilInput(int stm); // Search current position for stm, deepening forever until there is input.
1364 int sup0, sup1, sup2; // promo suppression squares
1367 MakeMove2 (int stm, MOVE move)
1369 sup0 = sup1; sup1 = sup2;
1370 sup2 = MakeMove(move, &undoInfo);
1378 sup2 = sup1; sup1 = sup0;
1384 SetUp(chuArray, chuPieces);
1389 SetMemorySize (int n)
1394 MoveToText (MOVE move)
1396 static char buf[50];
1397 int f = move>>SQLEN & SQUARE, g = f, t = move & SQUARE;
1398 if(t >= SPECIAL) { // kludgy! Print as side effect non-standard WB command to remove victims from double-capture (breaks hint command!)
1399 int e = f + epList[t - SPECIAL];
1400 // printf("take %c%d\n", e%BW+'a', e/BW+ONE);
1401 printf("move %c%d%c%d,\n", f%BW+'a', f/BW+ONE, e%BW+'a', e/BW+ONE); f = e;
1402 if(ep2List[t - SPECIAL]) {
1403 e = g + ep2List[t - SPECIAL];
1404 // printf("take %c%d\n", e%BW+'a', e/BW+ONE);
1405 printf("move %c%d%c%d,\n", f%BW+'a', f/BW+ONE, e%BW+'a', e/BW+ONE); f = e;
1407 t = g + toList[t - SPECIAL];
1409 sprintf(buf, "%c%d%c%d%s", f%BW+'a', f/BW+ONE, t%BW+'a', t/BW+ONE, move & PROMOTE ? "+" : "");
1414 ReadSquare (char *p, int *sqr)
1418 r = atoi(p + 1) - ONE;
1424 ParseMove (char *moveText)
1426 int i, j, f, t, t2, e, ret, deferred=0;
1427 moveText += ReadSquare(moveText, &f);
1428 moveText += ReadSquare(moveText, &t); t2 = t;
1429 if(*moveText == ',') {
1431 moveText += ReadSquare(moveText, &e);
1432 if(e != t) return INVALID; // must continue with same piece
1433 moveText += ReadSquare(moveText, &e);
1434 for(i=0; i<8; i++) if(f + kStep[i] == e) break;
1435 if(i >= 8) return INVALID; // this rejects Lion Dog 2+1 and 2-1 moves!
1436 for(j=0; j<8; j++) if(e + kStep[j] == t) break;
1437 if(j >= 8) return INVALID; // this rejects Lion Dog 1+2 moves!
1438 t2 = SPECIAL + 8*i + j;
1440 ret = f<<SQLEN | t2;
1441 if(*moveText == '+') ret |= PROMOTE;
1442 Search(-INF-1, INF+1, 0, 1, sup1, sup2);
1443 for(i=20; i<retMSP; i++) {
1444 if((moveStack[i] & (PROMOTE | DEFER-1)) == ret) break;
1445 if((moveStack[i] & DEFER-1) == ret) deferred = i; // promoted version of entered non-promotion is legal
1447 if(i>=retMSP) { // no exact match
1448 if(deferred) { // but maybe non-sensical deferral
1449 int flags = p[board[f]].promoFlag;
1450 i = deferred; // in any case we take that move
1451 if(!(flags & promoBoard[t] & (CANT_DEFER | LAST_RANK))) { // but change it into a deferral if that is allowed
1452 moveStack[i] &= ~PROMOTE;
1453 if(p[board[f]].value == 4) p[board[f]].promoFlag &= LAST_RANK; else
1454 if(!(flags & promoBoard[t])) moveStack[i] |= DEFER; // came from outside zone, so essential deferral
1458 for(i=20; i<retMSP; i++) printf("%d. %08x %08x %s\n", i-20, moveStack[i], ret, MoveToText(moveStack[i]));
1460 return (i >= retMSP ? INVALID : moveStack[i]);
1464 SearchBestMove (int stm, int timeLeft, int mps, int timeControl, int inc, int timePerMove, MOVE *move, MOVE *ponderMove)
1469 PonderUntilInput (int stm)
1473 // Some global variables that control your engine's behavior
1477 int resign; // engine-defined option
1478 int contemptFactor; // likewise
1481 { // reset the game and then replay it to the desired point
1484 last = moveNr - n; if(last < 0) last = 0;
1485 for(moveNr=0; moveNr<last; moveNr++) stm = MakeMove2(stm, gameMove[moveNr]);
1488 void PrintResult(int stm, int score)
1490 if(score == 0) printf("1/2-1/2\n");
1491 if(score > 0 && stm == WHITE || score < 0 && stm == BLACK) printf("1-0\n");
1492 else printf("0-1\n");
1497 int engineSide=NONE; // side played by engine
1498 int timeLeft; // timeleft on engine's clock
1499 int mps, timeControl, inc, timePerMove; // time-control parameters, to be used by Search
1500 int maxDepth; // used by search
1501 MOVE move, ponderMove;
1503 char inBuf[80], command[80];
1506 SetUp(chuArray, chuPieces);
1509 // pbytes(promoBoard);
1510 // Search(-INF, INF, 0, 1, ABSENT, ABSENT);
1511 // pmoves(20, retMSP);
1512 //MapFromScratch(attacks);
1513 // MapOneColor(1, last[WHITE], attacks);
1515 while(1) { // infinite loop
1517 fflush(stdout); // make sure everything is printed before we do something that might take time
1519 if(stm == engineSide) { // if it is the engine's turn to move, set it thinking, and let it move
1521 score = SearchBestMove(stm, timeLeft, mps, timeControl, inc, timePerMove, &move, &ponderMove);
1523 if(move == INVALID) { // game apparently ended
1524 engineSide = NONE; // so stop playing
1525 PrintResult(stm, score);
1527 stm = MakeMove2(stm, move); // assumes MakeMove returns new side to move
1528 gameMove[moveNr++] = move; // remember game
1529 printf("move %s\n", MoveToText(move));
1533 fflush(stdout); // make sure everything is printed before we do something that might take time
1535 // now it is not our turn (anymore)
1536 if(engineSide == ANALYZE) { // in analysis, we always ponder the position
1537 PonderUntilInput(stm);
1539 if(engineSide != NONE && ponder == ON && moveNr != 0) { // ponder while waiting for input
1540 if(ponderMove == INVALID) { // if we have no move to ponder on, ponder the position
1541 PonderUntilInput(stm);
1543 int newStm = MakeMove2(stm, ponderMove);
1544 PonderUntilInput(newStm);
1545 UnMake2(ponderMove);
1550 // wait for input, and read it until we have collected a complete line
1551 for(i = 0; (inBuf[i] = getchar()) != '\n'; i++);
1554 // extract the first word
1555 sscanf(inBuf, "%s", command);
1557 // recognize the command,and execute it
1558 if(!strcmp(command, "quit")) { break; } // breaks out of infinite loop
1559 if(!strcmp(command, "force")) { engineSide = NONE; continue; }
1560 if(!strcmp(command, "analyze")) { engineSide = ANALYZE; continue; }
1561 if(!strcmp(command, "exit")) { engineSide = NONE; continue; }
1562 if(!strcmp(command, "otim")) { goto noPonder; } // do not start pondering after receiving time commands, as move will follow immediately
1563 if(!strcmp(command, "time")) { sscanf(inBuf, "time %d", &timeLeft); goto noPonder; }
1564 if(!strcmp(command, "level")) {
1566 sscanf(inBuf, "level %d %d %d", &mps, &min, &inc) == 3 || // if this does not work, it must be min:sec format
1567 sscanf(inBuf, "level %d %d:%d %d", &mps, &min, &sec, &inc);
1568 timeControl = 60*min + sec; timePerMove = -1;
1571 if(!strcmp(command, "protover")){
1572 printf("feature ping=1 setboard=1 colors=0 usermove=1 memory=1 debug=1\n");
1573 printf("feature variants=\"chu,12x12+0_fairy\"\n");
1574 printf("feature option=\"Resign -check 0\"\n"); // example of an engine-defined option
1575 printf("feature option=\"Contempt -spin 0 -200 200\"\n"); // and another one
1576 printf("feature done=1\n");
1579 if(!strcmp(command, "option")) { // setting of engine-define option; find out which
1580 if(sscanf(inBuf+7, "Resign=%d", &resign) == 1) continue;
1581 if(sscanf(inBuf+7, "Contempt=%d", &contemptFactor) == 1) continue;
1584 if(!strcmp(command, "sd")) { sscanf(inBuf, "sd %d", &maxDepth); continue; }
1585 if(!strcmp(command, "st")) { sscanf(inBuf, "st %d", &timePerMove); continue; }
1586 if(!strcmp(command, "memory")) { SetMemorySize(atoi(inBuf+7)); continue; }
1587 if(!strcmp(command, "ping")) { printf("pong%s", inBuf+4); continue; }
1588 // if(!strcmp(command, "")) { sscanf(inBuf, " %d", &); continue; }
1589 if(!strcmp(command, "new")) { engineSide = BLACK; stm = Setup2(DEFAULT_FEN); maxDepth = MAXPLY; randomize = OFF; continue; }
1590 if(!strcmp(command, "setboard")){ engineSide = NONE; stm = Setup2(inBuf+9); continue; }
1591 if(!strcmp(command, "easy")) { ponder = OFF; continue; }
1592 if(!strcmp(command, "hard")) { ponder = ON; continue; }
1593 if(!strcmp(command, "undo")) { stm = TakeBack(1); continue; }
1594 if(!strcmp(command, "remove")) { stm = TakeBack(2); continue; }
1595 if(!strcmp(command, "go")) { engineSide = stm; continue; }
1596 if(!strcmp(command, "post")) { postThinking = ON; continue; }
1597 if(!strcmp(command, "nopost")) { postThinking = OFF;continue; }
1598 if(!strcmp(command, "random")) { randomize = ON; continue; }
1599 if(!strcmp(command, "hint")) { if(ponderMove != INVALID) printf("Hint: %s\n", MoveToText(ponderMove)); continue; }
1600 if(!strcmp(command, "book")) { continue; }
1601 if(!strcmp(command, "p")) { pboard(board); continue; }
1602 if(!strcmp(command, "w")) { pmap(attacks, WHITE); continue; }
1603 if(!strcmp(command, "b")) { pmap(attacks, BLACK); continue; }
1604 // ignored commands:
1605 if(!strcmp(command, "xboard")) { continue; }
1606 if(!strcmp(command, "computer")){ continue; }
1607 if(!strcmp(command, "name")) { continue; }
1608 if(!strcmp(command, "ics")) { continue; }
1609 if(!strcmp(command, "accepted")){ continue; }
1610 if(!strcmp(command, "rejected")){ continue; }
1611 if(!strcmp(command, "variant")) { continue; }
1612 if(!strcmp(command, "")) { continue; }
1613 if(!strcmp(command, "usermove")){
1614 int move = ParseMove(inBuf+9);
1615 if(move == INVALID) printf("Illegal move\n");
1617 stm = MakeMove2(stm, move);
1618 ponderMove = INVALID;
1619 gameMove[moveNr++] = move; // remember game
1623 printf("Error: unknown command\n");