00001
00002
00003 #ifndef OSL_CHECKMATE_IMMEDIATE_CHECKMATE_TCC
00004 #define OSL_CHECKMATE_IMMEDIATE_CHECKMATE_TCC
00005 #include "osl/checkmate/immediateCheckmate.h"
00006 #include "osl/checkmate/immediateCheckmateTable.h"
00007 #include "osl/move_classifier/kingOpenMove.h"
00008 #include "osl/bits/directionTraits.h"
00009 #include "osl/bits/pieceTable.h"
00010 #include "osl/bits/mask.h"
00011
00012 namespace osl
00013 {
00014 namespace checkmate
00015 {
00016 namespace detail {
00017 using osl::misc::BitOp;
00018 template<Player P>
00019 bool blockingVerticalAttack(NumEffectState const& state,Square pos)
00020 {
00021 PieceMask effect=state.effectSetAt(pos)&
00022 state.effectSetAt(pos+DirectionPlayerTraits<U,P>::offset());
00023 mask_t mask=effect.getMask(1);
00024 mask&=(state.piecesOnBoard(P).getMask(1)<<8);
00025 if((mask&mask_t::makeDirect(PtypeFuns<LANCE>::indexMask<<8)).none()){
00026 mask&=mask_t::makeDirect(PtypeFuns<ROOK>::indexMask<<8);
00027 while(mask.any()){
00028 int num=mask.takeOneBit()+NumBitmapEffect::longToNumOffset;
00029 Square from=state.pieceOf(num).square();
00030 assert(from.isOnBoard());
00031 if(from.isU<P>(pos)) goto found;
00032 }
00033 return false;
00034 found:;
00035 }
00036 const Offset offset=DirectionPlayerTraits<U,P>::offset();
00037 pos+=offset;
00038 const Player altP=alt(P);
00039 for(int i=0;i<3;i++,pos+=offset){
00040 Piece p=state.pieceAt(pos);
00041 if(p.canMoveOn<altP>()){
00042 if(state.countEffect(P,pos)==1) return true;
00043 if(!p.isEmpty()) return false;
00044 }
00045 else return false;
00046 }
00047 return false;
00048 }
00049 template<Player P>
00050 bool
00051 #ifdef __GNUC__
00052 __attribute__ ((pure))
00053 #endif
00054 blockingDiagonalAttack(NumEffectState const& state,Square pos,Square target,
00055 King8Info canMoveMask)
00056 {
00057 const Player altP=alt(P);
00058 Square to=target-DirectionPlayerTraits<U,P>::offset();
00059
00060 if((canMoveMask.uint64Value()&(0x10000<<U))==0) return false;
00061 PieceMask effect=state.effectSetAt(to)&state.effectSetAt(pos);
00062 mask_t mask=effect.getMask(1);
00063 mask&=(state.piecesOnBoard(P).getMask(1)<<8);
00064 mask&=mask_t::makeDirect(PtypeFuns<BISHOP>::indexMask<<8);
00065 while(mask.any()){
00066 int num=mask.takeOneBit()+NumBitmapEffect::longToNumOffset;
00067 Square from=state.pieceOf(num).square();
00068 assert(from.isOnBoard());
00069 Offset offset=Board_Table.getShort8OffsetUnsafe(to,from);
00070 if(to+offset != pos) continue;
00071 if(state.countEffect(P,to)==1) return true;
00072
00073 if(!state.pieceAt(to).isEmpty()) return false;
00074 Square pos1=to-offset;
00075
00076 Piece p=state.pieceAt(pos1);
00077 if(p.canMoveOn<altP>() &&
00078 state.countEffect(P,pos1)==1){
00079 return true;
00080 }
00081 }
00082 return false;
00083 }
00084 template<Player P,bool canDrop,bool setBestMove>
00085 bool hasKnightCheckmate(NumEffectState const& state,
00086 Square target,
00087 Square pos,
00088 King8Info canMoveMask,
00089 Move& bestMove, mask_t mask1)
00090 {
00091 if(!pos.isOnBoard()) return false;
00092 const Player altP=alt(P);
00093 Piece p=state.pieceAt(pos);
00094 if(p.canMoveOn<P>() &&
00095 !state.hasEffectByNotPinned(altP,pos)
00096 ){
00097 mask_t mask=state.effectSetAt(pos).getMask<KNIGHT>()&mask1;
00098 if(mask.any()){
00099 if(blockingVerticalAttack<P>(state,pos) ||
00100 blockingDiagonalAttack<P>(state,pos,target,canMoveMask)) return false;
00101 if(setBestMove){
00102 int num=mask.takeOneBit()+(PtypeFuns<KNIGHT>::indexNum<<5);
00103 Piece p1=state.pieceOf(num);
00104 Square from=p1.square();
00105 bestMove=Move(from,pos,KNIGHT,p.ptype(),false,P);
00106 }
00107 return true;
00108 }
00109 else if(canDrop && p.isEmpty()){
00110 if(blockingVerticalAttack<P>(state,pos) ||
00111 blockingDiagonalAttack<P>(state,pos,target,canMoveMask)) return false;
00112 if(setBestMove)
00113 bestMove=Move(pos,KNIGHT,P);
00114 return true;
00115 }
00116 }
00117 return false;
00118 }
00119
00120
00121 template<Player P,bool setBestMove>
00122 bool hasCheckmateMoveKnight(NumEffectState const& state, Square target,
00123 King8Info canMoveMask,Move& bestMove)
00124 {
00125
00126 if((canMoveMask.uint64Value()&0xff00)!=0) return false;
00127 mask_t mask=mask_t::makeDirect(PtypeFuns<KNIGHT>::indexMask);
00128 mask&=state.piecesOnBoard(P).getMask<KNIGHT>();
00129 mask&= ~state.promotedPieces().getMask<KNIGHT>();
00130 mask&= ~state.pinOrOpen(P).getMask<KNIGHT>();
00131 if(state.hasPieceOnStand<KNIGHT>(P)){
00132 Square pos=target-DirectionPlayerTraits<UUR,P>::offset();
00133 if(hasKnightCheckmate<P,true,setBestMove>(state,target,pos,canMoveMask,bestMove,mask))
00134 return true;
00135 pos=target-DirectionPlayerTraits<UUL,P>::offset();
00136 return hasKnightCheckmate<P,true,setBestMove>(state,target,pos,canMoveMask,bestMove,mask);
00137 }
00138 else{
00139 Square pos=target-DirectionPlayerTraits<UUR,P>::offset();
00140 if(hasKnightCheckmate<P,false,setBestMove>(state,target,pos,canMoveMask,bestMove,mask))
00141 return true;
00142 pos=target-DirectionPlayerTraits<UUL,P>::offset();
00143 return hasKnightCheckmate<P,false,setBestMove>(state,target,pos,canMoveMask,bestMove,mask);
00144 }
00145 return false;
00146 }
00147 template<Player P,bool setBestMove>
00148 bool slowCheckDrop(NumEffectState const& state,Square target,
00149 Ptype ptype,King8Info canMoveMask,Move& bestMove)
00150 {
00151 unsigned int dropMask=(canMoveMask.uint64Value()&0xff)
00152 &Immediate_Checkmate_Table.ptypeDropMask(ptype,canMoveMask);
00153
00154 assert(dropMask!=0);
00155 while(dropMask!=0){
00156 int i=BitOp::takeOneBit(dropMask);
00157 Direction d=static_cast<Direction>(i);
00158 unsigned int blockingMask=Immediate_Checkmate_Table.blockingMask(ptype,d) &
00159 (canMoveMask.uint64Value()>>16);
00160 Square drop=target-Board_Table.getOffset<P>(d);
00161 if(blockingMask!=0){
00162 NumBitmapEffect effect=state.effectSetAt(drop);
00163 mask_t longEffect=effect.getMask(1)&NumBitmapEffect::longEffectMask();
00164 longEffect&=(state.piecesOnBoard(P).getMask(1)<<8);
00165 if(longEffect.any()){
00166 do{
00167 int j=BitOp::takeOneBit(blockingMask);
00168 Direction d1=static_cast<Direction>(j);
00169 Square pos=target-Board_Table.getOffset<P>(d1);
00170 NumBitmapEffect effect1=state.effectSetAt(pos);
00171 if(effect1.countEffect(P)>1) continue;
00172 mask_t longEffect1=effect1.getMask(1)&longEffect;
00173 if(!longEffect1.any()) continue;
00174
00175 int num=longEffect1.takeOneBit()+NumBitmapEffect::longToNumOffset;
00176 if(Board_Table.isBetween(drop,state.pieceOf(num).square(),pos))
00177 goto tryNext;
00178 }while(blockingMask!=0);
00179 }
00180 }
00181
00182 if(setBestMove)
00183 bestMove=Move(drop,ptype,P);
00184 return true;
00185 tryNext:;
00186 }
00187 return false;
00188 }
00189 }
00190 }
00191 }
00192
00193
00194 template<osl::Player P,bool setBestMove>
00195 bool osl::checkmate::ImmediateCheckmate::
00196 hasCheckmateDrop(NumEffectState const& state, Square target,
00197 King8Info canMoveMask,Move& bestMove)
00198 {
00199 typedef misc::GeneralMask<unsigned short> mask_t;
00200 mask_t dropPtypeMask=mask_t::makeDirect(Immediate_Checkmate_Table.dropPtypeMask(canMoveMask));
00201 while(dropPtypeMask.any()){
00202 Ptype ptype=static_cast<Ptype>(dropPtypeMask.takeOneBit()+PTYPE_BASIC_MIN);
00203 if(state.hasPieceOnStand(P,ptype) &&
00204 detail::slowCheckDrop<P,setBestMove>(state,target,ptype,canMoveMask,
00205 bestMove))
00206 return true;
00207 }
00208 return false;
00209 }
00210
00211 template<osl::Player P,bool setBestMove>
00212 bool osl::checkmate::ImmediateCheckmate::
00213 slowHasCheckmateMoveDirPiece(NumEffectState const& state, Square target,
00214 King8Info canMoveMask,Direction d,Square pos,Piece p,Ptype ptype,Move& bestMove){
00215 const Player altP=alt(P);
00216
00217 if(ptype==PROOK){
00218 int dx=target.x()-pos.x();
00219 int dy=target.y()-pos.y();
00220 if(abs(dx)==1 && abs(dy)==1){
00221 {
00222 Square pos1=pos+Offset(dx,0);
00223 Piece p1=state.pieceAt(pos1);
00224 if(!p1.isEmpty()){
00225 {
00226
00227
00228
00229
00230
00231
00232
00233 Square pos2=pos+Offset(2*dx,0);
00234 if(state.pieceAt(pos2).template canMoveOn<altP>()){
00235 NumBitmapEffect effect2=state.effectSetAt(pos2);
00236 if(effect2.countEffect(P)==0 ||
00237 (effect2.countEffect(P)==1 &&
00238 effect2.test(p.number())))
00239 return false;
00240 }
00241 }
00242 {
00243
00244
00245
00246
00247
00248 if(p.square()==target-Offset(0,2*dy) &&
00249 state.hasEffectByPiece(p1,pos))
00250 return false;
00251 }
00252 }
00253 }
00254 {
00255 Square pos1=pos+Offset(0,dy);
00256 Piece p1=state.pieceAt(pos1);
00257 if(!p1.isEmpty()){
00258 Square pos2=pos+Offset(0,2*dy);
00259 {
00260 if(state.pieceAt(pos2).template canMoveOn<altP>()){
00261 NumBitmapEffect effect2=state.effectSetAt(pos2);
00262 if(effect2.countEffect(P)==0 ||
00263 (effect2.countEffect(P)==1 &&
00264 effect2.test(p.number())))
00265 return false;
00266
00267 }
00268 {
00269
00270
00271
00272
00273 if(p.square()==target-Offset(2*dx,0) &&
00274 state.hasEffectByPiece(p1,pos))
00275 return false;
00276 }
00277 }
00278 }
00279 }
00280 }
00281 }
00282
00283
00284
00285
00286
00287
00288
00289
00290 mask_t mask=mask_t::makeDirect((canMoveMask.uint64Value()>>16)&Immediate_Checkmate_Table.noEffectMask(ptype,d));
00291 if(mask.any()){
00292 int num=p.number();
00293 NumBitmapEffect effect2=state.effectSetAt(pos);
00294 effect2.reset(num+8);
00295 mask_t longEffect2=effect2.getMask(1)&NumBitmapEffect::longEffectMask();
00296 longEffect2&=(state.piecesOnBoard(P).getMask(1)<<8);
00297 do {
00298 Direction d1=static_cast<Direction>(mask.takeOneBit());
00299 Square pos1=target-Board_Table.getOffset<P>(d1);
00300 NumBitmapEffect effect1=state.effectSetAt(pos1);
00301 int count=effect1.countEffect(P);
00302
00303 if(effect1.test(num)) count--;
00304 if(count==0) return false;
00305
00306 mask_t longEffect1=effect1.getMask(1)&longEffect2;
00307 while(longEffect1.any()){
00308 int num1=longEffect1.takeOneBit()+NumBitmapEffect::longToNumOffset;
00309 if(Board_Table.isBetween(pos,state.pieceOf(num1).square(),pos1))
00310 count--;
00311 if(count==0) return false;
00312 }
00313 } while (mask.any());
00314 }
00315
00316 if(move_classifier::KingOpenMove<P>::isMember(state,ptype,p.square(),pos)) return false;
00317 if(setBestMove){
00318 bestMove=Move(p.square(),pos,ptype,
00319 state.pieceAt(pos).ptype(),
00320 ptype!=p.ptype(),P);
00321 }
00322 return true;
00323 }
00324
00325 template<osl::Player P,bool setBestMove>
00326 bool osl::checkmate::ImmediateCheckmate::
00327 hasCheckmateMoveDirPiece(NumEffectState const& state, Square target,
00328 King8Info canMoveMask,Direction d,Square pos,Piece p,Move& bestMove){
00329 Square from=p.square();
00330 Ptype ptype=p.ptype();
00331
00332 {
00333 const Player altP=alt(P);
00334 Direction d1=Board_Table.getShort8Unsafe<P>(from,pos);
00335 if(d1!=DIRECTION_INVALID_VALUE){
00336 int num=state.longEffectNumTable()[p.number()][P==BLACK ? d1 : inverse(d1)];
00337 if(num != EMPTY_NUM && state.pieceOf(num).isOnBoardByOwner<altP>())
00338 return false;
00339 }
00340 }
00341 if(canPromote(ptype) &&
00342 (from.canPromote<P>() || pos.canPromote<P>())){
00343 Ptype pptype=promote(ptype);
00344 if((((canMoveMask.uint64Value()>>8)|0x100)&
00345 Immediate_Checkmate_Table.noEffectMask(pptype,d))==0){
00346 if(slowHasCheckmateMoveDirPiece<P,setBestMove>(state,target,canMoveMask,d,pos,p,pptype,bestMove)) return true;
00347 }
00348 if (ptype==PAWN || isMajorBasic(ptype))
00349 return false;
00350 }
00351 if((((canMoveMask.uint64Value()>>8)|0x100)&
00352 Immediate_Checkmate_Table.noEffectMask(ptype,d))==0){
00353 if(slowHasCheckmateMoveDirPiece<P,setBestMove>(state,target,canMoveMask,d,pos,p,ptype,bestMove)) return true;
00354 }
00355 return false;
00356 }
00357
00358 template<osl::Player P,bool setBestMove>
00359 bool osl::checkmate::ImmediateCheckmate::
00360 hasCheckmateMoveDir(NumEffectState const& state, Square target,
00361 King8Info canMoveMask,Direction d,Move& bestMove){
00362 Square pos=target-Board_Table.getOffset<P>(d);
00363 if(state.countEffect(P,pos)<2 &&
00364 !effect_util::AdditionalEffect::hasEffect(state,pos,P)) return false;
00365 PieceMask pieceMask=state.piecesOnBoard(P)&state.effectSetAt(pos);
00366 assert(pos.isOnBoard());
00367
00368 pieceMask.reset(KingTraits<P>::index);
00369 for(int i=0;i<=PieceMask::numToIndex(40);i++){
00370 mask_t mask=pieceMask.getMask(i);
00371 while (mask.any()){
00372 const int num=mask.takeOneBit()+i*32;
00373 if(hasCheckmateMoveDirPiece<P,setBestMove>(state,target,canMoveMask,d,pos,state.pieceOf(num),bestMove)) return true;
00374 }
00375 }
00376 return false;
00377 }
00378
00379
00380 template<osl::Player P,bool setBestMove>
00381 bool osl::checkmate::ImmediateCheckmate::
00382 hasCheckmateMove(NumEffectState const& state, Square target,
00383 King8Info canMoveMask,Move& bestMove)
00384 {
00385 assert(! state.inCheck());
00386 typedef misc::GeneralMask<unsigned int> mask_t;
00387 mask_t mask2=mask_t::makeDirect((canMoveMask.uint64Value()>>24)&0xff);
00388 while(mask2.any()){
00389 Direction d=static_cast<Direction>(mask2.takeOneBit());
00390 if(hasCheckmateMoveDir<P,setBestMove>(state,target,canMoveMask,d,bestMove)) return true;
00391 }
00392 return false;
00393 }
00394
00395 template<osl::Player P>
00396 bool osl::checkmate::ImmediateCheckmate::
00397 hasCheckmateMove(NumEffectState const& state, King8Info canMoveMask)
00398 {
00399 const Player altP=alt(P);
00400 const Square target=state.kingSquare(altP);
00401 assert(target.isOnBoard());
00402
00403 Move dummy;
00404 if(hasCheckmateMove<P,false>(state,target,canMoveMask,dummy)) return true;
00405 if(detail::hasCheckmateMoveKnight<P,false>(state,target,canMoveMask,dummy)) return true;
00406 return hasCheckmateDrop<P,false>(state,target,canMoveMask,dummy);
00407 }
00408
00409 template<osl::Player P>
00410 bool osl::checkmate::ImmediateCheckmate::
00411 hasCheckmateMove(NumEffectState const& state)
00412 {
00413 const Player altP=alt(P);
00414 #ifndef NDEBUG
00415 const Square target=state.kingSquare(altP);
00416 #endif
00417 assert(target.isOnBoard());
00418 King8Info canMoveMask(state.Iking8Info(altP));
00419 return hasCheckmateMove<P>(state, canMoveMask);
00420 }
00421
00422 template<osl::Player P>
00423 bool osl::checkmate::ImmediateCheckmate::
00424 hasCheckmateMove(NumEffectState const& state, King8Info canMoveMask,
00425 Square target, Move& bestMove)
00426 {
00427 assert(! state.inCheck());
00428 assert(target.isOnBoard());
00429
00430 if(hasCheckmateMove<P,true>(state,target,canMoveMask,bestMove)) return true;
00431 if(detail::hasCheckmateMoveKnight<P,true>(state,target,canMoveMask,bestMove)) return true;
00432 return hasCheckmateDrop<P,true>(state,target,canMoveMask,bestMove);
00433 }
00434
00435 template<osl::Player P>
00436 bool osl::checkmate::ImmediateCheckmate::
00437 hasCheckmateMove(NumEffectState const& state,Move& bestMove)
00438 {
00439 const Player altP=alt(P);
00440 const Square target=state.kingSquare(altP);
00441 King8Info canMoveMask(state.Iking8Info(altP));
00442 return hasCheckmateMove<P>(state, canMoveMask, target, bestMove);
00443 }
00444
00445 #endif
00446
00447
00448
00449
00450