5×5将棋 MagicBitboard マジックナンバーの考え方求め方

Question

###前提・実現したいこと
55将棋においてMagicBitboardの実装をしようとしているのですが、マジックナンバーの考え方や求め方で詰まっております。

変数型はint32bit（マスが２５マスな為）
bitboardは以下のようであるとします。

//      0|   1|   2|   3|   4|
//      5|   6|   7|   8|   9|
//   10| 11| 12| 13| 14|
//   15| 16| 17| 18| 19|
//   20| 21| 22| 23| 24|

例えばですが、角が以下の位置にいる場合、

// ーーーーー
// ーーーーー
// ーー角ーー
// ーーーーー
// ーーーーー

利きは以下のようになりますが、

// ◯ーーー◯
// ー◯ー◯ー
// ーーーーー
// ー◯ー◯ー
// ◯ーーー◯

欲しいそれぞれの◯をマジックナンバーをかけることで一つに集めて以下のようにしたいです。

//上位ビットに集める
// ーーーーー
// ーーーーー
// ーーーーー
// ーー◯◯◯
// ◯◯◯◯◯

仮にも乱数を使って求めることはできました。しかし、どれがどこのbitか分からない上に、角の利きを一つ消してどこがどのbitか確かめようと同じマジックナンバーをかけると集めたbitが散らばってしまいます。考え方がまず間違っているのかも知れません。どなたかご教授いただけませんか？

#include <string>
#include <iostream>
#include <random>
#include <bitset>
using namespace std;

int magicNumber(){
    random_device rnd;
    mt19937 mt(rnd());
    return mt();
}

bool isSatisfy(int num){
    int partbit = num >> 23;
    cout << static_cast<bitset<32>>(num) << " " << static_cast<bitset<32>>(0b11111111) << endl;
    if(partbit == 0b11111111)return true;
    else return false;
}

int main(){
    while(true) {
        int num = 0b11111111;
        int magicNum = magicNumber();
        if(isSatisfy(num*magicNum)){
            cout << magicNum << endl;
            cout << static_cast<bitset<32>>(magicNum) << endl;
            break;
        }
    }
    return 0;
}

Answer 1

MagicNumberの求め方についてですが、isSatisfied関数で、角の利きの範囲の駒の有無の全パターンで正しくビットが集められるかチェックしないといけないのではないでしょうか。

例えば、ここに角がいる場合、

// ーーーーー
// ーーーーー
// ーー角ーー
// ーーーーー
// ーーーーー

このパターンだけ計算が合うMagicNumberでは駄目で、

// ◯ーーー◯
// ー◯ー◯ー
// ーーーーー
// ー◯ー◯ー
// ◯ーーー◯

左上の駒がない

// ーーーー◯
// ー◯ー◯ー
// ーーーーー
// ー◯ー◯ー
// ◯ーーー◯

色々ない

// ◯ーーーー
// ーーー◯ー
// ーーーーー
// ー◯ーーー
// ◯ーーー◯

全部ない

// ーーーーー
// ーーーーー
// ーーーーー
// ーーーーー
// ーーーーー

...など全ての場合をチェックすれば、求められると思います（わかりづらくてすいません）。

Comments

[_Victorique__]

遅くなりましたがそのようですね。マジックナンバーを見つけることができました。ありがとうございました。