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