All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
moveStackRejections.cc
Go to the documentation of this file.
1 /* moveStackRejections.cc
2  */
4 #include "osl/ptypeTable.h"
5 #include "osl/boardTable.h"
7 #include "osl/misc/carray.h"
8 #include "osl/misc/lightMutex.h"
9 #include "osl/eval/evalTraits.h"
10 #include "osl/oslConfig.h"
11 
12 #ifdef SHOW_PROBE_COUNTER
13 #include <iostream>
14 #endif
15 
16 
17 std::ostream& osl::search::operator<<(std::ostream& os,osl::search::OnBoardElement const& mp)
18 {
19  return os << "[" << mp.pos() << "," << mp.ptypeO() << "]";
20 }
21 
22 std::ostream& osl::search::operator<<(std::ostream& os,osl::search::StandElements const& mp)
23 {
24  os << "[";
25  for(int ptypeIndex=8;ptypeIndex<=15;ptypeIndex++)
26  os << (int)mp.v.c8[ptypeIndex-osl::PTYPE_BASIC_MIN] << ",";
27  return os << "]";
28 }
31 {
32  short posPtypeO=OnBoardElement::makePosPtypeO(pos,ptypeO);
33  for(size_t i=0;i<myOnboardMinus.size();++i){
34  if(myOnboardMinus[i].posPtypeO==posPtypeO){
36  myOnboardMinus.pop_back();
37  return;
38  }
39  }
40  myOnboardPlus.push_back(OnBoardElement(pos,ptypeO));
41 }
44 {
45  short posPtypeO=OnBoardElement::makePosPtypeO(pos,ptypeO);
46  for(size_t i=0;i<myOnboardPlus.size();++i){
47  if(myOnboardPlus[i].posPtypeO==posPtypeO){
48  myOnboardPlus[i]=myOnboardPlus[myOnboardPlus.size()-1];
49  myOnboardPlus.pop_back();
50  return;
51  }
52  }
53  myOnboardMinus.push_back(OnBoardElement(pos,ptypeO));
54 }
57 {
58  short posPtypeO=OnBoardElement::makePosPtypeO(pos,ptypeO);
59  for(size_t i=0;i<opOnboardMinus.size();++i){
60  if(opOnboardMinus[i].posPtypeO==posPtypeO){
61  opOnboardMinus[i]=opOnboardMinus[opOnboardMinus.size()-1];
62  opOnboardMinus.pop_back();
63  return;
64  }
65  }
66  opOnboardPlus.push_back(OnBoardElement(pos,ptypeO));
67 }
70 {
71  short posPtypeO=OnBoardElement::makePosPtypeO(pos,ptypeO);
72  for(size_t i=0;i<opOnboardPlus.size();++i){
73  if(opOnboardPlus[i].posPtypeO==posPtypeO){
74  opOnboardPlus[i]=opOnboardPlus[opOnboardPlus.size()-1];
75  opOnboardPlus.pop_back();
76  return;
77  }
78  }
79  opOnboardMinus.push_back(OnBoardElement(pos,ptypeO));
80 }
82 {
83  stand.add(ptype);
84 }
86 {
87  stand.sub(ptype);
88 }
90 {
91  if(move.isDrop()){
92  addMyBoard(move.to(),move.ptypeO());
93  addStand(move.ptype());
94  }
95  else{
96  if(move.isCapture()){
97  subOpBoard(move.to(),move.capturePtypeO());
98  subStand(unpromote(getPtype(move.capturePtypeO()))); // 相手にとって
99  addMyBoard(move.to(),move.ptypeO());
100  subMyBoard(move.from(),move.oldPtypeO());
101  }
102  else{
103  addMyBoard(move.to(),move.ptypeO());
104  subMyBoard(move.from(),move.oldPtypeO());
105  }
106  }
107 }
109 {
110  if(move.isDrop()){
111  addOpBoard(move.to(),move.ptypeO());
112  subStand(move.ptype());
113  }
114  else{
115  if(move.isCapture()){
116  subMyBoard(move.to(),move.capturePtypeO());
117  addStand(unpromote(getPtype(move.capturePtypeO()))); // 相手にとって
118  addOpBoard(move.to(),move.ptypeO());
119  subOpBoard(move.from(),move.oldPtypeO());
120  }
121  else{
122  addOpBoard(move.to(),move.ptypeO());
123  subOpBoard(move.from(),move.oldPtypeO());
124  }
125  }
126 }
127 
131 template<osl::Player P>
134  osl::search::OnBoardElement const& fromElement,
135  osl::search::OnBoardElement const& toElement,Move lastMove) const
136 {
137  Square from=fromElement.pos(), to=toElement.pos();
138  PtypeO fromPtypeO=fromElement.ptypeO(), toPtypeO=toElement.ptypeO();
139 
140  if(fromPtypeO!=toPtypeO &&
141  (fromPtypeO!=unpromote(toPtypeO) ||
142  (!from.canPromote<P>() && !to.canPromote<P>())))
143  return false;
144  EffectContent effect=Ptype_Table.getEffect(fromPtypeO,from,to);
145  if(!effect.hasEffect()) return false;
146  if(effect.hasUnblockableEffect()) return true;
147  Offset o=effect.offset();
148  Square moveTo=lastMove.to(),moveFrom=lastMove.from();
149  Square pos=from+o;
150  for (;; pos+=o) {
151  if(pos==to) return true;
152  if(pos==moveTo) return false;
153  if(!state.pieceAt(pos).isEmpty()){
154  if(pos==moveFrom){
155  for (pos+=o;; pos+=o) {
156  if(pos==to) return true;
157  if(pos==moveTo) return false;
158  if(!state.pieceAt(pos).isEmpty()){
159  break;
160  }
161  }
162  }
163  break;
164  }
165  }
166  return false;
167 }
168 
169 template<osl::Player P>
172  osl::search::OnBoardElement const& fromElement,
173  osl::search::OnBoardElement const& toElement,
174  osl::search::OnBoardElement const& captureElement,
175  osl::Move lastMove) const
176 {
177  Square to=toElement.pos();
178  if(to!=captureElement.pos()) return false;
179  Square from=fromElement.pos();
180  PtypeO fromPtypeO=fromElement.ptypeO(), toPtypeO=toElement.ptypeO();
181 
182  if(fromPtypeO!=toPtypeO &&
183  (fromPtypeO!=unpromote(toPtypeO) ||
184  (!from.canPromote<P>() && !to.canPromote<P>())))
185  return false;
186  EffectContent effect=Ptype_Table.getEffect(fromPtypeO,from,to);
187  if(!effect.hasEffect()) return false;
188  if(effect.hasUnblockableEffect()) return true;
189  Offset o=effect.offset();
190  Square moveTo=lastMove.to(),moveFrom=lastMove.from();
191  Square pos=from+o;
192  for (;; pos+=o) {
193  if(pos==to) return true;
194  if(pos==moveTo) return false;
195  if(!state.pieceAt(pos).isEmpty()){
196  if(pos==moveFrom){
197  for (pos+=o;; pos+=o) {
198  if(pos==to) return true;
199  if(pos==moveTo) return false;
200  if(!state.pieceAt(pos).isEmpty()){
201  break;
202  }
203  }
204  }
205  break;
206  }
207  }
208  return false;
209 }
220 template<osl::Player P>
221 bool osl::search::StateElements::canReject(osl::state::NumEffectState const& state,bool mayRejectSennichite,bool isRootMove,Move lastMove,Move actualMove) const
222 {
224  switch(myOnboardPlus.size()){
225  case 0:
226  switch(opOnboardPlus.size()){
227  case 1: // myPlus=0, opPlus=1
228  if(opOnboardMinus.size()==1 && myOnboardMinus.size()==0){
229  // op simple move
230  if(validSimpleMove<altP>(state,opOnboardPlus[0],opOnboardMinus[0],lastMove)){
231  if(!mayRejectSennichite && stand.isZero()){
232  return false;
233  }
234  return stand.geZero();
235  }
236  }
237  return false;
238  case 0: // myPlus=0, opPlus=0
239  if(opOnboardMinus.size()==1){
240  if(myOnboardMinus.size()==0){
241  StandElements localStand(stand);
242  // op drop move
243  Ptype ptype=getPtype(opOnboardMinus[0].ptypeO());
244  if(!isPromoted(ptype)){
245  localStand.sub(ptype);
246  if(!mayRejectSennichite && localStand.isZero()){
247  return false;
248  }
249  return localStand.geZero();
250  }
251  }
252  }
253  else{ // pass moves (including piece loosing cases)
254  if(opOnboardMinus.size()==0 && myOnboardMinus.size()==0){
255  if(isRootMove) return stand.gtZero();
256  else return stand.geZero();
257  }
258  }
259  return false;
260  default: return false;
261  }
262  case 1: // myPlus=1
263  switch(myOnboardMinus.size()){
264  case 1: // myPlus=1, myMinus=1
265  switch(opOnboardMinus.size()){
266  case 1: // myPlus=1, myMinus=1, opMinus=1
267  if(opOnboardPlus.size()==0){ // my capture move
268  if(validCaptureMove<P>(state,myOnboardMinus[0],myOnboardPlus[0],opOnboardMinus[0],lastMove))
269  {
270  StandElements localStand(stand);
271  Ptype capturePtype=unpromote(getPtype(opOnboardMinus[0].ptypeO()));
272  // altPに関して減りすぎた分を増やす?
273  // 相手に取って減っているはずなので,それをキャンセルする
274  localStand.add(capturePtype);
275  if(localStand.isZero()){
276  assert(actualMove.player()==P);
277  if(!mayRejectSennichite &&
278  actualMove.ptypeO()==myOnboardPlus[0].ptypeO() &&
279  actualMove.from()==myOnboardMinus[0].pos() &&
280  actualMove.to()==myOnboardPlus[0].pos()) return false;
281  return true;
282  }
283  return localStand.geZero();
284  }
285  }
286  return false;
287  case 0: // myPlus=1, myMinus=1, opMinus=0
288  if(opOnboardPlus.size()==0){ // my simple move
289  if(validSimpleMove<P>(state,myOnboardMinus[0],myOnboardPlus[0],lastMove)){
290  if(stand.isZero()){
291  assert(actualMove.player()==P);
292  if(!mayRejectSennichite &&
293  actualMove.ptypeO()==myOnboardPlus[0].ptypeO() &&
294  actualMove.from()==myOnboardMinus[0].pos() &&
295  actualMove.to()==myOnboardPlus[0].pos()) return false;
296  return true;
297  }
298  return stand.geZero();
299  }
300  }
301  return false;
302  }
303  case 0: // myPlus=1, myMinus=0
304  if(opOnboardPlus.size()==1){
305  if(opOnboardMinus.size()==1){
306  if(validCaptureMove<altP>(state,opOnboardPlus[0],opOnboardMinus[0],myOnboardPlus[0],lastMove))
307  {
308  StandElements localStand(stand);
309  Ptype capturePtype=unpromote(getPtype(myOnboardPlus[0].ptypeO()));
310  // 次のmoveを実行すると相手に取っては増える.
311  localStand.add(capturePtype);
312  if(!mayRejectSennichite && localStand.isZero()){
313  return false;
314  }
315  return localStand.geZero();
316  }
317  }
318  else return false;
319  }
320  else if(opOnboardPlus.size()==0 && opOnboardMinus.size()==0
321  && !isPromoted(myOnboardPlus[0].ptypeO()) ){
322  // my drop move
323  StandElements localStand(stand);
324  localStand.sub(getPtype(myOnboardPlus[0].ptypeO()));
325  if(localStand.isZero()){
326  if(!mayRejectSennichite &&
327  actualMove.ptypeO()==myOnboardPlus[0].ptypeO() &&
328  actualMove.isDrop() &&
329  actualMove.to()==myOnboardPlus[0].pos()) return false;
330  return true;
331  }
332  return localStand.geZero();
333  }
334  }
335  default: return false;
336  }
337 }
338 
339 std::ostream& osl::search::operator<<(std::ostream& os,osl::search::StateElements const& mps)
340 {
341  {
342  os << "[ MyOnboardPlus(";
343  for(size_t i=0;i<mps.myOnboardPlus.size();i++)
344  os << mps.myOnboardPlus[i] << ",\n";
345  os << "),";
346  }
347  {
348  os << "[ MyOnboardMinus(";
349  for(size_t i=0;i<mps.myOnboardMinus.size();i++)
350  os << mps.myOnboardMinus[i] << ",\n";
351  os << "),";
352  }
353  {
354  os << "[ OpOnboardPlus(";
355  for(size_t i=0;i<mps.opOnboardPlus.size();i++)
356  os << mps.opOnboardPlus[i] << ",\n";
357  os << "),";
358  }
359  {
360  os << "[ OpOnboardMinus(";
361  for(size_t i=0;i<mps.opOnboardMinus.size();i++)
362  os << mps.opOnboardMinus[i] << ",\n";
363  os << "),";
364  }
365  return os << "Stand(" << mps.stand << ") ]\n" << std::endl;
366 }
367 
368 #ifdef SHOW_PROBE_COUNTER
369 struct ProbeCounter{
370 #ifdef OSL_USE_RACE_DETECTOR
371  osl::LightMutex mutex;
372 #endif
374  ProbeCounter(){}
375  void incCheck(int d){
376 #ifdef OSL_USE_RACE_DETECTOR
377  osl::LightMutex::scoped_lock lk(mutex);
378 #endif
379  check[d]++;
380  }
381  void incHit(int d){
382 #ifdef OSL_USE_RACE_DETECTOR
383  osl::LightMutex::scoped_lock lk(mutex);
384 #endif
385  hit[d]++;
386  }
387  ~ProbeCounter(){
388  for(int i=0;i<1024;i++){
389  if(check[i]!=0){
390  std::cerr << i << " : " << hit[i] << "/" << check[i] << std::endl;
391  }
392  }
393  }
394 };
395 ProbeCounter probeCounter;
396 #endif
397 
398 template<osl::Player P>
400 probe(osl::state::NumEffectState const& state,osl::container::MoveStack const& history,int ply,osl::Move const& m,int alpha,int checkCountOfAltP)
401 {
402  StateElements elements;
403  elements.addMyMove(m);
404  assert(m.player()==P);
405  bool existNormal=false;
406  for(int i=1;i<ply;i+=2){
407  Move m1=history.lastMove(i);
408  if(m1.isNormal()){
409  assert(m1.player()==alt(P));
410  elements.addOpMove(m1);
411  existNormal=true;
412  }
413  else if(m1.isInvalid()) return false;
414  if(elements.isLoop()){
415  bool mayRejectSennichite=osl::eval::notLessThan(P,alpha,0) && (i>checkCountOfAltP*2-1);
416  if(elements.stand.isZero()){
417  if(mayRejectSennichite) return true;
418  }
419  else if(elements.stand.geZero()) return true;
420  }
421  Move m2=history.lastMove(i+1);
422  if(m2.isNormal()){
423  assert(m2.player()==P);
424  elements.addMyMove(m2);
425  existNormal=true;
426  }
427  else if(m2.isInvalid()) return false;
428 #ifdef SHOW_PROBE_COUNTER
429  probeCounter.incCheck(i);
430 #endif
431  // i==1 -- checkCount=1
432  // i==3 -- checkCount=2
433  bool mayRejectSennichite=osl::eval::notLessThan(P,alpha,0) && (i>checkCountOfAltP*2-1);
434  bool isRootMove=(i == ply-1);
435  if(
436  existNormal &&
437  elements.canReject<P>(state,mayRejectSennichite,isRootMove,m,m2)
438  ){
439 #ifdef SHOW_PROBE_COUNTER
440  probeCounter.incHit(i);
441 #endif
442  return true;
443  }
444  }
445  return false;
446 }
447 namespace osl
448 {
449  namespace search
450  {
451  template bool MoveStackRejections::probe<BLACK>(
452  osl::state::NumEffectState const& state,osl::container::MoveStack const& history,int ply,osl::Move const& m,int alpha, int checkCountOfAltP);
453  template bool MoveStackRejections::probe<WHITE>(
454  osl::state::NumEffectState const& state,osl::container::MoveStack const& history,int ply,osl::Move const& m,int alpha,int checkCountOfAltP);
455  }
456 }
457 
458 
459 // ;;; Local Variables:
460 // ;;; mode:c++
461 // ;;; c-basic-offset:2
462 // ;;; End:
463