Zobrist Hash (Hash/zobrist_hash_base.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-10-01 17:50:29+09:00
• Include: #include "Hash/zobrist_hash_base.hpp"

Zobrist Hash

Zobrist Hashは、ある数値列の各要素にランダムな値を割り当てることで、数値列の連続部分集合に対する状態の一致判定を効率的に行うための手法です。
これにより、数値列の部分集合が同一であるか、特定の条件を満たしているかを高速に判定できます。

ハッシュ値の取り方に関しては、以下の記事を参考にしています。
https://drken1215.hatenablog.com/entry/2022/05/12/105000

ZobristHashBase

ZobristHashBaseは、Zobrist Hashに関する基本的な機能を提供する抽象クラスです。
派生クラスで共通して使用されるハッシュ計算や、インターフェースを定義しています。

インターフェース

build

virtual void build(const vector<long long>& v)

この関数はハッシュ列を生成する関数です。
引数 v はハッシュ対象となる整数の配列です。

get_range_hash

virtual unsigned long long get_range_hash(int l, int r) 

この関数は、コンストラクタで入力された配列 v のうち、指定された範囲 $[l, r)$ の要素に対して累積ハッシュを計算して返します。

派生クラス

• ParityHash
  指定範囲 $[l, r)$ に含まれる 数値の出現回数の偶奇 のハッシュを計算します。
• CountHash
  指定範囲 $[l, r)$ に含まれる 数値の多重集合 のハッシュを計算します。
• TypeHash
  範囲 $[{\color{red} 0}, r)$ に含まれる 数値の集合 のハッシュを計算します。
• CubicHash
  指定範囲 $[l, r)$ に含まれる 数値の総積を因数ごとに 3 で割った余りに置き換えた値 のハッシュを計算します。

Required by

• Zobrist Hash (多重集合) (Hash/zobrist_count_hash.hpp)
• Zobrist Hash (立方数判定) (Hash/zobrist_cubic_hash.hpp)
• Zobrist Hash (偶奇判定) (Hash/zobrist_parity_hash.hpp)
• Zobrist Hash (集合) (Hash/zobrist_type_hash.hpp)

Verified with

• test/Hash/zobrist_hash/abc238-g.cpp
• test/Hash/zobrist_hash/abc250-e.cpp
• test/Hash/zobrist_hash/abc367-f.cpp

Code

#include <bits/stdc++.h>
using namespace std;

class ZobristHashBase
{
private:
    static unsigned long long splitmix64(uint64_t x)
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    static unsigned long long generate_random_value(unsigned long long x)
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }

protected:
    static unsigned long long hash(long long x)
    {
        static unordered_map<long long, unsigned long long> cache;
        if (cache.contains(x))
        {
            return cache[x];
        }

        cache[x] = generate_random_value(x);
        return cache[x];
    };

    virtual void build(const vector<long long> &v) = 0;
    ZobristHashBase() {};

public:
    vector<unsigned long long> hash_vector;
    virtual unsigned long long get_range_hash(int l, int r) const = 0;
    virtual ~ZobristHashBase() = default;
};

#line 1 "Hash/zobrist_hash_base.hpp"
#include <bits/stdc++.h>
using namespace std;

class ZobristHashBase
{
private:
    static unsigned long long splitmix64(uint64_t x)
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    static unsigned long long generate_random_value(unsigned long long x)
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }

protected:
    static unsigned long long hash(long long x)
    {
        static unordered_map<long long, unsigned long long> cache;
        if (cache.contains(x))
        {
            return cache[x];
        }

        cache[x] = generate_random_value(x);
        return cache[x];
    };

    virtual void build(const vector<long long> &v) = 0;
    ZobristHashBase() {};

public:
    vector<unsigned long long> hash_vector;
    virtual unsigned long long get_range_hash(int l, int r) const = 0;
    virtual ~ZobristHashBase() = default;
};

Back to top page