My Project
immediateCheckmate.tcc
Go to the documentation of this file.
1/* immediateCheckmate.tcc
2 */
3#ifndef OSL_CHECKMATE_IMMEDIATE_CHECKMATE_TCC
4#define OSL_CHECKMATE_IMMEDIATE_CHECKMATE_TCC
5#include "osl/checkmate/immediateCheckmate.h"
6#include "osl/checkmate/immediateCheckmateTable.h"
7#include "osl/move_classifier/kingOpenMove.h"
8#include "osl/bits/directionTraits.h"
9#include "osl/bits/pieceTable.h"
10#include "osl/bits/mask.h"
11
12namespace osl
13{
14 namespace checkmate
15 {
16 namespace detail {
17 using osl::misc::BitOp;
18 template<Player P>
19 bool blockingVerticalAttack(NumEffectState const& state,Square pos)
20 {
21 PieceMask effect=state.effectSetAt(pos)&
22 state.effectSetAt(pos+DirectionPlayerTraits<U,P>::offset());
23 mask_t mask=effect.getMask(1); // longは常に1
24 mask&=(state.piecesOnBoard(P).getMask(1)<<8);
25 if((mask&mask_t::makeDirect(PtypeFuns<LANCE>::indexMask<<8)).none()){
26 mask&=mask_t::makeDirect(PtypeFuns<ROOK>::indexMask<<8);
27 while(mask.any()){
28 int num=mask.takeOneBit()+NumBitmapEffect::longToNumOffset;
29 Square from=state.pieceOf(num).square();
30 assert(from.isOnBoard());
31 if(from.isU<P>(pos)) goto found;
32 }
33 return false;
34 found:;
35 }
36 const Offset offset=DirectionPlayerTraits<U,P>::offset();
37 pos+=offset;
38 const Player altP=alt(P);
39 for(int i=0;i<3;i++,pos+=offset){
40 Piece p=state.pieceAt(pos);
41 if(p.canMoveOn<altP>()){ // 自分の駒か空白
42 if(state.countEffect(P,pos)==1) return true;
43 if(!p.isEmpty()) return false;
44 }
45 else return false;
46 }
47 return false;
48 }
49 template<Player P>
50 bool
51#ifdef __GNUC__
52 __attribute__ ((pure))
53#endif
54 blockingDiagonalAttack(NumEffectState const& state,Square pos,Square target,
55 King8Info canMoveMask)
56 {
57 const Player altP=alt(P);
58 Square to=target-DirectionPlayerTraits<U,P>::offset();
59 // Uに相手の駒がある
60 if((canMoveMask.uint64Value()&(0x10000<<U))==0) return false;
61 PieceMask effect=state.effectSetAt(to)&state.effectSetAt(pos);
62 mask_t mask=effect.getMask(1); // longは常に1
63 mask&=(state.piecesOnBoard(P).getMask(1)<<8);
64 mask&=mask_t::makeDirect(PtypeFuns<BISHOP>::indexMask<<8);
65 while(mask.any()){
66 int num=mask.takeOneBit()+NumBitmapEffect::longToNumOffset;
67 Square from=state.pieceOf(num).square();
68 assert(from.isOnBoard());
69 Offset offset=Board_Table.getShort8OffsetUnsafe(to,from);
70 if(to+offset != pos) continue;
71 if(state.countEffect(P,to)==1) return true;
72 // Uがspaceだと絡んでくる
73 if(!state.pieceAt(to).isEmpty()) return false;
74 Square pos1=to-offset;
75 // BISHOPの利き一つで止めていた
76 Piece p=state.pieceAt(pos1);
77 if(p.canMoveOn<altP>() &&
78 state.countEffect(P,pos1)==1){
79 return true;
80 }
81 }
82 return false;
83 }
84 template<Player P,bool canDrop,bool setBestMove>
85 bool hasKnightCheckmate(NumEffectState const& state,
86 Square target,
87 Square pos,
88 King8Info canMoveMask,
89 Move& bestMove, mask_t mask1)
90 {
91 if(!pos.isOnBoard()) return false;
92 const Player altP=alt(P);
93 Piece p=state.pieceAt(pos);
94 if(p.canMoveOn<P>() &&
95 !state.hasEffectByNotPinned(altP,pos)
96 ){
97 mask_t mask=state.effectSetAt(pos).getMask<KNIGHT>()&mask1;
98 if(mask.any()){
99 if(blockingVerticalAttack<P>(state,pos) ||
100 blockingDiagonalAttack<P>(state,pos,target,canMoveMask)) return false;
101 if(setBestMove){
102 int num=mask.takeOneBit()+(PtypeFuns<KNIGHT>::indexNum<<5);
103 Piece p1=state.pieceOf(num);
104 Square from=p1.square();
105 bestMove=Move(from,pos,KNIGHT,p.ptype(),false,P);
106 }
107 return true;
108 }
109 else if(canDrop && p.isEmpty()){
110 if(blockingVerticalAttack<P>(state,pos) ||
111 blockingDiagonalAttack<P>(state,pos,target,canMoveMask)) return false;
112 if(setBestMove)
113 bestMove=Move(pos,KNIGHT,P);
114 return true;
115 }
116 }
117 return false;
118 }
119 // KNIGHT
120 // KNIGHTのdropは利きを遮ることはない
121 template<Player P,bool setBestMove>
122 bool hasCheckmateMoveKnight(NumEffectState const& state, Square target,
123 King8Info canMoveMask,Move& bestMove)
124 {
125 // 8近傍に移動できる時は桂馬の一手詰めはない
126 if((canMoveMask.uint64Value()&0xff00)!=0) return false;
127 mask_t mask=mask_t::makeDirect(PtypeFuns<KNIGHT>::indexMask);
128 mask&=state.piecesOnBoard(P).getMask<KNIGHT>();
129 mask&= ~state.promotedPieces().getMask<KNIGHT>();
130 mask&= ~state.pinOrOpen(P).getMask<KNIGHT>();
131 if(state.hasPieceOnStand<KNIGHT>(P)){
132 Square pos=target-DirectionPlayerTraits<UUR,P>::offset();
133 if(hasKnightCheckmate<P,true,setBestMove>(state,target,pos,canMoveMask,bestMove,mask))
134 return true;
135 pos=target-DirectionPlayerTraits<UUL,P>::offset();
136 return hasKnightCheckmate<P,true,setBestMove>(state,target,pos,canMoveMask,bestMove,mask);
137 }
138 else{
139 Square pos=target-DirectionPlayerTraits<UUR,P>::offset();
140 if(hasKnightCheckmate<P,false,setBestMove>(state,target,pos,canMoveMask,bestMove,mask))
141 return true;
142 pos=target-DirectionPlayerTraits<UUL,P>::offset();
143 return hasKnightCheckmate<P,false,setBestMove>(state,target,pos,canMoveMask,bestMove,mask);
144 }
145 return false;
146 }
147 template<Player P,bool setBestMove>
148 bool slowCheckDrop(NumEffectState const& state,Square target,
149 Ptype ptype,King8Info canMoveMask,Move& bestMove)
150 {
151 unsigned int dropMask=(canMoveMask.uint64Value()&0xff)
152 &Immediate_Checkmate_Table.ptypeDropMask(ptype,canMoveMask);
153 // dropMaskが0ならここに来ない
154 assert(dropMask!=0);
155 while(dropMask!=0){
156 int i=BitOp::takeOneBit(dropMask);
157 Direction d=static_cast<Direction>(i);
158 unsigned int blockingMask=Immediate_Checkmate_Table.blockingMask(ptype,d) &
159 (canMoveMask.uint64Value()>>16);
160 Square drop=target-Board_Table.getOffset<P>(d);
161 if(blockingMask!=0){
162 NumBitmapEffect effect=state.effectSetAt(drop);
163 mask_t longEffect=effect.getMask(1)&NumBitmapEffect::longEffectMask();
164 longEffect&=(state.piecesOnBoard(P).getMask(1)<<8);
165 if(longEffect.any()){
166 do{
167 int j=BitOp::takeOneBit(blockingMask);
168 Direction d1=static_cast<Direction>(j);
169 Square pos=target-Board_Table.getOffset<P>(d1);
170 NumBitmapEffect effect1=state.effectSetAt(pos);
171 if(effect1.countEffect(P)>1) continue;
172 mask_t longEffect1=effect1.getMask(1)&longEffect;
173 if(!longEffect1.any()) continue;
174 //
175 int num=longEffect1.takeOneBit()+NumBitmapEffect::longToNumOffset;
176 if(Board_Table.isBetween(drop,state.pieceOf(num).square(),pos))
177 goto tryNext;
178 }while(blockingMask!=0);
179 }
180 }
181 // blockingMaskの点がすべてOKならOK
182 if(setBestMove)
183 bestMove=Move(drop,ptype,P);
184 return true;
185 tryNext:;
186 }
187 return false;
188 }
189 } // detail
190 } // checkmate
191} // osl
192
193// not KNIGHT
194template<osl::Player P,bool setBestMove>
195bool osl::checkmate::ImmediateCheckmate::
196hasCheckmateDrop(NumEffectState const& state, Square target,
197 King8Info canMoveMask,Move& bestMove)
198{
199 typedef misc::GeneralMask<unsigned short> mask_t;
200 mask_t dropPtypeMask=mask_t::makeDirect(Immediate_Checkmate_Table.dropPtypeMask(canMoveMask));
201 while(dropPtypeMask.any()){
202 Ptype ptype=static_cast<Ptype>(dropPtypeMask.takeOneBit()+PTYPE_BASIC_MIN);
203 if(state.hasPieceOnStand(P,ptype) &&
204 detail::slowCheckDrop<P,setBestMove>(state,target,ptype,canMoveMask,
205 bestMove))
206 return true;
207 }
208 return false;
209}
210
211template<osl::Player P,bool setBestMove>
212bool osl::checkmate::ImmediateCheckmate::
213slowHasCheckmateMoveDirPiece(NumEffectState const& state, Square target,
214 King8Info canMoveMask,Direction d,Square pos,Piece p,Ptype ptype,Move& bestMove){
215 const Player altP=alt(P);
216 // ptypeがPROOKの時は,更なるチェックが必要
217 if(ptype==PROOK){
218 int dx=target.x()-pos.x();
219 int dy=target.y()-pos.y();
220 if(abs(dx)==1 && abs(dy)==1){
221 {
222 Square pos1=pos+Offset(dx,0);
223 Piece p1=state.pieceAt(pos1);
224 if(!p1.isEmpty()){
225 {
226 // * -OU *
227 // (A)(B)(D)
228 // * (C) *
229 // (E) * *
230 // +RY (C) -> (A), (E) -> (A)
231 // -?? - (B)
232 // (D) - 竜以外の利きなし
233 Square pos2=pos+Offset(2*dx,0);
234 if(state.pieceAt(pos2).template canMoveOn<altP>()){
235 NumBitmapEffect effect2=state.effectSetAt(pos2);
236 if(effect2.countEffect(P)==0 ||
237 (effect2.countEffect(P)==1 &&
238 effect2.test(p.number())))
239 return false;
240 }
241 }
242 {
243 // * -OU *
244 // (A)(B) *
245 // * (C) *
246 // +RY (C) -> (A)
247 // -?? - (B)竜でpinされているが実はAへの利き持つ
248 if(p.square()==target-Offset(0,2*dy) &&
249 state.hasEffectByPiece(p1,pos))
250 return false;
251 }
252 }
253 }
254 {
255 Square pos1=pos+Offset(0,dy);
256 Piece p1=state.pieceAt(pos1);
257 if(!p1.isEmpty()){
258 Square pos2=pos+Offset(0,2*dy);
259 {
260 if(state.pieceAt(pos2).template canMoveOn<altP>()){
261 NumBitmapEffect effect2=state.effectSetAt(pos2);
262 if(effect2.countEffect(P)==0 ||
263 (effect2.countEffect(P)==1 &&
264 effect2.test(p.number())))
265 return false;
266
267 }
268 {
269 // (C)(B)-OU
270 // * (A) *
271 // +RY (C) -> (A)
272 // -?? - (B)竜でpinされているが実はAへの利き持つ
273 if(p.square()==target-Offset(2*dx,0) &&
274 state.hasEffectByPiece(p1,pos))
275 return false;
276 }
277 }
278 }
279 }
280 }
281 }
282 // 元々2つの利きがあったマスが,
283 // block & 自分の利きの除去で利きがなくなることはあるか?
284 // -> ある.
285 // +KA * *
286 // * (A) +KI
287 // * -OU (B)
288 // * * *
289 // で金がAに移動して王手をかけると,Bの利きが2から0になる.
290 mask_t mask=mask_t::makeDirect((canMoveMask.uint64Value()>>16)&Immediate_Checkmate_Table.noEffectMask(ptype,d));
291 if(mask.any()){
292 int num=p.number();
293 NumBitmapEffect effect2=state.effectSetAt(pos);
294 effect2.reset(num+8);
295 mask_t longEffect2=effect2.getMask(1)&NumBitmapEffect::longEffectMask();
296 longEffect2&=(state.piecesOnBoard(P).getMask(1)<<8);
297 do {
298 Direction d1=static_cast<Direction>(mask.takeOneBit());
299 Square pos1=target-Board_Table.getOffset<P>(d1);
300 NumBitmapEffect effect1=state.effectSetAt(pos1);
301 int count=effect1.countEffect(P);
302 // 自分の利きの除去
303 if(effect1.test(num)) count--;
304 if(count==0) return false;
305 // blockしている利きの除去
306 mask_t longEffect1=effect1.getMask(1)&longEffect2;
307 while(longEffect1.any()){
308 int num1=longEffect1.takeOneBit()+NumBitmapEffect::longToNumOffset;
309 if(Board_Table.isBetween(pos,state.pieceOf(num1).square(),pos1))
310 count--;
311 if(count==0) return false;
312 }
313 } while (mask.any());
314 }
315 // 自殺手でないことのチェックを入れる
316 if(move_classifier::KingOpenMove<P>::isMember(state,ptype,p.square(),pos)) return false;
317 if(setBestMove){
318 bestMove=Move(p.square(),pos,ptype,
319 state.pieceAt(pos).ptype(),
320 ptype!=p.ptype(),P);
321 }
322 return true;
323}
324
325template<osl::Player P,bool setBestMove>
326bool osl::checkmate::ImmediateCheckmate::
327hasCheckmateMoveDirPiece(NumEffectState const& state, Square target,
328 King8Info canMoveMask,Direction d,Square pos,Piece p,Move& bestMove){
329 Square from=p.square();
330 Ptype ptype=p.ptype();
331 // 相手の利きが伸びてしまって移動後も利きがついてくる可能性
332 {
333 const Player altP=alt(P);
334 Direction d1=Board_Table.getShort8Unsafe<P>(from,pos);
335 if(d1!=DIRECTION_INVALID_VALUE){ // not knight move
336 int num=state.longEffectNumTable()[p.number()][P==BLACK ? d1 : inverse(d1)];
337 if(num != EMPTY_NUM && state.pieceOf(num).isOnBoardByOwner<altP>())
338 return false;
339 }
340 }
341 if(canPromote(ptype) &&
342 (from.canPromote<P>() || pos.canPromote<P>())){
343 Ptype pptype=promote(ptype);
344 if((((canMoveMask.uint64Value()>>8)|0x100)&
345 Immediate_Checkmate_Table.noEffectMask(pptype,d))==0){
346 if(slowHasCheckmateMoveDirPiece<P,setBestMove>(state,target,canMoveMask,d,pos,p,pptype,bestMove)) return true;
347 }
348 if (ptype==PAWN || /*basic because canpromote*/isMajorBasic(ptype))
349 return false;
350 }
351 if((((canMoveMask.uint64Value()>>8)|0x100)&
352 Immediate_Checkmate_Table.noEffectMask(ptype,d))==0){
353 if(slowHasCheckmateMoveDirPiece<P,setBestMove>(state,target,canMoveMask,d,pos,p,ptype,bestMove)) return true;
354 }
355 return false;
356}
357
358template<osl::Player P,bool setBestMove>
359bool osl::checkmate::ImmediateCheckmate::
360hasCheckmateMoveDir(NumEffectState const& state, Square target,
361 King8Info canMoveMask,Direction d,Move& bestMove){
362 Square pos=target-Board_Table.getOffset<P>(d);
363 if(state.countEffect(P,pos)<2 &&
364 !effect_util::AdditionalEffect::hasEffect(state,pos,P)) return false;
365 PieceMask pieceMask=state.piecesOnBoard(P)&state.effectSetAt(pos);
366 assert(pos.isOnBoard());
367 // 玉で王手をかけない
368 pieceMask.reset(KingTraits<P>::index);
369 for(int i=0;i<=PieceMask::numToIndex(40);i++){
370 mask_t mask=pieceMask.getMask(i);
371 while (mask.any()){
372 const int num=mask.takeOneBit()+i*32;
373 if(hasCheckmateMoveDirPiece<P,setBestMove>(state,target,canMoveMask,d,pos,state.pieceOf(num),bestMove)) return true;
374 }
375 }
376 return false;
377}
378
379// not KNIGHT
380template<osl::Player P,bool setBestMove>
381bool osl::checkmate::ImmediateCheckmate::
382hasCheckmateMove(NumEffectState const& state, Square target,
383 King8Info canMoveMask,Move& bestMove)
384{
385 assert(! state.inCheck());
386 typedef misc::GeneralMask<unsigned int> mask_t;
387 mask_t mask2=mask_t::makeDirect((canMoveMask.uint64Value()>>24)&0xff);
388 while(mask2.any()){
389 Direction d=static_cast<Direction>(mask2.takeOneBit());
390 if(hasCheckmateMoveDir<P,setBestMove>(state,target,canMoveMask,d,bestMove)) return true;
391 }
392 return false;
393}
394
395template<osl::Player P>
396bool osl::checkmate::ImmediateCheckmate::
397hasCheckmateMove(NumEffectState const& state, King8Info canMoveMask)
398{
399 const Player altP=alt(P);
400 const Square target=state.kingSquare(altP);
401 assert(target.isOnBoard());
402 // 相手からの王手がかかっていない
403 Move dummy;
404 if(hasCheckmateMove<P,false>(state,target,canMoveMask,dummy)) return true;
405 if(detail::hasCheckmateMoveKnight<P,false>(state,target,canMoveMask,dummy)) return true;
406 return hasCheckmateDrop<P,false>(state,target,canMoveMask,dummy);
407}
408
409template<osl::Player P>
410bool osl::checkmate::ImmediateCheckmate::
411hasCheckmateMove(NumEffectState const& state)
412{
413 const Player altP=alt(P);
414#ifndef NDEBUG
415 const Square target=state.kingSquare(altP);
416#endif
417 assert(target.isOnBoard());
418 King8Info canMoveMask(state.Iking8Info(altP));
419 return hasCheckmateMove<P>(state, canMoveMask);
420}
421
422template<osl::Player P>
423bool osl::checkmate::ImmediateCheckmate::
424hasCheckmateMove(NumEffectState const& state, King8Info canMoveMask,
425 Square target, Move& bestMove)
426{
427 assert(! state.inCheck());
428 assert(target.isOnBoard());
429
430 if(hasCheckmateMove<P,true>(state,target,canMoveMask,bestMove)) return true;
431 if(detail::hasCheckmateMoveKnight<P,true>(state,target,canMoveMask,bestMove)) return true;
432 return hasCheckmateDrop<P,true>(state,target,canMoveMask,bestMove);
433}
434
435template<osl::Player P>
436bool osl::checkmate::ImmediateCheckmate::
437hasCheckmateMove(NumEffectState const& state,Move& bestMove)
438{
439 const Player altP=alt(P);
440 const Square target=state.kingSquare(altP);
441 King8Info canMoveMask(state.Iking8Info(altP));
442 return hasCheckmateMove<P>(state, canMoveMask, target, bestMove);
443}
444
445#endif /* OSL_CHECKMATE_IMMEDIATE_CHECKMATE_TCC */
446// ;;; Local Variables:
447// ;;; mode:c++
448// ;;; c-basic-offset:2
449// ;;; End:
450