proofNumberTable.cc
Go to the documentation of this file.
/* proofNumberTable.cc
*/
#include "osl/checkmate/proofNumberTable.h"
#include "osl/checkmate/immediateCheckmate.h"
#include "osl/effect_util/neighboring8Direct.h"
#include "osl/bits/boardTable.h"
#include "osl/bits/ptypeTable.h"
#include "osl/oslConfig.h"
osl::checkmate::ProofNumberTable osl::checkmate::Proof_Number_Table;
osl::checkmate::EdgeTable osl::checkmate::Edge_Table;
namespace {
namespace ProofNumberTable {
osl::SetUpRegister _initializer([](){
osl::checkmate::Proof_Number_Table.init();
osl::checkmate::Edge_Table.init();
});
}
}
namespace osl
{
namespace
{
using namespace osl::checkmate;
const checkmate::ProofNumberTable::Liberty
effectiveCheckShort(Ptype ptype,Direction dir,unsigned int mask)
{
assert(isShort(dir));
// 王は8近傍に移動できない
if (ptype==KING)
return ProofNumberTable::Liberty(0,false);
// ptypeがdir方向に利きを持たない場合も空王手の場合があるので作成
const bool has_effect
= (Ptype_Table.getMoveMask(ptype)
& (dirToMask(dir) | dirToMask(shortToLong(dir))));
int dx=Board_Table.getDxForBlack(dir);
int dy=Board_Table.getDyForBlack(dir);
int count = 0;
for (int l=0;l<8;l++) {
if ((mask&(1<<l))==0)
continue;
Direction dir1=static_cast<Direction>(l);
int dx1=Board_Table.getDxForBlack(dir1);
int dy1=Board_Table.getDyForBlack(dir1);
Offset32 o32(dx-dx1,dy-dy1);
if ((dx != dx1 || dy != dy1)
&& !Ptype_Table.getEffect(newPtypeO(BLACK,ptype),o32).hasEffect())
++count;
}
return ProofNumberTable::Liberty(std::max(count,1), has_effect);
}
const checkmate::ProofNumberTable::Liberty
effectiveCheckLong(Ptype ptype,Direction dir,unsigned int mask)
{
assert(isLong(dir));
// ptypeがdir方向に利きを持たなくても2マス離れた空王手で8近傍に
// 利きが増える場合があるので作成
const bool has_effect
= (Ptype_Table.getMoveMask(ptype) & dirToMask(dir));
int dx=Board_Table.getDxForBlack(dir)*2; // 1マス遠くから
int dy=Board_Table.getDyForBlack(dir)*2;
int count = 0;
for (int l=0;l<8;l++) {
if ((mask&(1<<l))==0)
continue;
Direction dir1=static_cast<Direction>(l);
int dx1=Board_Table.getDxForBlack(dir1);
int dy1=Board_Table.getDyForBlack(dir1);
Offset32 o32(dx-dx1,dy-dy1);
if (!Ptype_Table.getEffect(newPtypeO(BLACK,ptype),o32).hasEffect())
++count;
}
return ProofNumberTable::Liberty(std::max(count,1), has_effect);
}
}
}
void osl::checkmate::
ProofNumberTable::init()
{
// liberties
for (int i=0; i<0x100; i++) {
for (int k=PTYPE_PIECE_MIN; k<=PTYPE_MAX; k++) {
const Ptype ptype=static_cast<Ptype>(k);
assert(isPiece(ptype));
for (int j=0; j<8; j++) {
Direction dir=static_cast<Direction>(j);
const Liberty e = effectiveCheckShort(ptype,dir,i);
liberties[i][k][j] = e;
}
int longs = 0;
for (int j=LONG_DIRECTION_MIN; j<=LONG_DIRECTION_MAX; ++j,++longs) {
Direction dir=static_cast<Direction>(j);
const Liberty e = effectiveCheckLong(ptype,dir,i);
liberties[i][k][j] = e;
}
assert(longs == 8);
}
}
// drop_liberty
drop_liberty.fill(0);
for(int i=0;i<0x10000;i++){
const unsigned int liberty = (i>>8)&0xff;
const int liberty_count = misc::BitOp::countBit(liberty);
if (liberty_count <= 2)
continue; // low enough
for (int k=PTYPE_BASIC_MIN;k<=PTYPE_MAX;k++) {
int minimum_liberty = liberty_count;
Ptype ptype=static_cast<Ptype>(k);
if (ptype == KING)
continue;
for (int j=0;j<8;j++) {
// 有効王手でない
if ((i&(0x1<<j))==0)
continue;
if ((i&(0x100<<j))!=0)
continue;
const Direction dir=static_cast<Direction>(j);
// ptypeがdir方向に利きを持つか
const bool has_effect
= (Ptype_Table.getMoveMask(ptype)
& (dirToMask(dir) | dirToMask(shortToLong(dir))));
if (! has_effect)
continue;
const int e = liberties[liberty][k][j].liberty;
assert(e);
minimum_liberty = std::min(minimum_liberty, e);
}
for (int l=minimum_liberty; l<liberty_count; ++l)
{
drop_liberty[i][l] |= (1<<(ptype-GOLD));
}
}
}
// pmajor_liberty
pmajor_liberty.fill(8);
for (int l=0; l<0x100; l++) { // liberty
for (int m=0; m<0x100; m++) { // move_mask
if (l & m)
continue;
int min_liberty = std::max(2,misc::BitOp::countBit(l))-1;
if (min_liberty > 1)
{
for (int j=0; j<8; j++) {
if ((m&(0x1<<j))==0)
continue;
const int pr = liberties[l][PROOK][j].liberty;
const int pb = liberties[l][PBISHOP][j].liberty;
min_liberty = std::min(min_liberty, std::min(pr,pb));
assert(min_liberty);
}
}
pmajor_liberty[l][m] = min_liberty;
}
}
// promote_liberty
promote_liberty.fill(8);
for (int l=0; l<0x100; l++) { // liberty
for (int m=0; m<0x100; m++) { // move_mask
if (l & m)
continue;
int min_liberty = std::max(2,misc::BitOp::countBit(l))-1;
if (min_liberty > 1)
{
for (int j=0; j<8; j++) {
if ((m&(0x1<<j))==0)
continue;
for (int k=PTYPE_BASIC_MIN;k<=PTYPE_MAX;k++) {
Ptype ptype=static_cast<Ptype>(k);
if (ptype == KING || ptype == PROOK || ptype == PBISHOP)
continue;
Liberty e = liberties[l][k][j];
if (! e.has_effect)
continue;
assert(e.liberty);
min_liberty = std::min(min_liberty, (int)e.liberty);
assert(min_liberty);
}
}
}
promote_liberty[l][m] = min_liberty;
}
}
// other_move_liberty
other_move_liberty.fill(8);
for (int l=0; l<0x100; l++) { // liberty
for (int m=0; m<0x100; m++) { // move_mask
if (l & m)
continue;
int min_liberty = std::max(2,misc::BitOp::countBit(l))-1;
if (min_liberty > 1)
{
for (int j=0; j<8; j++) {
if ((m&(0x1<<j))==0)
continue;
for (int k=PTYPE_BASIC_MIN;k<=PTYPE_MAX;k++) {
Ptype ptype=static_cast<Ptype>(k);
if (ptype == KING || ptype == PROOK || ptype == PBISHOP)
continue;
if (j == U
&& (ptype == GOLD || ptype == PPAWN || ptype == PLANCE
|| ptype == PKNIGHT || ptype == PSILVER))
continue;
Liberty e = liberties[l][k][j];
if (! e.has_effect)
continue;
assert(e.liberty);
min_liberty = std::min(min_liberty, (int)e.liberty);
assert(min_liberty);
}
}
}
other_move_liberty[l][m] = min_liberty;
}
}
}
int osl::checkmate::
ProofNumberTable::countLiberty(const NumEffectState& state, Move move) const
{
const Player attack = move.player();
const Square king = state.kingSquare(alt(attack));
const King8Info info(state.Iking8Info(alt(attack)));
return countLiberty(state, info.libertyCount(), move, king, info);
}
int osl::checkmate::
ProofNumberTable::libertyAfterAllDrop(const NumEffectState& state, Player attack,
King8Info info) const
{
assert(state.turn() == attack);
int result = info.libertyCount()-1;
if (result < 2)
return 1;
const unsigned int ld_mask = info.libertyDropMask();
uint8_t ptype_mask = 0;
for (int p=GOLD; p<=ROOK; ++p)
ptype_mask |= state.hasPieceOnStand(attack, static_cast<Ptype>(p)) << (p-GOLD);
for (;
result > 1
&& (ptype_mask & drop_liberty[ld_mask][result-1]);
--result)
{
}
return result;
}
int osl::checkmate::
ProofNumberTable::libertyAfterAllDrop(const NumEffectState& state) const
{
const Player attack = state.turn();
const King8Info info(state.Iking8Info(alt(attack)));
return libertyAfterAllDrop(state, attack, info);
}
int osl::checkmate::
ProofNumberTable::libertyAfterAllMove(const NumEffectState& state,
Player attack,
King8Info info, Square king) const
{
bool has_pmajor = false;
{
for (int i = PtypeTraits<BISHOP>::indexMin;
i < PtypeTraits<ROOK>::indexLimit; i++)
{
// move maskを見て8マス調べる方が良いか?
const Piece p = state.pieceOf(i);
assert(isMajor(p.ptype()));
if (! p.isOnBoardByOwner(attack))
continue;
if (king.squareForBlack(attack).y() > 3 // 1段おまけ
&& ! isPromoted(p.ptype()))
{
if (! p.square().canPromote(attack))
continue;
}
if (Neighboring8Direct::hasEffect(state, p.ptypeO(), p.square(),
king))
{
// 本当はそこにbitが立っているかを判定したい．
has_pmajor = true;
break;
}
}
}
int moveCandidate;
if(attack==BLACK)
moveCandidate = info.moveCandidateMask<BLACK>(state);
else
moveCandidate = info.moveCandidateMask<WHITE>(state);
if (has_pmajor)
{
int result = pmajor_liberty[info.liberty()][moveCandidate];
assert(result);
return result;
}
bool promoted_area = king.squareForBlack(attack).y() < 3;
if (! promoted_area)
{
const Square u = king + Board_Table.getOffset(alt(attack), U);
promoted_area = state.hasEffectByPtype<GOLD>(attack, u);
}
if (promoted_area)
{
int result = promote_liberty[info.liberty()][moveCandidate];
assert(result);
return result;
}
int result = other_move_liberty[info.liberty()][moveCandidate];
assert(result);
return result;
}
int osl::checkmate::
ProofNumberTable::libertyAfterAllMove(const NumEffectState& state) const
{
const Player attack = state.turn();
const Square king = state.kingSquare(alt(attack));
const King8Info info(state.Iking8Info(alt(attack)));
return libertyAfterAllMove(state, attack, info, king);
}
int osl::checkmate::
ProofNumberTable::disproofAfterAllCheck(const NumEffectState& state,
Player attack,
King8Info info) const
{
int num_checks;
num_checks=info.countMoveCandidate(attack,state);
int drop_scale = state.hasPieceOnStand<GOLD>(attack)
+ state.hasPieceOnStand<SILVER>(attack);
if (drop_scale)
num_checks += misc::BitOp::countBit(info.dropCandidate()) * drop_scale;
return std::max(1, num_checks);
}
const osl::checkmate::ProofDisproof osl::checkmate::
ProofNumberTable::attackEstimation(const NumEffectState& state,
Player attack,
King8Info info, Square king) const
{
int p = libertyAfterAllDrop(state, attack, info);
if (p >= 2)
{
p = std::min(p, libertyAfterAllMove(state, attack, info, king));
}
return ProofDisproof(p, disproofAfterAllCheck(state, attack, info));
}
const osl::checkmate::ProofDisproof osl::checkmate::
ProofNumberTable::attackEstimation(const NumEffectState& state) const
{
const Player attack = state.turn();
const Square king = state.kingSquare(alt(attack));
const King8Info info(state.Iking8Info(alt(attack)));
return attackEstimation(state, attack, info, king);
}
int osl::checkmate::
ProofNumberTable::libertyAfterAllCheck(const NumEffectState& state) const
{
return attackEstimation(state).proof();
}
␌
void osl::checkmate::EdgeTable::init()
{
edge_mask.fill(~(0xfull << 48));
for (int x=1; x<=9; ++x) {
for (int y=1; y<=9; ++y) {
Square king(x,y);
for (int d=DIRECTION_MIN; d<=SHORT8_DIRECTION_MAX; ++d) {
Square target = king+Board_Table.getOffset(BLACK, Direction(d));
if (target.x() <= 1 || target.x() >= 9 || target.y() <=1 || target.y() >=9)
edge_mask[BLACK][king.index()] &= ~(0x100ull<<d);
target = king+Board_Table.getOffset(WHITE, Direction(d));
if (target.x() <= 1 || target.x() >= 9 || target.y() <=1 || target.y() >=9)
edge_mask[WHITE][king.index()] &= ~(0x100ull<<d);
}
}
}
}
/* ------------------------------------------------------------------------- */
// ;;; Local Variables:
// ;;; mode:c++
// ;;; c-basic-offset:2
// ;;; End:
boardTable.h
_initializer
static osl::SetUpRegister _initializer([](){ osl::Centering3x3::table.init();})
osl::Move
圧縮していない moveの表現 .
Definition basic_type.h:1052
osl::Move::player
Player player() const
Definition basic_type.h:1195
osl::Neighboring8Direct::hasEffect
static bool hasEffect(const NumEffectState &state, PtypeO ptypeo, Square from, Square target)
ptypeo の駒がfromからtargetの8近傍に直接の利きを持つか
Definition neighboring8Direct.h:108
osl::NumEffectState
利きを持つ局面
Definition numEffectState.h:34
osl::NumEffectState::Iking8Info
uint64_t Iking8Info(Player king) const
Definition numEffectState.h:78
osl::NumEffectState::hasEffectByPtype
bool hasEffectByPtype(Player attack, Square target) const
target に ptype の利きがあるか?
Definition numEffectState.h:355
osl::Piece
駒.
Definition basic_type.h:788
osl::Piece::ptypeO
PtypeO ptypeO() const
Definition basic_type.h:824
osl::Piece::ptype
Ptype ptype() const
Definition basic_type.h:821
osl::Piece::square
const Square square() const
Definition basic_type.h:832
osl::Piece::isOnBoardByOwner
bool isOnBoardByOwner() const
piece がプレイヤーPの持ち物でかつボード上にある駒の場合は true.
Definition basic_type.h:852
osl::SimpleState::hasPieceOnStand
bool hasPieceOnStand(Player player, Ptype ptype) const
Definition simpleState.h:191
osl::SimpleState::turn
Player turn() const
Definition simpleState.h:220
osl::SimpleState::pieceOf
const Piece pieceOf(int num) const
Definition simpleState.h:76
osl::SimpleState::kingSquare
Square kingSquare() const
Definition simpleState.h:94
osl::Square
Definition basic_type.h:532
osl::Square::index
unsigned int index() const
Definition basic_type.h:572
osl::Square::y
int y() const
将棋としてのY座標を返す.
Definition basic_type.h:567
osl::Square::canPromote
bool canPromote() const
Definition basic_type.h:659
osl::Square::squareForBlack
const Square squareForBlack(Player player) const
Definition basic_type.h:598
osl::Square::x
int x() const
将棋としてのX座標を返す.
Definition basic_type.h:563
osl::checkmate::EdgeTable
Definition proofNumberTable.h:202
osl::checkmate::EdgeTable::init
void init()
Definition proofNumberTable.cc:373
osl::checkmate::EdgeTable::edge_mask
CArray2d< uint64_t, 2, Square::SIZE > edge_mask
Definition proofNumberTable.h:203
osl::checkmate::King8Info
敵玉の8近傍の状態を表す.
Definition king8Info.h:29
osl::checkmate::King8Info::liberty
unsigned int liberty() const
8-15 bit 目を 0-7bitにshiftして返す
Definition king8Info.h:54
osl::checkmate::King8Info::countMoveCandidate
unsigned int countMoveCandidate(NumEffectState const &state) const
Definition king8Info.h:95
osl::checkmate::King8Info::moveCandidateMask
unsigned int moveCandidateMask(NumEffectState const &state) const
Definition king8Info.h:114
osl::checkmate::King8Info::libertyDropMask
unsigned int libertyDropMask() const
0-15bit
Definition king8Info.h:59
osl::checkmate::King8Info::dropCandidate
unsigned int dropCandidate() const
0-7 bit 目を返す
Definition king8Info.h:49
osl::checkmate::King8Info::libertyCount
unsigned int libertyCount() const
libertyの数
Definition king8Info.h:82
osl::checkmate::ProofDisproof
証明数(proof number)と反証数(disproof number).
Definition proofDisproof.h:17
osl::checkmate::ProofNumberTable
Definition proofNumberTable.h:16
osl::checkmate::ProofNumberTable::libertyAfterAllDrop
int libertyAfterAllDrop(const NumEffectState &state) const
drop のみ
Definition proofNumberTable.cc:255
osl::checkmate::ProofNumberTable::attackEstimation
const ProofDisproof attackEstimation(const NumEffectState &state) const
全て
Definition proofNumberTable.cc:357
osl::checkmate::ProofNumberTable::pmajor_liberty
CArray2d< uint8_t, 0x100u, 0x100u > pmajor_liberty
龍や馬で王手をかけられる時のliberty: [liberty][move_mask]
Definition proofNumberTable.h:37
osl::checkmate::ProofNumberTable::init
void init()
Definition proofNumberTable.cc:84
osl::checkmate::ProofNumberTable::disproofAfterAllCheck
int disproofAfterAllCheck(const NumEffectState &, Player, King8Info) const
Definition proofNumberTable.cc:330
osl::checkmate::ProofNumberTable::drop_liberty
CArray2d< uint8_t, 0x10000u, 8 > drop_liberty
全ての有効drop -> 最小liberty.
Definition proofNumberTable.h:35
osl::checkmate::ProofNumberTable::promote_liberty
CArray2d< uint8_t, 0x100u, 0x100u > promote_liberty
王が1,2段目にいる時の移動王手によるliberty: [liberty][move_mask].
Definition proofNumberTable.h:41
osl::checkmate::ProofNumberTable::libertyAfterAllMove
int libertyAfterAllMove(const NumEffectState &state) const
移動 のみ
Definition proofNumberTable.cc:321
osl::checkmate::ProofNumberTable::libertyAfterAllCheck
int libertyAfterAllCheck(const NumEffectState &state) const
全て
Definition proofNumberTable.cc:366
osl::checkmate::ProofNumberTable::liberties
CArray2d< CArray< Liberty, DIRECTION_SIZE >, 0x100u, PTYPE_SIZE > liberties
一つの王手 -> Liberty: long なdirection は1マスあけた王手を意味する
Definition proofNumberTable.h:31
osl::checkmate::ProofNumberTable::other_move_liberty
CArray2d< uint8_t, 0x100u, 0x100u > other_move_liberty
それ以外の移動liberty: [liberty][move_mask]
Definition proofNumberTable.h:43
osl::checkmate::ProofNumberTable::countLiberty
const Liberty countLiberty(Ptype ptype, Direction d, unsigned int liberty_mask) const
dir 方向からの王手をかけた時のlibertyの予想
Definition proofNumberTable.h:50
immediateCheckmate.h
ProofNumberTable
Definition proofNumberTable.cc:14
osl::checkmate::Edge_Table
EdgeTable Edge_Table
Definition proofNumberTable.cc:11
osl::checkmate::Proof_Number_Table
ProofNumberTable Proof_Number_Table
Definition proofNumberTable.cc:10
osl
Definition additionalEffect.h:6
osl::Ptype
Ptype
駒の種類を4ビットでコード化する
Definition basic_type.h:84
osl::PTYPE_PIECE_MIN
@ PTYPE_PIECE_MIN
Definition basic_type.h:104
osl::PTYPE_MAX
@ PTYPE_MAX
Definition basic_type.h:105
osl::ROOK
@ ROOK
Definition basic_type.h:100
osl::PPAWN
@ PPAWN
Definition basic_type.h:87
osl::PROOK
@ PROOK
Definition basic_type.h:92
osl::KING
@ KING
Definition basic_type.h:93
osl::SILVER
@ SILVER
Definition basic_type.h:98
osl::PTYPE_BASIC_MIN
@ PTYPE_BASIC_MIN
Definition basic_type.h:103
osl::PKNIGHT
@ PKNIGHT
Definition basic_type.h:89
osl::GOLD
@ GOLD
Definition basic_type.h:94
osl::PLANCE
@ PLANCE
Definition basic_type.h:88
osl::PBISHOP
@ PBISHOP
Definition basic_type.h:91
osl::PSILVER
@ PSILVER
Definition basic_type.h:90
osl::Ptype_Table
const PtypeTable Ptype_Table
Definition tables.cc:97
osl::dirToMask
constexpr int dirToMask(Direction dir)
Definition basic_type.h:393
osl::Board_Table
const BoardTable Board_Table
Definition tables.cc:95
osl::Direction
Direction
Definition basic_type.h:310
osl::LONG_DIRECTION_MAX
@ LONG_DIRECTION_MAX
Definition basic_type.h:333
osl::LONG_DIRECTION_MIN
@ LONG_DIRECTION_MIN
Definition basic_type.h:324
osl::DIRECTION_MIN
@ DIRECTION_MIN
Definition basic_type.h:334
osl::SHORT8_DIRECTION_MAX
@ SHORT8_DIRECTION_MAX
Definition basic_type.h:321
osl::U
@ U
Definition basic_type.h:314
osl::isPromoted
bool isPromoted(Ptype ptype)
ptypeがpromote後の型かどうかのチェック
Definition basic_type.h:137
osl::isShort
constexpr bool isShort(Direction d)
Definition basic_type.h:342
osl::Offset32
Offset32Base< 8, 9 > Offset32
Definition offset32.h:63
osl::Player
Player
Definition basic_type.h:8
osl::WHITE
@ WHITE
Definition basic_type.h:10
osl::BLACK
@ BLACK
Definition basic_type.h:9
osl::isPiece
constexpr bool isPiece(Ptype ptype)
ptypeが空白やEDGEでないかのチェック
Definition basic_type.h:120
osl::isMajor
bool isMajor(Ptype ptype)
Definition basic_type.h:185
osl::isLong
constexpr bool isLong(Direction d)
Definition basic_type.h:350
osl::shortToLong
constexpr Direction shortToLong(Direction d)
引数に longDirを与えてはいけない
Definition basic_type.h:388
osl::alt
constexpr Player alt(Player player)
Definition basic_type.h:13
osl::newPtypeO
PtypeO newPtypeO(Player player, Ptype ptype)
Definition basic_type.h:211
neighboring8Direct.h
oslConfig.h
proofNumberTable.h
ptypeTable.h
osl::PtypeTraits
Definition ptypeTraits.h:12
osl::SetUpRegister
Definition oslConfig.h:128
osl::checkmate::ProofNumberTable::Liberty
Definition proofNumberTable.h:19
osl::checkmate::ProofNumberTable::Liberty::liberty
uint8_t liberty
玉の自由度の予測値.
Definition proofNumberTable.h:21
osl::checkmate::ProofNumberTable::Liberty::has_effect
bool has_effect
false の場合は必ず空き王手
Definition proofNumberTable.h:23
osl::misc::BitOp::countBit
static int countBit(Integer mask)
Definition mask.h:160