My Project
proofNumberTable.cc
Go to the documentation of this file.
1 /* proofNumberTable.cc
2  */
6 #include "osl/bits/boardTable.h"
7 #include "osl/bits/ptypeTable.h"
8 #include "osl/oslConfig.h"
9 
12 
13 namespace {
14  namespace ProofNumberTable {
18  });
19  }
20 }
21 
22 namespace osl
23 {
24  namespace
25  {
26  using namespace osl::checkmate;
30  const checkmate::ProofNumberTable::Liberty
31  effectiveCheckShort(Ptype ptype,Direction dir,unsigned int mask)
32  {
33  assert(isShort(dir));
34  // 王は8近傍に移動できない
35  if (ptype==KING)
36  return ProofNumberTable::Liberty(0,false);
37  // ptypeがdir方向に利きを持たない場合も空王手の場合があるので作成
38  const bool has_effect
39  = (Ptype_Table.getMoveMask(ptype)
40  & (dirToMask(dir) | dirToMask(shortToLong(dir))));
41  int dx=Board_Table.getDxForBlack(dir);
42  int dy=Board_Table.getDyForBlack(dir);
43  int count = 0;
44  for (int l=0;l<8;l++) {
45  if ((mask&(1<<l))==0)
46  continue;
47  Direction dir1=static_cast<Direction>(l);
48  int dx1=Board_Table.getDxForBlack(dir1);
49  int dy1=Board_Table.getDyForBlack(dir1);
50  Offset32 o32(dx-dx1,dy-dy1);
51  if ((dx != dx1 || dy != dy1)
52  && !Ptype_Table.getEffect(newPtypeO(BLACK,ptype),o32).hasEffect())
53  ++count;
54  }
55  return ProofNumberTable::Liberty(std::max(count,1), has_effect);
56  }
57  const checkmate::ProofNumberTable::Liberty
58  effectiveCheckLong(Ptype ptype,Direction dir,unsigned int mask)
59  {
60  assert(isLong(dir));
61  // ptypeがdir方向に利きを持たなくても2マス離れた空王手で8近傍に
62  // 利きが増える場合があるので作成
63  const bool has_effect
64  = (Ptype_Table.getMoveMask(ptype) & dirToMask(dir));
65  int dx=Board_Table.getDxForBlack(dir)*2; // 1マス遠くから
66  int dy=Board_Table.getDyForBlack(dir)*2;
67  int count = 0;
68  for (int l=0;l<8;l++) {
69  if ((mask&(1<<l))==0)
70  continue;
71  Direction dir1=static_cast<Direction>(l);
72  int dx1=Board_Table.getDxForBlack(dir1);
73  int dy1=Board_Table.getDyForBlack(dir1);
74  Offset32 o32(dx-dx1,dy-dy1);
75  if (!Ptype_Table.getEffect(newPtypeO(BLACK,ptype),o32).hasEffect())
76  ++count;
77  }
78  return ProofNumberTable::Liberty(std::max(count,1), has_effect);
79  }
80  }
81 }
82 
85 {
86  // liberties
87  for (int i=0; i<0x100; i++) {
88  for (int k=PTYPE_PIECE_MIN; k<=PTYPE_MAX; k++) {
89  const Ptype ptype=static_cast<Ptype>(k);
90  assert(isPiece(ptype));
91  for (int j=0; j<8; j++) {
92  Direction dir=static_cast<Direction>(j);
93  const Liberty e = effectiveCheckShort(ptype,dir,i);
94  liberties[i][k][j] = e;
95  }
96  int longs = 0;
97  for (int j=LONG_DIRECTION_MIN; j<=LONG_DIRECTION_MAX; ++j,++longs) {
98  Direction dir=static_cast<Direction>(j);
99  const Liberty e = effectiveCheckLong(ptype,dir,i);
100  liberties[i][k][j] = e;
101  }
102  assert(longs == 8);
103  }
104  }
105  // drop_liberty
106  drop_liberty.fill(0);
107  for(int i=0;i<0x10000;i++){
108  const unsigned int liberty = (i>>8)&0xff;
109  const int liberty_count = misc::BitOp::countBit(liberty);
110  if (liberty_count <= 2)
111  continue; // low enough
112 
113  for (int k=PTYPE_BASIC_MIN;k<=PTYPE_MAX;k++) {
114  int minimum_liberty = liberty_count;
115  Ptype ptype=static_cast<Ptype>(k);
116  if (ptype == KING)
117  continue;
118  for (int j=0;j<8;j++) {
119  // 有効王手でない
120  if ((i&(0x1<<j))==0)
121  continue;
122  if ((i&(0x100<<j))!=0)
123  continue;
124  const Direction dir=static_cast<Direction>(j);
125  // ptypeがdir方向に利きを持つか
126  const bool has_effect
127  = (Ptype_Table.getMoveMask(ptype)
128  & (dirToMask(dir) | dirToMask(shortToLong(dir))));
129  if (! has_effect)
130  continue;
131  const int e = liberties[liberty][k][j].liberty;
132  assert(e);
133  minimum_liberty = std::min(minimum_liberty, e);
134  }
135  for (int l=minimum_liberty; l<liberty_count; ++l)
136  {
137  drop_liberty[i][l] |= (1<<(ptype-GOLD));
138  }
139  }
140  }
141  // pmajor_liberty
142  pmajor_liberty.fill(8);
143  for (int l=0; l<0x100; l++) { // liberty
144  for (int m=0; m<0x100; m++) { // move_mask
145  if (l & m)
146  continue;
147  int min_liberty = std::max(2,misc::BitOp::countBit(l))-1;
148  if (min_liberty > 1)
149  {
150  for (int j=0; j<8; j++) {
151  if ((m&(0x1<<j))==0)
152  continue;
153  const int pr = liberties[l][PROOK][j].liberty;
154  const int pb = liberties[l][PBISHOP][j].liberty;
155  min_liberty = std::min(min_liberty, std::min(pr,pb));
156  assert(min_liberty);
157  }
158  }
159  pmajor_liberty[l][m] = min_liberty;
160  }
161  }
162  // promote_liberty
163  promote_liberty.fill(8);
164  for (int l=0; l<0x100; l++) { // liberty
165  for (int m=0; m<0x100; m++) { // move_mask
166  if (l & m)
167  continue;
168  int min_liberty = std::max(2,misc::BitOp::countBit(l))-1;
169  if (min_liberty > 1)
170  {
171  for (int j=0; j<8; j++) {
172  if ((m&(0x1<<j))==0)
173  continue;
174  for (int k=PTYPE_BASIC_MIN;k<=PTYPE_MAX;k++) {
175  Ptype ptype=static_cast<Ptype>(k);
176  if (ptype == KING || ptype == PROOK || ptype == PBISHOP)
177  continue;
178  Liberty e = liberties[l][k][j];
179  if (! e.has_effect)
180  continue;
181  assert(e.liberty);
182  min_liberty = std::min(min_liberty, (int)e.liberty);
183  assert(min_liberty);
184  }
185  }
186  }
187  promote_liberty[l][m] = min_liberty;
188  }
189  }
190  // other_move_liberty
191  other_move_liberty.fill(8);
192  for (int l=0; l<0x100; l++) { // liberty
193  for (int m=0; m<0x100; m++) { // move_mask
194  if (l & m)
195  continue;
196  int min_liberty = std::max(2,misc::BitOp::countBit(l))-1;
197  if (min_liberty > 1)
198  {
199  for (int j=0; j<8; j++) {
200  if ((m&(0x1<<j))==0)
201  continue;
202  for (int k=PTYPE_BASIC_MIN;k<=PTYPE_MAX;k++) {
203  Ptype ptype=static_cast<Ptype>(k);
204  if (ptype == KING || ptype == PROOK || ptype == PBISHOP)
205  continue;
206  if (j == U
207  && (ptype == GOLD || ptype == PPAWN || ptype == PLANCE
208  || ptype == PKNIGHT || ptype == PSILVER))
209  continue;
210  Liberty e = liberties[l][k][j];
211  if (! e.has_effect)
212  continue;
213  assert(e.liberty);
214  min_liberty = std::min(min_liberty, (int)e.liberty);
215  assert(min_liberty);
216  }
217  }
218  }
219  other_move_liberty[l][m] = min_liberty;
220  }
221  }
222 }
223 
225 ProofNumberTable::countLiberty(const NumEffectState& state, Move move) const
226 {
227  const Player attack = move.player();
228  const Square king = state.kingSquare(alt(attack));
229  const King8Info info(state.Iking8Info(alt(attack)));
230  return countLiberty(state, info.libertyCount(), move, king, info);
231 }
232 
235  King8Info info) const
236 {
237  assert(state.turn() == attack);
238  int result = info.libertyCount()-1;
239  if (result < 2)
240  return 1;
241  const unsigned int ld_mask = info.libertyDropMask();
242  uint8_t ptype_mask = 0;
243  for (int p=GOLD; p<=ROOK; ++p)
244  ptype_mask |= state.hasPieceOnStand(attack, static_cast<Ptype>(p)) << (p-GOLD);
245  for (;
246  result > 1
247  && (ptype_mask & drop_liberty[ld_mask][result-1]);
248  --result)
249  {
250  }
251  return result;
252 }
253 
256 {
257  const Player attack = state.turn();
258  const King8Info info(state.Iking8Info(alt(attack)));
259  return libertyAfterAllDrop(state, attack, info);
260 }
261 
264  Player attack,
265  King8Info info, Square king) const
266 {
267  bool has_pmajor = false;
268  {
269  for (int i = PtypeTraits<BISHOP>::indexMin;
270  i < PtypeTraits<ROOK>::indexLimit; i++)
271  {
272  // move maskを見て8マス調べる方が良いか?
273  const Piece p = state.pieceOf(i);
274  assert(isMajor(p.ptype()));
275  if (! p.isOnBoardByOwner(attack))
276  continue;
277  if (king.squareForBlack(attack).y() > 3 // 1段おまけ
278  && ! isPromoted(p.ptype()))
279  {
280  if (! p.square().canPromote(attack))
281  continue;
282  }
283  if (Neighboring8Direct::hasEffect(state, p.ptypeO(), p.square(),
284  king))
285  {
286  // 本当はそこにbitが立っているかを判定したい.
287  has_pmajor = true;
288  break;
289  }
290  }
291  }
292  int moveCandidate;
293  if(attack==BLACK)
294  moveCandidate = info.moveCandidateMask<BLACK>(state);
295  else
296  moveCandidate = info.moveCandidateMask<WHITE>(state);
297  if (has_pmajor)
298  {
299  int result = pmajor_liberty[info.liberty()][moveCandidate];
300  assert(result);
301  return result;
302  }
303  bool promoted_area = king.squareForBlack(attack).y() < 3;
304  if (! promoted_area)
305  {
306  const Square u = king + Board_Table.getOffset(alt(attack), U);
307  promoted_area = state.hasEffectByPtype<GOLD>(attack, u);
308  }
309  if (promoted_area)
310  {
311  int result = promote_liberty[info.liberty()][moveCandidate];
312  assert(result);
313  return result;
314  }
315  int result = other_move_liberty[info.liberty()][moveCandidate];
316  assert(result);
317  return result;
318 }
319 
322 {
323  const Player attack = state.turn();
324  const Square king = state.kingSquare(alt(attack));
325  const King8Info info(state.Iking8Info(alt(attack)));
326  return libertyAfterAllMove(state, attack, info, king);
327 }
328 
331  Player attack,
332  King8Info info) const
333 {
334  int num_checks;
335  num_checks=info.countMoveCandidate(attack,state);
336  int drop_scale = state.hasPieceOnStand<GOLD>(attack)
337  + state.hasPieceOnStand<SILVER>(attack);
338  if (drop_scale)
339  num_checks += misc::BitOp::countBit(info.dropCandidate()) * drop_scale;
340  return std::max(1, num_checks);
341 }
342 
345  Player attack,
346  King8Info info, Square king) const
347 {
348  int p = libertyAfterAllDrop(state, attack, info);
349  if (p >= 2)
350  {
351  p = std::min(p, libertyAfterAllMove(state, attack, info, king));
352  }
353  return ProofDisproof(p, disproofAfterAllCheck(state, attack, info));
354 }
355 
358 {
359  const Player attack = state.turn();
360  const Square king = state.kingSquare(alt(attack));
361  const King8Info info(state.Iking8Info(alt(attack)));
362  return attackEstimation(state, attack, info, king);
363 }
364 
367 {
368  return attackEstimation(state).proof();
369 }
370 
371 
372 
374 {
375  edge_mask.fill(~(0xfull << 48));
376  for (int x=1; x<=9; ++x) {
377  for (int y=1; y<=9; ++y) {
378  Square king(x,y);
379  for (int d=DIRECTION_MIN; d<=SHORT8_DIRECTION_MAX; ++d) {
380  Square target = king+Board_Table.getOffset(BLACK, Direction(d));
381  if (target.x() <= 1 || target.x() >= 9 || target.y() <=1 || target.y() >=9)
382  edge_mask[BLACK][king.index()] &= ~(0x100ull<<d);
383  target = king+Board_Table.getOffset(WHITE, Direction(d));
384  if (target.x() <= 1 || target.x() >= 9 || target.y() <=1 || target.y() >=9)
385  edge_mask[WHITE][king.index()] &= ~(0x100ull<<d);
386  }
387  }
388  }
389 }
390 
391 
392 /* ------------------------------------------------------------------------- */
393 // ;;; Local Variables:
394 // ;;; mode:c++
395 // ;;; c-basic-offset:2
396 // ;;; End:
397 
398 
osl::checkmate::ProofNumberTable::Liberty::liberty
uint8_t liberty
玉の自由度の予測値.
Definition: proofNumberTable.h:21
osl::PTYPE_PIECE_MIN
@ PTYPE_PIECE_MIN
Definition: basic_type.h:104
osl::Square
Definition: basic_type.h:532
osl::isMajor
bool isMajor(Ptype ptype)
Definition: basic_type.h:185
immediateCheckmate.h
osl::checkmate::King8Info::liberty
unsigned int liberty() const
8-15 bit 目を 0-7bitにshiftして返す
Definition: king8Info.h:54
osl::eval::min
int min(Player p, int v1, int v2)
Definition: evalTraits.h:92
osl::WHITE
@ WHITE
Definition: basic_type.h:10
ptypeTable.h
osl::SetUpRegister
Definition: oslConfig.h:128
osl::Board_Table
const BoardTable Board_Table
Definition: tables.cc:95
osl::checkmate::ProofNumberTable
Definition: proofNumberTable.h:16
proofNumberTable.h
osl::NumEffectState::Iking8Info
uint64_t Iking8Info(Player king) const
Definition: numEffectState.h:78
osl::alt
constexpr Player alt(Player player)
Definition: basic_type.h:13
boardTable.h
osl::PtypeTable::getEffect
const EffectContent getEffect(PtypeO ptypeo, Square from, Square to) const
fromにいるptypeoがtoに利きを持つか?
Definition: ptypeTable.h:112
osl::PLANCE
@ PLANCE
Definition: basic_type.h:88
neighboring8Direct.h
osl::Offset32
Offset32Base< 8, 9 > Offset32
Definition: offset32.h:63
_initializer
static osl::SetUpRegister _initializer([](){ osl::Centering3x3::table.init();})
osl::checkmate::ProofNumberTable::attackEstimation
const ProofDisproof attackEstimation(const NumEffectState &state) const
全て
Definition: proofNumberTable.cc:357
osl::PSILVER
@ PSILVER
Definition: basic_type.h:90
osl::Move
圧縮していない moveの表現 .
Definition: basic_type.h:1052
osl::isShort
constexpr bool isShort(Direction d)
Definition: basic_type.h:342
osl::LONG_DIRECTION_MAX
@ LONG_DIRECTION_MAX
Definition: basic_type.h:333
osl::Piece::ptypeO
PtypeO ptypeO() const
Definition: basic_type.h:824
osl::PtypeTraits
Definition: ptypeTraits.h:12
osl::newPtypeO
PtypeO newPtypeO(Player player, Ptype ptype)
Definition: basic_type.h:211
osl::Ptype
Ptype
駒の種類を4ビットでコード化する
Definition: basic_type.h:84
osl::checkmate::King8Info::countMoveCandidate
unsigned int countMoveCandidate(NumEffectState const &state) const
Definition: king8Info.h:95
osl::DIRECTION_MIN
@ DIRECTION_MIN
Definition: basic_type.h:334
osl::Ptype_Table
const PtypeTable Ptype_Table
Definition: tables.cc:97
osl::BoardTable::getDyForBlack
int getDyForBlack(Direction dir) const
Definition: boardTable.h:43
osl::Piece
駒.
Definition: basic_type.h:788
osl::checkmate::King8Info::dropCandidate
unsigned int dropCandidate() const
0-7 bit 目を返す
Definition: king8Info.h:49
osl::SHORT8_DIRECTION_MAX
@ SHORT8_DIRECTION_MAX
Definition: basic_type.h:321
osl::PtypeTable::getMoveMask
int getMoveMask(Ptype ptype) const
Definition: ptypeTable.h:84
osl::GOLD
@ GOLD
Definition: basic_type.h:94
osl::eval::max
int max(Player p, int v1, int v2)
Definition: evalTraits.h:84
osl::SimpleState::pieceOf
const Piece pieceOf(int num) const
Definition: simpleState.h:76
osl::checkmate::King8Info::libertyCount
unsigned int libertyCount() const
libertyの数
Definition: king8Info.h:82
osl::checkmate::ProofNumberTable::libertyAfterAllDrop
int libertyAfterAllDrop(const NumEffectState &state) const
drop のみ
Definition: proofNumberTable.cc:255
osl::PTYPE_MAX
@ PTYPE_MAX
Definition: basic_type.h:105
osl::KING
@ KING
Definition: basic_type.h:93
osl::checkmate::ProofNumberTable::libertyAfterAllMove
int libertyAfterAllMove(const NumEffectState &state) const
移動 のみ
Definition: proofNumberTable.cc:321
osl::Square::index
unsigned int index() const
Definition: basic_type.h:572
osl::BoardTable::getDxForBlack
int getDxForBlack(Direction dir) const
Definition: boardTable.h:40
osl::PPAWN
@ PPAWN
Definition: basic_type.h:87
osl::PKNIGHT
@ PKNIGHT
Definition: basic_type.h:89
osl::shortToLong
constexpr Direction shortToLong(Direction d)
引数に longDirを与えてはいけない
Definition: basic_type.h:388
osl::Piece::isOnBoardByOwner
bool isOnBoardByOwner() const
piece がプレイヤーPの持ち物でかつボード上にある駒の場合は true.
Definition: basic_type.h:852
osl::checkmate
Definition: king8Info.h:12
oslConfig.h
osl::PBISHOP
@ PBISHOP
Definition: basic_type.h:91
osl::checkmate::ProofNumberTable::Liberty::has_effect
bool has_effect
false の場合は必ず空き王手
Definition: proofNumberTable.h:23
osl::SimpleState::hasPieceOnStand
bool hasPieceOnStand(Player player, Ptype ptype) const
Definition: simpleState.h:191
osl::Square::x
int x() const
将棋としてのX座標を返す.
Definition: basic_type.h:563
osl::checkmate::EdgeTable::init
void init()
Definition: proofNumberTable.cc:373
osl::misc::BitOp::countBit
static int countBit(Integer mask)
Definition: mask.h:160
osl::NumEffectState
利きを持つ局面
Definition: numEffectState.h:34
osl::BoardTable::getOffset
const Offset getOffset(Direction dir) const
Definition: boardTable.h:47
osl::Direction
Direction
Definition: basic_type.h:310
osl::ROOK
@ ROOK
Definition: basic_type.h:100
osl::Square::canPromote
bool canPromote() const
Definition: basic_type.h:659
osl::isPiece
constexpr bool isPiece(Ptype ptype)
ptypeが空白やEDGEでないかのチェック
Definition: basic_type.h:120
osl::SimpleState::kingSquare
Square kingSquare() const
Definition: simpleState.h:94
osl::checkmate::Proof_Number_Table
ProofNumberTable Proof_Number_Table
Definition: proofNumberTable.cc:10
osl::Square::y
int y() const
将棋としてのY座標を返す.
Definition: basic_type.h:567
osl::checkmate::ProofNumberTable::libertyAfterAllCheck
int libertyAfterAllCheck(const NumEffectState &state) const
全て
Definition: proofNumberTable.cc:366
osl::isLong
constexpr bool isLong(Direction d)
Definition: basic_type.h:350
osl::isPromoted
bool isPromoted(Ptype ptype)
ptypeがpromote後の型かどうかのチェック
Definition: basic_type.h:137
osl::Piece::square
const Square square() const
Definition: basic_type.h:832
osl::Piece::ptype
Ptype ptype() const
Definition: basic_type.h:821
osl::checkmate::ProofNumberTable::disproofAfterAllCheck
int disproofAfterAllCheck(const NumEffectState &, Player, King8Info) const
Definition: proofNumberTable.cc:330
osl::checkmate::Edge_Table
EdgeTable Edge_Table
Definition: proofNumberTable.cc:11
osl::BLACK
@ BLACK
Definition: basic_type.h:9
osl::PTYPE_BASIC_MIN
@ PTYPE_BASIC_MIN
Definition: basic_type.h:103
osl::checkmate::ProofNumberTable::init
void init()
Definition: proofNumberTable.cc:84
ProofNumberTable
Definition: proofNumberTable.cc:14
osl::checkmate::ProofDisproof
証明数(proof number)と反証数(disproof number).
Definition: proofDisproof.h:17
osl::checkmate::King8Info::moveCandidateMask
unsigned int moveCandidateMask(NumEffectState const &state) const
Definition: king8Info.h:114
osl::SILVER
@ SILVER
Definition: basic_type.h:98
osl::checkmate::King8Info::libertyDropMask
unsigned int libertyDropMask() const
0-15bit
Definition: king8Info.h:59
osl::PROOK
@ PROOK
Definition: basic_type.h:92
osl::SimpleState::turn
Player turn() const
Definition: simpleState.h:220
osl::effect_util::Neighboring8Direct::hasEffect
static bool hasEffect(const NumEffectState &state, PtypeO ptypeo, Square from, Square target)
ptypeo の駒がfromからtargetの8近傍に直接の利きを持つか
Definition: neighboring8Direct.h:108
osl::Player
Player
Definition: basic_type.h:8
osl::NumEffectState::hasEffectByPtype
bool hasEffectByPtype(Player attack, Square target) const
target に ptype の利きがあるか? 成不成を区別しない
Definition: numEffectState.h:355
osl::LONG_DIRECTION_MIN
@ LONG_DIRECTION_MIN
Definition: basic_type.h:324
osl::checkmate::ProofNumberTable::countLiberty
const Liberty countLiberty(Ptype ptype, Direction d, unsigned int liberty_mask) const
dir 方向からの王手をかけた時のlibertyの予想
Definition: proofNumberTable.h:50
osl::checkmate::ProofNumberTable::Liberty
Definition: proofNumberTable.h:19
osl::U
@ U
Definition: basic_type.h:314
osl::Square::squareForBlack
const Square squareForBlack(Player player) const
Definition: basic_type.h:598
osl::checkmate::King8Info
敵玉の8近傍の状態を表す.
Definition: king8Info.h:29
osl::checkmate::EdgeTable
Definition: proofNumberTable.h:202
osl::dirToMask
constexpr int dirToMask(Direction dir)
Definition: basic_type.h:393
osl::Move::player
Player player() const
Definition: basic_type.h:1195
osl
Definition: additionalEffect.h:6