1/* 2 File: MBCMoveGenerator.h 3 Contains: Generate all legal moves from a position 4 Copyright: � 2003 by Apple Inc., all rights reserved. 5 6 IMPORTANT: This Apple software is supplied to you by Apple Computer, 7 Inc. ("Apple") in consideration of your agreement to the following 8 terms, and your use, installation, modification or redistribution of 9 this Apple software constitutes acceptance of these terms. If you do 10 not agree with these terms, please do not use, install, modify or 11 redistribute this Apple software. 12 13 In consideration of your agreement to abide by the following terms, 14 and subject to these terms, Apple grants you a personal, non-exclusive 15 license, under Apple's copyrights in this original Apple software (the 16 "Apple Software"), to use, reproduce, modify and redistribute the 17 Apple Software, with or without modifications, in source and/or binary 18 forms; provided that if you redistribute the Apple Software in its 19 entirety and without modifications, you must retain this notice and 20 the following text and disclaimers in all such redistributions of the 21 Apple Software. Neither the name, trademarks, service marks or logos 22 of Apple Inc. may be used to endorse or promote products 23 derived from the Apple Software without specific prior written 24 permission from Apple. Except as expressly stated in this notice, no 25 other rights or licenses, express or implied, are granted by Apple 26 herein, including but not limited to any patent rights that may be 27 infringed by your derivative works or by other works in which the 28 Apple Software may be incorporated. 29 30 The Apple Software is provided by Apple on an "AS IS" basis. APPLE 31 MAKES NO WARRANTIES, EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION 32 THE IMPLIED WARRANTIES OF NON-INFRINGEMENT, MERCHANTABILITY AND 33 FITNESS FOR A PARTICULAR PURPOSE, REGARDING THE APPLE SOFTWARE OR ITS 34 USE AND OPERATION ALONE OR IN COMBINATION WITH YOUR PRODUCTS. 35 36 IN NO EVENT SHALL APPLE BE LIABLE FOR ANY SPECIAL, INDIRECT, 37 INCIDENTAL OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 38 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 39 PROFITS; OR BUSINESS INTERRUPTION) ARISING IN ANY WAY OUT OF THE USE, 40 REPRODUCTION, MODIFICATION AND/OR DISTRIBUTION OF THE APPLE SOFTWARE, 41 HOWEVER CAUSED AND WHETHER UNDER THEORY OF CONTRACT, TORT (INCLUDING 42 NEGLIGENCE), STRICT LIABILITY OR OTHERWISE, EVEN IF APPLE HAS BEEN 43 ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 44*/ 45 46#include "MBCMoveGenerator.h" 47#include <algorithm> 48 49@implementation MBCMoveCounter 50 51- (int)count 52{ 53 return fCount; 54} 55 56- (void) startMoveList:(BOOL)white 57{ 58 fCount = 0; 59 fCounting = true; 60} 61 62- (void) startUnambiguousMoves 63{ 64 fCounting = false; 65} 66 67- (void) endMoveList 68{ 69} 70 71 72- (void) validMove:(MBCPiece)piece from:(MBCSquare)from to:(MBCSquare)to 73{ 74 fCount += fCounting; 75} 76 77- (void) validMove:(MBCPiece)piece from:(MBCSquare)from to:(MBCSquare)to 78 capturing:(MBCPiece) victim 79{ 80 fCount += fCounting; 81} 82 83- (void) validDrop:(MBCPiece)piece at:(MBCSquare)at 84{ 85 fCount += fCounting; 86} 87 88- (void) validCastle:(MBCPiece)king kingSide:(BOOL)kingSide; 89{ 90 fCount += fCounting; 91} 92 93@end 94 95@implementation MBCCheckCounter 96 97- (id)initForWhite:(BOOL)white variant:(MBCVariant)variant position:(const MBCPieces *)pos canCastle:(BOOL)canCastle 98{ 99 if (self = [super init]) { 100 fWhite = white; 101 fCanCastle = canCastle; 102 fGenerator = new MBCMoveGenerator(nil, variant, 0); 103 fPosition = *pos; 104 } 105 106 return self; 107} 108 109- (void)dealloc 110{ 111 delete fGenerator; 112 [super dealloc]; 113} 114 115- (void) validMove:(MBCPiece)piece from:(MBCSquare)from to:(MBCSquare)to 116{ 117 if (fCounting) { 118 MBCPieces newPos = fPosition; 119 newPos.fBoard[to] = newPos.fBoard[from]; 120 newPos.fBoard[from] = EMPTY; 121 122 if (!fGenerator->InCheck(fWhite, newPos)) 123 fCount += 1; 124 } 125} 126 127- (void) validMove:(MBCPiece)piece from:(MBCSquare)from to:(MBCSquare)to 128 capturing:(MBCPiece) victim 129{ 130 [self validMove:piece from:from to:to]; 131} 132 133- (void) validDrop:(MBCPiece)piece at:(MBCSquare)at 134{ 135 if (fCounting) { 136 MBCPieces newPos = fPosition; 137 newPos.fBoard[at] = piece; 138 139 if (!fGenerator->InCheck(fWhite, newPos)) 140 fCount += 1; 141 } 142} 143 144- (void) validCastle:(MBCPiece)king kingSide:(BOOL)kingSide; 145{ 146 if (fCounting && fCanCastle) { 147 MBCPieces newPos = fPosition; 148 char kingOrig = 'e'; 149 char kingDest = kingSide ? 'g' : 'c'; 150 char rookOrig = kingSide ? 'h' : 'a'; 151 char rookDest = kingSide ? 'f' : 'd'; 152 unsigned rank = fWhite ? 1 : 8; 153 std::swap(newPos.fBoard[Square(kingOrig, rank)], newPos.fBoard[Square(kingDest, rank)]); 154 std::swap(newPos.fBoard[Square(rookOrig, rank)], newPos.fBoard[Square(rookDest, rank)]); 155 156 if (!fGenerator->InCheck(fWhite, newPos)) 157 fCount += 1; 158 } 159} 160 161@end 162 163@implementation MBCDebugMoveBuilder 164 165+ (id)debugMoveBuilder 166{ 167 return [[[MBCDebugMoveBuilder alloc] init] autorelease]; 168} 169 170- (void) startMoveList:(BOOL)white 171{ 172 fUnambiguous = false; 173 fMoves = [[NSMutableArray alloc] init]; 174 fUnambiguousMoves = [[NSMutableArray alloc] init]; 175 fDrops = [[NSMutableArray alloc] init]; 176} 177 178- (void) startUnambiguousMoves 179{ 180 fUnambiguous = true; 181} 182 183- (void) endMoveList 184{ 185 NSLog(@"Moves: %@\n", 186 [fMoves componentsJoinedByString:@" "]); 187 NSLog(@"Unambiguous: %@\n", 188 [fUnambiguousMoves componentsJoinedByString:@" "]); 189 if ([fDrops count]) 190 NSLog(@"Drops: %@\n", 191 [fDrops componentsJoinedByString:@" "]); 192} 193 194const char * sPieces = " KQBNRP"; 195 196- (void) validMove:(MBCPiece)piece from:(MBCSquare)from to:(MBCSquare)to 197{ 198 if (fUnambiguous) 199 [fUnambiguousMoves 200 addObject: [NSString stringWithFormat:@"%c%c%d", 201 sPieces[piece], 202 Col(to), Row(to)]]; 203 else 204 [fMoves 205 addObject: [NSString stringWithFormat:@"%c%c%d-%c%d", 206 sPieces[piece], 207 Col(from), Row(from), 208 Col(to), Row(to)]]; 209} 210 211- (void) validMove:(MBCPiece)piece from:(MBCSquare)from to:(MBCSquare)to 212 capturing:(MBCPiece)victim 213{ 214 if (fUnambiguous) 215 [fUnambiguousMoves 216 addObject: [NSString stringWithFormat:@"%cx%c%d", 217 sPieces[piece], 218 Col(to), Row(to)]]; 219 else 220 [fMoves 221 addObject: [NSString stringWithFormat:@"%c%c%dx%c%d", 222 sPieces[piece], 223 Col(from), Row(from), 224 Col(to), Row(to)]]; 225} 226 227- (void) validDrop:(MBCPiece)piece at:(MBCSquare)at 228{ 229 [fDrops addObject: [NSString stringWithFormat:@"%c@%c%d", 230 sPieces[piece], 231 Col(at), Row(at)]]; 232} 233 234- (void) validCastle:(MBCPiece)king kingSide:(BOOL)kingSide; 235{ 236 [(fUnambiguous ? fUnambiguousMoves : fMoves) 237 addObject:kingSide ? @"O-O" : @"O-O-O"]; 238} 239 240@end 241 242void MBCMoveCollection::AddMove( 243 bool unambig, MBCPiece piece, MBCSquare from, MBCSquare to) 244{ 245 MBCPieceMoves & moves = 246 (unambig ? fUnambiguousMoves : fMoves)[Piece(piece)]; 247 int instance; 248 for (instance = 0; instance < moves.fNumInstances; ++instance) 249 if (moves.fFrom[instance] == from) 250 goto foundInstance; 251 moves.fFrom[moves.fNumInstances++] = from; 252 foundInstance: 253 moves.fTo[instance] |= (1llu << to); 254} 255 256void MBCMoveCollection::AddDrop(MBCPiece piece, MBCSquare at) 257{ 258 if ((piece = MBCPiece(piece)) == PAWN) { 259 fPawnDrops |= (1llu << at); 260 } else { 261 fPieceDrops |= (1llu << at); 262 fDroppablePieces |= (1 << piece); 263 } 264} 265 266void MBCMoveCollection::AddCastle(bool kingSide) 267{ 268 if (kingSide) 269 fCastleKingside = true; 270 else 271 fCastleQueenside = true; 272} 273 274@implementation MBCMoveCollector 275 276- (MBCMoveCollection *) collection 277{ 278 return &fCollection; 279} 280 281- (void) startMoveList:(BOOL)white 282{ 283 fUnambiguous = false; 284 memset(&fCollection, 0, sizeof(MBCMoveCollection)); 285 fCollection.fWhiteMoves = white; 286} 287 288- (void) startUnambiguousMoves 289{ 290 fUnambiguous = true; 291} 292 293- (void) endMoveList 294{ 295} 296 297- (void) validMove:(MBCPiece)piece from:(MBCSquare)from to:(MBCSquare)to 298{ 299 fCollection.AddMove(fUnambiguous, piece, from, to); 300} 301 302- (void) validMove:(MBCPiece)piece from:(MBCSquare)from to:(MBCSquare)to 303 capturing:(MBCPiece)victim 304{ 305 fCollection.AddMove(fUnambiguous, piece, from, to); 306} 307 308- (void) validDrop:(MBCPiece)piece at:(MBCSquare)at 309{ 310 fCollection.AddDrop(piece, at); 311} 312 313- (void) validCastle:(MBCPiece)king kingSide:(BOOL)kingSide 314{ 315 fCollection.AddCastle(kingSide); 316} 317 318@end 319 320MBCMoveGenerator::MBCMoveGenerator(id <MBCMoveBuilder> builder, 321 MBCVariant variant, 322 long flags) 323 : fBuilder(builder), fFlags(flags), fVariant(variant), 324 fPieceFilter(EMPTY), fTargetFilter(kInvalidSquare) 325{ 326} 327 328void MBCMoveGenerator::SetVariant(MBCVariant variant) 329{ 330 fVariant = variant; 331} 332 333void MBCMoveGenerator::Generate(bool white, const MBCPieces & position) 334{ 335 [fBuilder startMoveList:white]; 336 337 fColor = white ? kWhitePiece : kBlackPiece; 338 fPosition = &position; 339 340 memset(fTargetUsed, 0, 64*sizeof(uint8_t)); 341 memset(fTargetAmbiguous, 0, 64*sizeof(uint8_t)); 342 343 TryMoves(false); 344 345 [fBuilder startUnambiguousMoves]; 346 347 TryMoves(true); 348 349 [fBuilder endMoveList]; 350} 351 352void MBCMoveGenerator::Ambiguities(MBCSquare from, MBCSquare to, 353 const MBCPieces & position) 354{ 355 MBCPiece p = position.fBoard[from]; 356 357 fPieceFilter = What(p); 358 fTargetFilter = to; 359 360 Generate(Color(p) == kWhitePiece, position); 361 362 fPieceFilter = EMPTY; 363 fTargetFilter = kInvalidSquare; 364} 365 366bool MBCMoveGenerator::InCheck(bool white, const MBCPieces & position) 367{ 368 if (fVariant == kVarSuicide) 369 return false; 370 371 id saveBuilder = fBuilder; 372 MBCMoveCounter * counter = [[MBCMoveCounter alloc] init]; 373 MBCPiece king = (white?kWhitePiece:kBlackPiece) | KING; 374 375 fBuilder = counter; 376 377 for (MBCSquare i = Square('a', 1); i<=Square('h', 8); ++i) 378 if (What(position.fBoard[i]) == king) { 379 fTargetFilter = i; 380 Generate(!white, position); 381 fTargetFilter = kInvalidSquare; 382 383 break; 384 } 385 386 bool res = [counter count] > 0; 387 fBuilder = saveBuilder; 388 [counter release]; 389 390 return res; 391} 392 393bool MBCMoveGenerator::InCheckMate(bool white, const MBCPieces & position) 394{ 395 if (!InCheck(white, position)) 396 return NO; 397 398 id saveBuilder = fBuilder; 399 MBCMoveCounter * counter = 400 [[MBCCheckCounter alloc] initForWhite:white variant:fVariant position:&position canCastle:NO]; 401 fBuilder = counter; 402 403 Generate(white, position); 404 405 bool res = ![counter count]; 406 fBuilder = saveBuilder; 407 [counter release]; 408 409 return res; 410} 411 412bool MBCMoveGenerator::InStaleMate(bool white, const MBCPieces & position) 413{ 414 if (InCheck(white, position)) 415 return NO; 416 417 id saveBuilder = fBuilder; 418 MBCMoveCounter * counter = 419 [[MBCCheckCounter alloc] initForWhite:white variant:fVariant position:&position canCastle:YES]; 420 fBuilder = counter; 421 422 Generate(white, position); 423 424 bool res = ![counter count]; 425 fBuilder = saveBuilder; 426 [counter release]; 427 428 return res; 429} 430 431void MBCMoveGenerator::TryMoves(bool unambiguous) 432{ 433 fUnambiguous = unambiguous; 434 435 for (MBCSquare i = Square('a', 1); i<=Square('h', 8); ++i) { 436 MBCPiece piece = fPosition->fBoard[i]; 437 if (fPieceFilter ? What(piece) == fPieceFilter 438 : (piece && Color(piece) == fColor) 439 ) 440 TryMoves(Piece(piece), i); 441 } 442 if (fTargetFilter == kInvalidSquare) { 443 if (fVariant != kVarSuicide) 444 TryCastle(); 445 if (fVariant == kVarCrazyhouse) 446 TryDrops(); 447 } 448} 449 450void MBCMoveGenerator::TryMoves(MBCPiece piece, MBCSquare from) 451{ 452 switch (piece) { 453 case PAWN: { 454 int dir = fColor == kWhitePiece ? 1 : -1; 455 unsigned orig= fColor == kWhitePiece ? 2 : 7; 456 457 if (TryMove(piece, from, 0, dir) // Single step always permitted 458 && Row(from) == orig // How about a double step? 459 ) 460 TryMove(piece, from, 0, 2*dir);// Double step 461 TryMove(piece, from, -1, dir); // Capture left 462 TryMove(piece, from, 1, dir); // Capture right 463 break; } 464 case ROOK: 465 TryMoves(piece, from, 1, 0); 466 TryMoves(piece, from, -1, 0); 467 TryMoves(piece, from, 0, 1); 468 TryMoves(piece, from, 0, -1); 469 break; 470 case KNIGHT: 471 TryMove(piece, from, 1, 2); 472 TryMove(piece, from, 2, 1); 473 TryMove(piece, from, 2, -1); 474 TryMove(piece, from, 1, -2); 475 TryMove(piece, from, -1, -2); 476 TryMove(piece, from, -2, -1); 477 TryMove(piece, from, -2, 1); 478 TryMove(piece, from, -1, 2); 479 break; 480 case BISHOP: 481 TryMoves(piece, from, 1, 1); 482 TryMoves(piece, from, 1, -1); 483 TryMoves(piece, from, -1, -1); 484 TryMoves(piece, from, -1, 1); 485 break; 486 case QUEEN: 487 TryMoves(piece, from, 1, 0); 488 TryMoves(piece, from, -1, 0); 489 TryMoves(piece, from, 0, 1); 490 TryMoves(piece, from, 0, -1); 491 TryMoves(piece, from, 1, 1); 492 TryMoves(piece, from, 1, -1); 493 TryMoves(piece, from, -1, -1); 494 TryMoves(piece, from, -1, 1); 495 break; 496 case KING: 497 TryMove(piece, from, 1, 0); 498 TryMove(piece, from, -1, 0); 499 TryMove(piece, from, 0, 1); 500 TryMove(piece, from, 0, -1); 501 TryMove(piece, from, 1, 1); 502 TryMove(piece, from, 1, -1); 503 TryMove(piece, from, -1, -1); 504 TryMove(piece, from, -1, 1); 505 506 break; 507 } 508} 509 510void MBCMoveGenerator::TryMoves(MBCPiece piece, MBCSquare from, 511 int dCol, int dRow) 512{ 513 int dc = 0; 514 int dr = 0; 515 516 while (TryMove(piece, from, (dc += dCol), (dr += dRow))) 517 ; 518} 519 520bool MBCMoveGenerator::TryMove(MBCPiece piece, MBCSquare from, 521 int dCol, int dRow) 522{ 523 char col = Col(from)+dCol; 524 int row = Row(from)+dRow; 525 526 if (col < 'a' || col > 'h' || row < 1 || row > 8) 527 return false; 528 else 529 return TryMove(piece, from, Square(col, row)); 530} 531 532bool MBCMoveGenerator::TryMove(MBCPiece piece, MBCSquare from, MBCSquare to) 533{ 534 MBCPiece victim = fPosition->fBoard[to]; 535 536 if (fTargetFilter != kInvalidSquare && to != fTargetFilter) 537 return !victim; // Try again if square was clear 538 539 if (victim && Color(victim) == fColor) 540 return false; // Field is blocked by own piece 541 542 if (piece == PAWN) // Pawns move straight, capture diagonally 543 if (Col(from) != Col(to)) { // Attempted capture 544 if (!victim) // Field is empty, try en passant 545 if (fPosition->fEnPassant == to) // Yup 546 victim = Opposite(fColor) | PAWN; 547 else 548 return false; 549 } else if (victim) // Straight move is blocked 550 return false; 551 552 uint8_t pieceMask = 1 << piece; 553 554 if (fUnambiguous) { 555 // 556 // Simplify language model 557 // 558 if (fTargetAmbiguous[to] & pieceMask) // Amiguous move, don't do it 559 return !victim; // Don't move further after capture 560 } else { 561 fTargetAmbiguous[to] |= fTargetUsed[to] & pieceMask; 562 fTargetUsed[to] |= pieceMask; 563 } 564 if (victim) 565 [fBuilder validMove:piece from:from to:to capturing:victim]; 566 else 567 [fBuilder validMove:piece from:from to:to]; 568 569 return !victim; // Don't move further after capture 570} 571 572void MBCMoveGenerator::TryCastle() 573{ 574 int row = fColor == kWhitePiece ? 1 : 8; 575 576 MBCPiece king = fColor | KING; 577 MBCPiece rook = fColor | ROOK; 578 MBCSquare kingPos = Square('e', row); 579 MBCSquare kingRookPos = Square('h', row); 580 MBCSquare queenRookPos = Square('a', row); 581 582 if (fPosition->fBoard[kingPos] != king) // King moved 583 return; 584 585 bool kingSide = fPosition->fBoard[kingRookPos]==rook 586 && !fPosition->fBoard[Square('g', row)] 587 && !fPosition->fBoard[Square('f', row)]; 588 bool queenSide= fPosition->fBoard[queenRookPos]==rook 589 && !fPosition->fBoard[Square('b', row)] 590 && !fPosition->fBoard[Square('c', row)] 591 && !fPosition->fBoard[Square('d', row)]; 592 593 if (fUnambiguous && kingSide && queenSide) 594 return; 595 596 if (kingSide) 597 [fBuilder validCastle:king kingSide:YES]; 598 if (queenSide) 599 [fBuilder validCastle:king kingSide:NO]; 600} 601 602void MBCMoveGenerator::TryDrops() 603{ 604 for (MBCPiece p = QUEEN; p <= PAWN; ++p) { 605 MBCPiece piece = fColor | p; 606 int pawn = p==PAWN; 607 if (!fPosition->fInHand[piece]) 608 continue; 609 for (MBCSquare i = Square('a', 1+pawn); i <= Square('h', 8-pawn); ++i) 610 if (!fPosition->fBoard[i]) 611 [fBuilder validDrop:piece at:i]; 612 } 613} 614 615// Local Variables: 616// mode:ObjC 617// End: 618