不偏ゲーム
(game/impartial-game.hpp)
Depends on
Verified with
Code
#pragma once
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <functional>
#include <map>
#include <type_traits>
#include <utility>
#include <vector>
using namespace std;
#include "../internal/internal-function.hpp"
/**
* ゲームの遷移が DAG で表せる不偏ゲームの solver
*
* Board：盤面の型
* Move は着手の型 or void
* Game は
*
* - splittable = true の場合は vector<Board> (ゲームの分割に対応)
* - splittable = falseの場合は Board
*
* State は次
*
* - Move が void である場合, Game
* - Move が void でない場合, pair<Game, Move>
*
* States は vector<State>
*
* F は Board を引数, States を返り値に取る callable。つまり
*
* - デフォルトの場合 : vector<Board>(Board)
* - splittable の場合 : vector<vector<Board>>(Board)
* - Move != void の場合は返り値の value_type が pair(*, move) になる
*
* 雑にゲームの勝敗を知りたいときはデフォルトでよい
* 最善手の情報が欲しいときは Move の引数を変えて頑張る
*/
template <typename Board, typename Move = void, bool splittable = false>
struct ImpartialGameSolver {
using Boards = vector<Board>;
using Game = conditional_t<splittable, vector<Board>, Board>;
using State = conditional_t<is_void_v<Move>, Game, pair<Game, Move>>;
using States = vector<State>;
using Nimber = long long;
using F = nyaan_internal::inplace_function<States(Board), 64>;
map<Board, Nimber> mp;
F f;
ImpartialGameSolver() = default;
ImpartialGameSolver(const F& _f) : f(_f) {}
template <typename Func,
typename = enable_if_t<is_invocable_r_v<States, Func&, Board>>>
ImpartialGameSolver(Func&& _f) : f(std::forward<Func>(_f)) {}
void set_func(const F& _f) { f = _f; }
template <typename Func>
auto set_func(Func&& _f)
-> enable_if_t<is_invocable_r_v<States, Func&, Board>, void> {
f = std::forward<Func>(_f);
}
template <typename T>
Nimber get(const T& t) {
if constexpr (is_same_v<T, Board>) {
if (mp.count(t)) return mp[t];
return mp[t] = _get(t);
} else if constexpr (is_same_v<T, Boards>) {
Nimber n = 0;
for (const Board& s : t) n ^= get(s);
return n;
} else {
static_assert(is_same_v<T, pair<Game, Move>>);
return get(t.first);
}
}
// 負け局面で呼ぶと RE する
template <typename T>
conditional_t<is_same_v<T, Board>, Move, pair<int, Move>> get_best_move(
const T& t) {
static_assert(is_void_v<Move> == false);
Nimber n = get(t);
assert(n != 0 and "No Best Move.");
if constexpr (is_same_v<T, Board>) {
auto res = change_x(t, n);
if (res.first) return res.second;
} else {
static_assert(is_same_v<T, Boards>);
for (int i = 0; i < (int)t.size(); i++) {
auto res = change_x(t[i], n);
if (res.first) return {i, res.second};
}
}
assert(false and "Error in get_best_move().");
exit(1);
}
private:
Nimber _get(const Board& b) {
States gs = std::invoke(f, b);
if (gs.empty()) return {};
vector<Nimber> ns;
for (State& st : gs) ns.push_back(get(st));
sort(begin(ns), end(ns));
ns.erase(unique(begin(ns), end(ns)), end(ns));
for (int i = 0; i < (int)ns.size(); i++) {
if (ns[i] != i) return i;
}
return ns.size();
}
// nimber が x 変わるような着手を返す
pair<bool, Move> change_x(const Board& b, Nimber x) {
assert(is_void_v<Move> == false);
Nimber n = get(b);
for (auto& st : std::invoke(f, b)) {
if (get(st) == (x ^ n)) return {true, st.second};
}
return {false, Move{}};
}
};
/**
* @brief 不偏ゲーム
*/
#line 2 "game/impartial-game.hpp"
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <functional>
#include <map>
#include <type_traits>
#include <utility>
#include <vector>
using namespace std;
#line 2 "internal/internal-function.hpp"
#include <cstddef>
#line 5 "internal/internal-function.hpp"
#include <memory>
#line 8 "internal/internal-function.hpp"
namespace nyaan_internal {
template <class>
class function_ref;
template <class R, class... Args>
class function_ref<R(Args...)> {
void* obj_ = nullptr;
R (*call_obj_)(void*, Args...) = nullptr;
R (*func_)(Args...) = nullptr;
public:
function_ref() noexcept = default;
function_ref(std::nullptr_t) noexcept {}
function_ref(R (*f)(Args...)) noexcept : func_(f) {}
template <
class F, class Fn = std::remove_reference_t<F>,
class = std::enable_if_t<
std::is_lvalue_reference_v<F&&> &&
!std::is_same_v<std::decay_t<F>, function_ref> &&
!std::is_pointer_v<std::decay_t<F>> && !std::is_function_v<Fn> &&
std::is_invocable_r_v<R, Fn&, Args...>>>
function_ref(F&& f) noexcept {
obj_ = const_cast<void*>(static_cast<const void*>(std::addressof(f)));
call_obj_ = [](void* p, Args... args) -> R {
return std::invoke(*static_cast<Fn*>(p), std::forward<Args>(args)...);
};
}
R operator()(Args... args) const {
if (call_obj_) {
return call_obj_(obj_, std::forward<Args>(args)...);
}
if (!func_) throw std::bad_function_call();
return func_(std::forward<Args>(args)...);
}
explicit operator bool() const noexcept {
return call_obj_ != nullptr || func_ != nullptr;
}
};
template <class, std::size_t Capacity = 32,
std::size_t Align = alignof(std::max_align_t)>
class inplace_function;
template <class R, class... Args, std::size_t Capacity, std::size_t Align>
class inplace_function<R(Args...), Capacity, Align> {
using storage_t = typename std::aligned_storage<Capacity, Align>::type;
storage_t storage_;
R (*invoke_)(void*, Args&&...) = nullptr;
void (*copy_)(void*, const void*) = nullptr;
void (*move_)(void*, void*) = nullptr;
void (*destroy_)(void*) = nullptr;
template <class F>
static R invoke_impl(void* p, Args&&... args) {
return std::invoke(*static_cast<F*>(p), std::forward<Args>(args)...);
}
template <class F>
static void copy_impl(void* dst, const void* src) {
new (dst) F(*static_cast<const F*>(src));
}
template <class F>
static void move_impl(void* dst, void* src) {
if constexpr (std::is_move_constructible_v<F>) {
new (dst) F(std::move(*static_cast<F*>(src)));
} else {
new (dst) F(*static_cast<F*>(src));
}
}
template <class F>
static void destroy_impl(void* p) {
static_cast<F*>(p)->~F();
}
template <class F>
void emplace(F&& f) {
using Fn = std::decay_t<F>;
static_assert(std::is_invocable_r_v<R, Fn&, Args...>,
"inplace_function target is not invocable with this signature");
static_assert(sizeof(Fn) <= Capacity,
"inplace_function target is too large; increase Capacity");
static_assert(alignof(Fn) <= Align,
"inplace_function target alignment is too strict; increase Align");
static_assert(std::is_copy_constructible_v<Fn>,
"inplace_function target must be copy constructible");
if constexpr (std::is_pointer_v<Fn>) {
if (f == nullptr) return;
}
if constexpr (std::is_move_constructible_v<Fn> ||
std::is_lvalue_reference_v<F>) {
new (&storage_) Fn(std::forward<F>(f));
} else {
new (&storage_) Fn(f);
}
invoke_ = &invoke_impl<Fn>;
copy_ = ©_impl<Fn>;
move_ = &move_impl<Fn>;
destroy_ = &destroy_impl<Fn>;
}
public:
inplace_function() noexcept = default;
inplace_function(std::nullptr_t) noexcept {}
~inplace_function() { reset(); }
inplace_function(const inplace_function& other) {
if (other) {
other.copy_(&storage_, &other.storage_);
invoke_ = other.invoke_;
copy_ = other.copy_;
move_ = other.move_;
destroy_ = other.destroy_;
}
}
inplace_function(inplace_function&& other) {
if (other) {
other.move_(&storage_, &other.storage_);
invoke_ = other.invoke_;
copy_ = other.copy_;
move_ = other.move_;
destroy_ = other.destroy_;
other.reset();
}
}
template <
class F, class Fn = std::decay_t<F>,
class = std::enable_if_t<!std::is_same_v<Fn, inplace_function> &&
!std::is_same_v<Fn, std::nullptr_t>>>
inplace_function(F&& f) {
emplace(std::forward<F>(f));
}
inplace_function& operator=(const inplace_function& other) {
if (this == &other) return *this;
reset();
if (other) {
other.copy_(&storage_, &other.storage_);
invoke_ = other.invoke_;
copy_ = other.copy_;
move_ = other.move_;
destroy_ = other.destroy_;
}
return *this;
}
inplace_function& operator=(inplace_function&& other) {
if (this == &other) return *this;
reset();
if (other) {
other.move_(&storage_, &other.storage_);
invoke_ = other.invoke_;
copy_ = other.copy_;
move_ = other.move_;
destroy_ = other.destroy_;
other.reset();
}
return *this;
}
template <
class F, class Fn = std::decay_t<F>,
class = std::enable_if_t<!std::is_same_v<Fn, inplace_function> &&
!std::is_same_v<Fn, std::nullptr_t>>>
inplace_function& operator=(F&& f) {
reset();
emplace(std::forward<F>(f));
return *this;
}
inplace_function& operator=(std::nullptr_t) noexcept {
reset();
return *this;
}
void reset() noexcept {
if (destroy_) destroy_(&storage_);
invoke_ = nullptr;
copy_ = nullptr;
move_ = nullptr;
destroy_ = nullptr;
}
explicit operator bool() const noexcept { return invoke_ != nullptr; }
R operator()(Args... args) const {
if (!invoke_) throw std::bad_function_call();
return invoke_(
const_cast<void*>(static_cast<const void*>(&storage_)),
std::forward<Args>(args)...);
}
};
} // namespace nyaan_internal
using nyaan_internal::function_ref;
using nyaan_internal::inplace_function;
#line 14 "game/impartial-game.hpp"
/**
* ゲームの遷移が DAG で表せる不偏ゲームの solver
*
* Board：盤面の型
* Move は着手の型 or void
* Game は
*
* - splittable = true の場合は vector<Board> (ゲームの分割に対応)
* - splittable = falseの場合は Board
*
* State は次
*
* - Move が void である場合, Game
* - Move が void でない場合, pair<Game, Move>
*
* States は vector<State>
*
* F は Board を引数, States を返り値に取る callable。つまり
*
* - デフォルトの場合 : vector<Board>(Board)
* - splittable の場合 : vector<vector<Board>>(Board)
* - Move != void の場合は返り値の value_type が pair(*, move) になる
*
* 雑にゲームの勝敗を知りたいときはデフォルトでよい
* 最善手の情報が欲しいときは Move の引数を変えて頑張る
*/
template <typename Board, typename Move = void, bool splittable = false>
struct ImpartialGameSolver {
using Boards = vector<Board>;
using Game = conditional_t<splittable, vector<Board>, Board>;
using State = conditional_t<is_void_v<Move>, Game, pair<Game, Move>>;
using States = vector<State>;
using Nimber = long long;
using F = nyaan_internal::inplace_function<States(Board), 64>;
map<Board, Nimber> mp;
F f;
ImpartialGameSolver() = default;
ImpartialGameSolver(const F& _f) : f(_f) {}
template <typename Func,
typename = enable_if_t<is_invocable_r_v<States, Func&, Board>>>
ImpartialGameSolver(Func&& _f) : f(std::forward<Func>(_f)) {}
void set_func(const F& _f) { f = _f; }
template <typename Func>
auto set_func(Func&& _f)
-> enable_if_t<is_invocable_r_v<States, Func&, Board>, void> {
f = std::forward<Func>(_f);
}
template <typename T>
Nimber get(const T& t) {
if constexpr (is_same_v<T, Board>) {
if (mp.count(t)) return mp[t];
return mp[t] = _get(t);
} else if constexpr (is_same_v<T, Boards>) {
Nimber n = 0;
for (const Board& s : t) n ^= get(s);
return n;
} else {
static_assert(is_same_v<T, pair<Game, Move>>);
return get(t.first);
}
}
// 負け局面で呼ぶと RE する
template <typename T>
conditional_t<is_same_v<T, Board>, Move, pair<int, Move>> get_best_move(
const T& t) {
static_assert(is_void_v<Move> == false);
Nimber n = get(t);
assert(n != 0 and "No Best Move.");
if constexpr (is_same_v<T, Board>) {
auto res = change_x(t, n);
if (res.first) return res.second;
} else {
static_assert(is_same_v<T, Boards>);
for (int i = 0; i < (int)t.size(); i++) {
auto res = change_x(t[i], n);
if (res.first) return {i, res.second};
}
}
assert(false and "Error in get_best_move().");
exit(1);
}
private:
Nimber _get(const Board& b) {
States gs = std::invoke(f, b);
if (gs.empty()) return {};
vector<Nimber> ns;
for (State& st : gs) ns.push_back(get(st));
sort(begin(ns), end(ns));
ns.erase(unique(begin(ns), end(ns)), end(ns));
for (int i = 0; i < (int)ns.size(); i++) {
if (ns[i] != i) return i;
}
return ns.size();
}
// nimber が x 変わるような着手を返す
pair<bool, Move> change_x(const Board& b, Nimber x) {
assert(is_void_v<Move> == false);
Nimber n = get(b);
for (auto& st : std::invoke(f, b)) {
if (get(st) == (x ^ n)) return {true, st.second};
}
return {false, Move{}};
}
};
/**
* @brief 不偏ゲーム
*/
Back to top page