不围棋(NoGo)是一种在 \(9 \times 9\) 的棋盘上进行的一种棋类游戏,游戏下子限制为禁止在棋盘上产生围棋中的吃子,最终无法行动的一方失败,另一方获得胜利。详见 Botzone 上的 NoGo。 = = 这个东西作为 AI 大作业就意味着要……爆肝……然后我把我的 Documentation 粘在下面了…… 还是挺高兴的,第一次写出了 UCT,打爆了上次想写却没写出好的五子棋 AI 的我。

Abstract

Bot 是一个主体采用了 Alpha Beta 优化的最大-最小搜索和上限置信区间蒙特卡洛树搜索(Upper Confidence Boundary Applied to Trees, UCT)的 NoGo Bot。Alpha-Beta 搜索的部分采用了可行步数差来评估局面好坏,应用了 Pattern Match 等评估方法为 Alpha Beta 优化顺序、实现剪枝、作为第二关键字为搜索结果排序,并实现了自适应搜索深度以适应前后期可达深度不同导致的时间利用不充分的问题;UCT 部分使用了经典 UCT 的实现,并且通过估价值限制一定的随机性来提高模拟的有效性,并且每一步初始时利用已有知识初始化了胜率。通过前后期算法的分治,总体胜率能达到第一梯队水平,并使得即使贪心策略被克制的情况下,仍有着不低的胜率。


Algorithm Analysis

在下面的描述中,我们令 \(N = 9 \times 9 = 81\),为棋盘大小。

作为一个完全知识博弈游戏,NoGo 游戏显然存在必胜与必败策略。然而,基于我们的算力远无法遍历 \(O(3 ^ {N})\) 种局面,亦无法遍历 \(O(N!)\) 种合法棋局,我们只能通过剪枝、估价和随机模拟的方法来实现,这在 Bot 中全有体现。

我们通过多局游戏后可以发现开局局势非常简单,此时几乎靠估价函数来进行布局——多产生「眼」,也即最简单的产生可行步数差方式,并且抑制对方产生「眼」,利用 Pattern Match 以及类似的其他方法可以很方便地求得这样的点。当然,不同的估价函数——无论怎么调参——得到的答案可能会存在「循环克制」的问题,Bot 在后面会有针对这种情况进行优化。

到游戏中期时,局面已经变得比较复杂,简单的估价已经无法很好地求得答案了。此时 Alpha-Beta 搜索派上了用场。通过对后几步的预测,Alpha-Beta 可以很轻松地避免因贪心导致的短视,亦可以稳健地在对手出现失误时获得优势。事实上,Bot 的开局也综合估价函数来应用了 Alpha Beta 搜索来避免被估价克制和压制棋力非常弱的对手。

可以发现,随着深度限制 \(k\) 的增长,搜索完第 \(k\) 层的时间 \(t(k)\) 约是 \(O(s ^ k)\) 的,\(s\) 为可行步数。注意到有 \[(\sum_{i = 1}^{k-1} t(i)) < t(k)\] 其中 \(t(k)\) 为搜索完第 \(k\) 层的时间。所以,Bot 采用了迭代加深来进行搜索,充分利用了时间限制。

不过,因为前期通常来说只能搜索出约 \(3\) 层的结果,Bot 前期使用了剪枝,可以在第一步时达到 \(6 \sim 7\) 层。

到游戏偏后期但 Alpha Beta 仍搜索不到游戏终结的时候,由于单纯的评价可行步数差效果很差,搜索里可行步数差相同的不同结果可能会导致不同程度的类似「奇数步赢偶数步输」的情况,单纯应用 Alpha Beta 搜索容易盲目地将自己的优势葬送掉。

UCT 的一次 Simulation 的复杂度为 \(O(Ns)\),其中 \(s\) 为可行步数,前期在 \(1s\) 的时限下只能进行 \(O(10 ^ 2)\) 次模拟,远远不能满足算法准确性需要。然而,注意到中后期后继状态不算多了,Simulation 也能运行约 \(O(10 ^ 3)\) 次,评估胜率也显得比较准确了,因此 Bot 此时采用了通过估价值限制一定的随机性以提高模拟效率的蒙特卡洛搜索来进行 UCT 搜索以在中后期维持并获得优势。

到游戏终局时,胜负已可以轻易判定。为了方便评测,Bot 用 Alpha Beta 来以非常短的时间做出每一步的决策。

这里说一下在 OJ 上的 \(261\) 个版本里出现过的但是最终被抛弃掉的部分尝试:

  1. 在 Alpha Beta 到深度限制时采用多元化估价以替代单一的步数差的估价。这样看起来很优秀,甚至可以避免出现前述缺点,但实际上这样严重依赖于估价函数的准确性以及和其他 bot 的克制性,效果很差。
  2. 在 Alpha Beta 估价时使用 \(O(N ^ 2)\) 的试下策略(Dot Evaluation)来优化贪心函数的短视。这样看起来很棒棒,但是牺牲的复杂度实在是太高,最终极大影响到了搜索的深度,因此最终被舍弃。
  3. 限制 UCT 模拟步数,到达指定深度时用 \[r = \frac {1 + e ^ {-k}} 2 \times D ^ s\] 来预测胜率,其中 \(k\) 为步数差,\(s\) 为任一玩家剩余可行步数,\(D\) 为衰减常数,\(\sqrt[81]{0.1} < D \leq 1\)。
    这样做效果确实不错,OJ 上上传的 IG.TheShy(223) 就是这么做的。然而,为了算法的纯粹性(强迫症),以及为了使 UCT 更稳定,Bot 没有采用这一做法。(然后因为这个原因 Bot 最终被吊打了)

Implementation Introduction

为了尝试使用 OOP 实现程序,Bot 中所有用到的结构体全部进行了封装,模块化实现功能,提高了程序的可拓展性与鲁棒性。这在 Bot 的开发中得到了体现:迭代升级的过程非常流畅,未曾需要对主体程序进行重构。当然,因为存在部分冗余函数,并且需要参数传递,程序相对冗长、常数较大是不可忽视的缺点。

局面使用了 Board 来保存;UFset 是并查集;Point 是用来替代 std::pair<int, int> 的传递坐标的位置,实现了和 pair<int, int> 相互的类型转换;策略保存在 Alpha_BetaUCT 中,两个类都有一个 public 函数 Action()

Board

判断一个局面是否可行的函数 Board::valid() 使用的是随机合并并查集来实现的,复杂度为 \(\Omega(N) \sim O(N \log N )\)。众所周知,判断气数是否合法完全可以使用 Flood Fill 实现,复杂度为 \(O(N)\),看似更优,实则不然。首先,无论是 DFS 还是 BFS 都会用到速度较慢的数据结构,包括栈和队列,常数很大;其次,\(M = 4 N\),边数本身就有大常数。而并查集由于大量的合并操作以及随机合并顺序导致 \(O(N \log N)\) 是非常松的上界,况且其 \(\log N \approx 6 \) 本来就非常小(可看做常数),并且 f[x] = getf(f[f[x]]) 利用寻址比递归快的特性跑得比西方记者快得多。因此,并查集运行的实际效果远优秀于 Flood Fill,甚至优秀于严格 \(O(N \alpha(N))\) 的按秩合并路径压缩并查集。在之后的描述中,我们将 Board::valid() 的复杂度称为 \(O(N)\)。

一个非常常用到的操作是 Board::getValidMoves(),也寻找一个局面下的可行操作。常规的做法是使用 \(O(N ^ 2)\) 的复杂度,进行试下并用 Board::valid() 判断。显然,这个复杂度是不优秀的。Bot 里实现了一个 \(O(N)\) 的 Board::getValidMoves(),使用对联通块的气计数的方法来优化判气复杂度。当然,由于我们两部分搜索都会用到对估价值进行排序,实质上调用一次 Board::getValidMoves() 复杂度是 \(O(N \log N)\) 的,不过由于 \(N\) 很小,并且其余部分函数本身常数就不小,因此这个 \(\log\) 是可以接受的。

Evaluation

对于评分系统,我们主要介绍 Pattern Match。Board::EyeDetect 实现了对 Pattern 的处理,Board::EyeDetect::eval() 通过枚举每一个位置可能成为一口气的方法,来对开局进行比较有效的估价。

我们通常都不会优先去走只有自己能走的点——那样通常会降低自己占气的优势。因此,Bot 针对这种情况进行了判断,对敌人能走的点提高优先级。

以人类智慧设置的参数显然并不一定准确。为了提高评分准确性,Bot 在本地通过模拟退火算法进行了 \(O(10 ^ 4)\) 局左右互搏的游戏,获得了一个效果更好的参数——当然,由于最初退火时没有客观的 UCT 版本对打,最终参数有过拟合的趋势,最终没有采用退火结果。

Alpha Beta

Alpha-Beta 实现部分通过评分系统加扰动来确定搜索顺序,使得搜索有随机化,并使 Alpha-Beta 剪枝更有效,并间接实现了使用贪心值作为二关键字排序,估价相同时默认保留第一个结果,自适应地完成了前中期的交替。

在对选择进行剪枝时,我们可以发现:尽管我们自己的选择从来都是估价函数得到的结果中的前几个,但敌人很可能选择出乎意料的走法。我们知道估价函数是不准确的,所以我们搜索时可以默认敌人比我们更
「聪明」。因此,Bot 的剪枝的限制对于敌人更加宽松,而对于自己的选择则适当收紧,这样在损失极少正确性的情况下 Bot 可以使搜索获得更深的深度。

UCT

UCT 实现很常规,探索常数按论文取到了 \(C= 2\)。说几点优化:

  1. 预处理了所有有关 sqrt, log, exp 的函数;
  2. 使用估价函数加大扰动来实现一种「总体而言,更倾向于采用估价函数大的一步下的随机方法」的模拟,提高了模拟效率;
  3. 每一步初始时利用已有知识初始化了胜率;
  4. IG.TheShy 等版本中采用了前述公式来减少模拟步数,预测胜率;
  5. 随机数发生器采用了 xor-shift-128+,复杂度低且随机性好。

Algorithm Switcher

当可行选择数在 \((L, R)\) 之间时调用 UCT,否则调用 Alpha Beta。在提交版本中,\(L=9,R=27\)。

One more thing…

有时,搜索程序会返回必败,此时搜索会无返回结果。秉承着永不言败的精神,Bot 将会返回一个最有希望的合法点,以期望对手下错来赢得该局游戏。

Code

调用 init() 进行初始化,调用 GetUpdate() 更新敌方策略,调用 Action() 来进行决策。

/* This is a simple NoGo bot written by fstqwq(YANG Zonghan).
 * Current Version : Alpha-Beta + UCT Version
 * For my lovely Lily
 */
#include <bits/stdc++.h>
#include "submit.h"
using namespace std;

/****** Magic ******/

#pragma GCC optimize("-O3")
#define __ __attribute__((optimize("-O3")))
#define inline __ __inline __attribute__((__always_inline__, __artificial__))

/***** Constants *****/

extern int ai_side;
string ai_name = "lily";
typedef signed char stone;
const int N = 9;
const stone NONE = 0, BLACK = 1, WHITE = 2;
const int INF = 999, TLE = 2333;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
const int x8[] = {-1, -1, 1, 1, 1, -1, 0, 0}, y8[] = {-1, 1, -1, 1, 0, 0, 1, -1};
const time_t TIME_LIMIT = time_t(CLOCKS_PER_SEC * 0.9);
const int Score[5] = {99, 32, 16, 8, 4};
const int DefaultDotLimit = 99; // deprecated

/****** Data Structures and Functions ******/

double sqLOG[300000], sq[300000], EXP[100]; // precalculate anything related to sqrt(), log(), exp()
inline double Rate(const int x) {
    return x > 0 ? 1 - EXP[x] : EXP[-x];
}
inline constexpr stone Switch(const stone x) {return stone(3 - x);}
inline bool legal(const int i, const int j) {return i >= 0 && i < N && j >= 0 && j < N;}
inline int min(int a, int b) {return a < b ? a : b;}
inline int max(int a, int b) {return a > b ? a : b;}

inline uint64_t xorshift128plus() { // xorshift128+, from Wikipedia
    static uint64_t s[2] = {200312llu + uint64_t(time(NULL)) * uint64_t(s), 9999999919260817llu ^ uint64_t(dx)};
    uint64_t x = s[0];
    uint64_t const y = s[1];
    s[0] = y;
    x ^= x << 23; // a
    s[1] = x ^ y ^ (x >> 17) ^ (y >> 26); // b, c
    return s[1] + y;
}

inline unsigned Rand() {
    return (unsigned)xorshift128plus();
}

template <class T> inline T Rand(const T st, const T ed) {
    return T(xorshift128plus() % (ed - st + 1)) + st;
}

template <class RandomIt> inline void Shuffle(RandomIt first, RandomIt last) { // random_shuffle()
    for (int i = int(last - first) - 1; i > 0; --i) {
        swap(first[i], first[Rand(0, i)]);
    }
}

template <int SIZE> struct UFset { // Union-Find Set
    int f[SIZE];
    inline UFset () {
        for (int i = 0; i < SIZE; i++) f[i] = i;
    }
    inline void clear () {
        for (int i = 0; i < SIZE; i++) f[i] = i;
    }
    inline int & operator [] (const int x) {return f[x];}
    __ int getf(const int x) {
        return f[x] == x ? x : (f[x] = getf(f[f[x]])); // magic
    }
    inline void merge(const int x, const int y) {
        if (getf(x) != getf(y)) {
            f[getf(y)] = getf(x); // no need of optimization
        }
    }
    inline bool isRoot(const int x) {
        return f[x] == x;
    }
};

struct Point { // pair of int
    int x, y;
    inline Point () {}
    inline Point (const int a, const int b) {x = a, y = b;}
    inline Point (const int a) {x = a / N, y = a % N;}
    inline Point (const pair <int, int> a) {x = a.first, y = a.second;}
    inline Point operator = (const Point b) {x = b.x, y = b.y; return *this;}
    inline bool operator < (const Point &a) const {return x < a.x || (x == a.x && y < a.y);}
    inline operator pair<int, int>() const {return make_pair(x, y);}
};

int lasteval; // Record last value of evaluation, optimization of constant
bool isUCT; // Avoid passing too much bools, optimization of constant

struct Board { // Chessoard
    struct EyeDetect { // A data structure that can evaluate the board by eye detection
        int a[N][N];
        inline int at(const int i, const int j) const {return a[i][j];}
        inline int at(const Point x) const {return a[x.x][x.y];}
        inline void eval(const Board &board, const stone hand) { // Complexity : O(N ^ 2) with constant of 5
            memset(a, 0, sizeof a);
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) if (!board.at(i, j)) {
                    int c[3] = {0};
                    for (int d = 0; d < 4; d++) {
                        int tx = i + dx[d], ty = j + dy[d];
                        if (board.at(tx, ty) >= 0) c[board.at(tx, ty)]++;
                    }
                    if (!c[1] || !c[2]) {
                        const int val = Score[c[0]];
                        if (c[Switch(hand)]) a[i][j] += val;
                        for (int d = 0; d < 4; d++) {
                            int tx = i + dx[d], ty = j + dy[d];
                            if (!board.at(tx, ty)) {
                                a[tx][ty] += val;
                            }
                        }
                    }
                    for (int d = 0; d < 4; d++) {
                        int tx = i + x8[d], ty = j + y8[d];
                        if (board.at(tx, ty) >= 0) c[board.at(tx, ty)]++;
                    }
                    a[i][j] += c[hand];
                }
            }
            a[0][0] += 8; a[N - 1][N - 1] += 8;
            a[0][N - 1] += 8; a[N - 1][0] += 8;
        }
    };

    stone g[N][N];
    inline Board () {memset(g, 0, sizeof g);}
    inline Board (char x) { memset(g, x, sizeof g); }
    inline stone * operator [] (const int x) { return g[x]; }
    inline stone at(const int i, const int j) const { if (i >= 0 && i < N && j >= 0 && j < N) return g[i][j]; else return -1;}
    inline stone at(const Point x) const {if (x.x >= 0 && x.x < N && x.y >= 0 && x.y < N) return g[x.x][x.y]; else return -1;}
    inline void set(const int i, const int j, const char k) {g[i][j] = k;} 
    inline void set(const Point x, const char k) {g[x.x][x.y] = k;}
    inline void reset(const int i, const int j) {g[i][j] = 0;}
    inline void reset(const Point x) {g[x.x][x.y] = 0;}

    inline bool valid() const { // Complexity : O(N ^ 2) // Unused
        UFset<N * N> f;
        int chi[N * N];
        memset(chi, 0, sizeof chi);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) if (g[i][j]) {
                for (int d = 0; d < 4; d++) {
                    int ti = i + dx[d], tj = j + dy[d]; 
                    if (legal(ti, tj)) {
                        if (g[ti][tj]) {
                            if (g[ti][tj] == g[i][j]) {
                                f.merge(i * N + j, ti * N + tj);
                            }
                        }
                        else chi[i * N + j]++;
                    }
                }
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (g[i][j] && !f.isRoot(i * N + j)) {
                    chi[f.getf(i * N + j)] += chi[i * N + j]; 
                }
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (g[i][j] && f.isRoot(i * N + j) && !chi[i * N + j]) {
                    return false;
                }
            }
        }
        return true;
    }

    inline void sort_by_eval(vector <Point> &a, const bool MY[N][N], const bool EN[N][N], const stone hand, const int chi[N * N]) { // Complexity : sort(s ^ 2)
        static pair<int, Point> ret[81];
        static EyeDetect Eval;  
        Eval.eval(*this, hand);
        int c = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) if (MY[i][j]) {
                int value = (EN[i][j] * 16 + chi[i * N + j] * 4 + Eval.at(i, j)) * 1024 + Rand() % (isUCT ? 16384 : 2048); // Consider value of enemy's availability and randomization
                ret[c++] = make_pair(-value, (Point){i, j});
            }
        }
        sort(ret, ret + c);
        a.resize(c); // Avoid push_back()
        for (int i = 0; i < c; i++) a[i] = ret[i].second;
    }

    inline void getValidPoints(const stone hand, vector <Point> &ret) { // Complexity : O(N ^ 2) + sort_by_eval()
        static UFset<N * N> f;
        static int chi[N * N];
        static bool MY[N][N], EN[N][N];

        // Clear
        ret.clear();
        f.clear();
        memset(chi, 0, sizeof chi);
        memset(MY, 0, sizeof MY);
        memset(EN, 0, sizeof EN);

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) if (g[i][j]) {
                for (int d = 0; d < 4; d++) {
                    int ti = i + dx[d], tj = j + dy[d]; 
                    if (legal(ti, tj) && g[ti][tj] && g[ti][tj] == g[i][j]) {
                        f.merge(i * N + j, ti * N + tj);
                    }
                }
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) if (!g[i][j]) {
                for (int d = 0; d < 4; d++) {
                    int ti = i + dx[d], tj = j + dy[d]; 
                    if (legal(ti, tj) && g[ti][tj] && chi[f.getf(ti * N + tj)] >= 0) {
                        chi[f[ti * N + tj]] = -(chi[f[ti * N + tj]] + 1);
                    }
                }
                for (int d = 0; d < 4; d++) {
                    int ti = i + dx[d], tj = j + dy[d]; 
                    if (legal(ti, tj) && g[ti][tj] && chi[f.getf(ti * N + tj)] < 0) {
                        chi[f[ti * N + tj]] = -chi[f[ti * N + tj]];
                    }
                }
            }
        }
        int aval = 0, eavl = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) if (!g[i][j]) {
                int o[3] = {0}, c[3] = {0}, e = 0;  
                for (int d = 0; d < 4; d++) {
                    int ti = i + dx[d], tj = j + dy[d]; 
                    if (legal(ti, tj)) {
                        if (g[ti][tj]) {
                            c[g[ti][tj]]++;
                            if (chi[f.getf(ti * N + tj)] == 1) o[g[ti][tj]]++;
                        }
                        else e++;
                    }
                }
                if ((o[1] == 0 || o[1] < c[1] || e) && (!o[2]) && (c[1] + e)) (hand == BLACK ? (aval++, MY) : (eavl++, EN))[i][j] = 1;
                if ((o[2] == 0 || o[2] < c[2] || e) && (!o[1]) && (c[2] + e)) (hand == WHITE ? (aval++, MY) : (eavl++, EN))[i][j] = 1;
                chi[i * N + j] = o[hand];
            }
        }
        lasteval = aval - eavl;
        sort_by_eval(ret, MY, EN, hand, chi); // shuffle the return value by eye evaluation
    }

    inline int eval(const stone hand) const { // Complexity : O(N ^ 2)
        int ret = 0;
        static UFset<N * N> f;
        static int chi[N * N];
        f.clear();
        memset(chi, 0, sizeof chi);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) if (g[i][j]) {
                for (int d = 0; d < 4; d++) {
                    int ti = i + dx[d], tj = j + dy[d]; 
                    if (legal(ti, tj) && g[ti][tj] && g[ti][tj] == g[i][j]) {
                        f.merge(i * N + j, ti * N + tj);
                    }
                }
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) if (!g[i][j]) {
                for (int d = 0; d < 4; d++) {
                    int ti = i + dx[d], tj = j + dy[d]; 
                    if (legal(ti, tj) && g[ti][tj] && chi[f.getf(ti * N + tj)] >= 0) {
                        chi[f[ti * N + tj]] = -(chi[f[ti * N + tj]] + 1);
                    }
                }
                for (int d = 0; d < 4; d++) {
                    int ti = i + dx[d], tj = j + dy[d]; 
                    if (legal(ti, tj) && g[ti][tj] && chi[f.getf(ti * N + tj)] < 0) {
                        chi[f[ti * N + tj]] = -chi[f[ti * N + tj]];
                    }
                }
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) if (!g[i][j]) {
                int o[3] = {0}, c[3] = {0}, e = 0;  
                for (int d = 0; d < 4; d++) {
                    int ti = i + dx[d], tj = j + dy[d]; 
                    if (legal(ti, tj)) {
                        if (g[ti][tj]) {
                            c[g[ti][tj]]++;
                            if (chi[f.getf(ti * N + tj)] == 1) o[g[ti][tj]]++;
                        }
                        else e++;
                    }
                }
                if ((o[1] == 0 || o[1] < c[1] || e) && (!o[2]) && (c[1] + e)) ret++;
                if ((o[2] == 0 || o[2] < c[2] || e) && (!o[1]) && (c[2] + e)) ret--;
            }
        }
        return lasteval = (hand == BLACK ? ret : -ret);
    }
};

/****** Main Strategies ******/

Board Main;
stone my, en;
int Step = 0;
time_t StartTime;

inline bool isTLE() {return clock() - StartTime > TIME_LIMIT;}

class Alpha_Beta {
    private:
    __ int dfs(const int Steps, const stone hand, int alpha, const int beta) {
        if (!Steps) return Main.eval(hand);
        if (isTLE()) return -TLE;
        vector <Point> choice;
        Main.getValidPoints(hand, choice);
        int width = min(16 + (choice.size() < 50) * 16 + (hand == en) * 16, (int)choice.size()); // Limit the width of searching, assuming that enemy is wiser
        for (int j = 0 ; j < width; j++) {
            const Point &i = choice[j];
            Main.set(i, hand);
            int value = -dfs(Steps - 1, Switch(hand), -beta, -alpha);
            Main.reset(i);
            if (value == TLE) return -TLE;
            if (value >= beta) return beta;
            if (value > alpha) alpha = value;
        }
        return alpha;
    }

    int ans_value = -INF;
    Point ans = {0, 0};

    public:
    inline pair<int, int> Action() {
        isUCT = 0;
        vector <Point> choice;
        Main.getValidPoints(my, choice);

        ans = *choice.begin(); // assert choice.size() > 0
        ans_value = -1;

        unsigned StepLim = 2;
        while (!isTLE() && abs(ans_value) < INF) {
            int tmp_value = -INF;
            Point tmp = ans; // Instead of {0, 0}, never say die.

            unsigned vised = 0;
            for (auto i : choice) {
                Main.set(i, my);
                int value = -dfs(StepLim, en, -INF, -tmp_value);
                Main.reset(i);  

                if (value == TLE) break;

                vised++;

                if (value > tmp_value) {
                    tmp_value = value;
                    tmp = i;
                }
            }
            if (vised == choice.size()) {
                ans = tmp;
                ans_value = tmp_value;
                StepLim++;
            }
        }

        return ans;
    }
};

class UCT {
    private:
    static constexpr int ROUNDS_PER_GAME = 10;
    static constexpr double C = 1.4;
    struct Node {
        Board board; stone hand;
        vector <Point> choice;
        vector <Node*> son;
        Node* fa;
        unsigned size, now;
        int N;
        double Q;
        inline double value(const int faN) const {
            return (double)(N - Q) / N + C * sqLOG[faN] / sq[N];
        }
        inline Node* BestChild() const {
            if (!now) return NULL;
            Node *ret = son[0]; double rv = 0;
            for (unsigned i = 0; i < now; i++) {
                double val = son[i]->value(N);
                if (val > rv) ret = son[i], rv = val; 
            }
            return ret;
        }
    };

    Node t[int(1e5)], *ptr, *root;

    inline Node* newNode(const Board &x, const stone hand, const Point step = {-1, -1}, Node* fa = NULL) {
        ptr->board = x;
        ptr->hand = hand;
        ptr->fa = fa;
        if (fa != NULL) ptr->board.set(step, Switch(hand));
        ptr->board.getValidPoints(hand, ptr->choice);
        ptr->size = (unsigned)ptr->choice.size(), ptr->now = 0;
        ptr->son.resize(ptr->size);
        ptr->N = 0, ptr->Q = 0;
        return ptr++;
    }

    inline void update(Node *x, double Y) {
        while (x != NULL) {
            x->N += ROUNDS_PER_GAME;
            x->Q += Y;
            Y = ROUNDS_PER_GAME - Y;
            x = x->fa;
        }
    }

    inline Node* expand(Node *x) {
        x->son[x->now] = newNode(x->board, Switch(x->hand), x->choice[x->now], x);
        update(x->son[x->now], ROUNDS_PER_GAME * Rate(lasteval));
        return x->son[x->now++];
    }

    inline Node* policy(Node *x) {
        while (x->size) {
            if (x->now < x->size) return expand(x);
            else x = x->BestChild();
        }
        return x;
    }

    inline double simulation(const Node *x) {
        static Board tmp;
        static vector <Point> choice;
        int T = ROUNDS_PER_GAME; double Y = 0;
        while (T--) {
            stone hand = x->hand;
            tmp = x->board;
            while (true) {
                tmp.getValidPoints(hand, choice);
                if (!choice.size()) {
                    Y += int(hand != x->hand);
                    break;
                }
                tmp.set(choice[0], hand);
                hand = Switch(hand);
            }
        }
        return Y;
    }

    public:
    inline pair<int, int> Action() {
        isUCT = 1;
        ptr = t; 
        root = newNode(Main, my);

        // UCT Search
        while (!isTLE()) {
            Node *x = policy(root);
            double result = simulation(x);
            update(x, result);
        }
        Node *bc = root->BestChild();
        Point ans;
        for (unsigned i = 0; i < root->now; i++) {
            if (root->son[i] == bc) {
                ans = root->choice[i];
                break;
            }
        }
        return ans;
    }
};

Alpha_Beta alphabeta;
UCT uct;

inline void init() {
    cerr << "GLHF" << endl;
    if (ai_side == 0) my = BLACK, en = WHITE;
    else my = WHITE, en = BLACK;
    // precalculate
    for (int i = 0; i < 100; i++) EXP[i] = exp(-i) / 2;
    for (int i = 1; i < 300000; i++) sqLOG[i] = (double)sqrtl(log(i));
    for (int i = 1; i < 300000; i++) sq[i] = (double)sqrtl(i);
}

inline void GetUpdate(pair<int, int> location) {
    Step++;
    vector <Point> choice;
    Main.getValidPoints(en, choice);    
    Main.set(location, en);
}

inline pair<int, int> Action() {
    Step++;
    StartTime = clock();

    if (Step == 1) { // First move of BLACK
        Main.set(make_pair(0, 0), my);
        return make_pair(0, 0);
    }

    vector <Point> choice;
    Main.getValidPoints(my, choice);

    Point ans;
    if (choice.size()) {
        ans = (9 < choice.size() && choice.size() < 27) ? uct.Action() : alphabeta.Action(); // divide-and-conqure on algorithms
    }
    else {  // Never say die!
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) if (!Main.at(i, j)) {
                choice.push_back({i, j});
            }
        }
        if (choice.size()) ans = choice[Rand() % (choice.size())];
    }

    Main.set(ans, my);
    return ans;
}

唔……张老师让我每天写总结……QwQ
2016.6.21

今天去七中玩耍第一天,地铁居然这么快好评。

上午做题,

T1是欧拉心算,我居然推出来了(虽然的确很简单);

T2是一道很简单的卷积,我竟然没看出卷积的本质……最开始思路卡在了我去年出过的一道题上,不仅超级麻烦而且时间跑满了。后来发现枚举端点不仅快而且好……暴力艹了过去。事实上可以FFT,因为本质上就是个卷积。

T3动态仙人掌,求加点后的直径。然而我连树的部分分都不会……后来被讲题时才点醒,LCT维护距离就好了。(讲正解时睡过去了TAT

然后下午晚上开始花式字符串。

你们怎么那么熟练啊?QAQ

我反正基本上都不太会,跟节奏都显得比较吃力。

不管吧,至少多见了很多奇技淫巧。

而且至少没颓废了,想了题了。

希望能够跟上dalao们的节奏吧……

 

吃饭好贵啊QAQ一天40快破产了。(听YJQ说便当和肥肠粉便宜

哦中午返校我不知道怎么进学校,碰了下大门被保安质问好久……(我演技不够熟练233)

碰到精爷,他说在七中过得很好,恩祝福他能够在七中得到更好的资源和条件吧。

2017.6.22

我甚至记不到FancyCoder老师到底讲了什么…大概只记得一个K维数点了…而且我觉得按照bitset的做法空间是不是会炸啊?TAT

下午第一题我推出了一个幂求和可搞的多项式……然后掏出wwwwodddd3.pdf乱抄一通= =,第二题神tm bitset,第三题好神的字符串啊TAT不会。

于是210,输出无解得了10分。

好像这个世界就我一个写第一题的N log N呢……不过幸好我只有一步带log,跑起来和O(N)最慢的差不多。

晚上因为没课我回家昏睡了10个小时 = =。

2017.6.23

上午是陈老师的题。他们太强啦怎么什么都会做啊?于是我敲了三道暴力。结果还有一道差点敲挂了,交上去前才改了出来。于是20+50+70,感谢陈老师良心暴力分;然而mcfx 290…绝望。

于是下午大家又水水地把三道题带过了。我只能一个人上去找陈老师深入交♂流(捂脸

啊呸哪里来的交流明明是单向的(逃

2017.6.24

唔…神tm计数不会,于是我怼T2……退火加三分套三分,交上去居然有70分,改了改就90了……orz……

他们怎么什么题都会啊,讲课那么快……

2017.6.25

膜Seter……HackVM手玩了59分233,然后被HackVM的Quine吓尿了,还有这种操作.jpg。然后他们都会点分TAT……

晚上神tm讲提答,结果讲着讲着就变成构造专场了……

2017.6.26

T1怎么这么简单……T2推结论失败,于是上wiki强行看懂上升幂符号然后顺便hack了一波大爷们的代码2333……结果我0写成1滚了……

晚上神tm数学……博弈比什么几何有趣多了……

2017.6.27

三道YJQ良心送分题……

然而我T1 dfs x -> X 丢了88分 TAT

T2暴力打挂只有15……

T3没去推也是个暴力分

于是垫底滚了

2017.6.28

网络流写挂 100 -> 10

暴力写挂 70 -> 0

又垫底啦2333

YJQ讲博弈比Seter有趣!

2017.6.29

YJQ出原题!哼。

T2出锅强行改题意233……然而我凸包写挂滚了。

于是又垫底咯233

2016.6.30

T1 sbdp……然而司机写了一个特别神的六方dp,神到令人 目瞪口呆.jpg ,然而再神也T了……233

T2 矩形面积并好强啊!

T3 dp好神啊!

2017.7.1

简单Fail树上线段树合并……

然而其他都不会了233凸包都写挂了

2017.7.2

T1看来像是一个简单AC自动机……然而有坑,首先因为字符集很大我们不能像26一样直接更新Fail指针到每个节点,但是暴力跳要T。于是需要一颗主席树……差点TLE orz

T2 T3 神题 orz

2017.7.3

T1 挺蠢的呀TAT我没想到是我傻

T2 最小割树可过……而且因为度数小,FF比dinic快?艹

T3 cnmbmdzz

2017.7.4

最开始没看懂T1题意……真丢人,我退群吧

T2 分段计数容斥DP……然后我太菜了只会暴力

T3 强行题意 cnmbmdzz

2017.7.5

毒瘤yjq搬花oj原题

T1是征途加强版……我没看出来这是征途我是不是应该可以退群了

T2 卧槽?这能做?(wsj A了这题后)卧槽?这都能A?

T3 胖题不会自杀吧

2017.7.6

垃圾windows下的lemon不能输出long double 60 -> 0

T2 假题意 cnmbmdzz

T3 提答,出题人给的checker是一坨屎……于是吓得我学习了一下python字符串处理;然后题也不良心,一个meet in the middle可以艹6个点

2017.7.7

LNR day1

签到题想了一个小时

然后T2 woc能做?(然后后来想想题解很有道理orz

T3 小学数学杀TAT……然后被大佬点醒后推了推式子,xjb不用杜教筛拿了60。被xmk老爷证了是 \( \sqrt M\)的,然而常数……

160,似乎打了T2暴力后分数还可以?

2017.7.8

全场梦游心态爆炸

然后都没敢交题不然分数太惨了。

cnmbmdzz

第一题好题?挺厉害的分类讨论dp,但是我就是不会TAT

第二题也是好题?首先展开式子就可以 O(N) 预处理了,然后就可以跑凸包了orz

第三题构造神题 orz

2017.7.9

因为有我的题我就睡过去了Zzzzz

其实T1非常妙。但我的毛病是不去深入思考,于是就暴力分orz

T2其实也很妙?被CTSC论文吓走了。

T3我单独写一篇出题记吧2333,最后看看得分分布很妙呀QwQ

2017.7.10

T1先是被题意杀,后还是不会……然后看了看std,恩很有道理…我记得noip前也有道关于排列的dp用了这个思想然后我也gg了。

T2 虚树居然没挂……233

T3 明明是一道乱搞题非要subtask……orz

2017.7.11

T1 三维数点没卡过去,然后std是个很简单的容斥?oi学傻了,小学都会的东西都不会了

T2 字符串弃疗

T3 挺好推的博弈吧……然后我弃疗了?orz

2017.7.12

T1 状压预处理写挂inf次……卡常技术不高超没卡过去

T2 傻逼网络流,但是标程答案是错的真是 * 苟了;同时学习了一波牛逼的建图,转化的思路挺秒的233

T3 好牛逼的转化

2017.7.13

本来是UNR,起床起晚睡一天

啊呸,睡了一个上午,下午晚上星巴克一直坐着的,xjb切bzoj

2017.7.14

T1 xjb乱搞本来94分,结果subtask 38分……orz

T2 感觉没想到直径实在是太蠢了;数据水到给了20分链

T3 全场都会的sb dp吧……

下午颁奖。于是拿了个光荣垫底奖。不过主要是看表演233

hbb唱START:DASH好萌啊!(为什么不伪声(滑稽

大佬好萌啊QwQ

csz和yjq增援操!哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈

神tm唱歌,结果变成底层群员蹲地上gay来gay去……


说好的写总结,结果写了一大堆废话。

感谢张老师给我这个机会到七中去见了世面,感谢yjq大力相助让我有机会到七中来玩。


唔,越到退役越乱想好多。

曾经的我以为,我一定能够完成前人都能完成的事情。

YJQ 是我真正接触oi后的偶像?233

然后我就以 YJQ所取得的成绩 作为我衡量自己的标准。

 

然而我还是太菜了。

 

noip心态一崩考得特别炸,连500都没上。

然而这仍然阻挡不了我冬令营时候的狂妄,拒了PKU的省队一本。

当时想想,我可是要和他们一样THU的,哪里需要保底。

于是thuwc成功成为了50 ~ 60名中的一个,给了希望,然后幻灭。

省选靠着运气才进了B队。

APIO,我因为NOIP爆炸,连国际金的资格都没有,更何况我还差14分。

THUSC,炸到连面试都没进。

 

还有几天NOI了,结果是未知的,但是其实也是已知的了。

 

似乎,我这一路已经证明了,我也许终将是个弱者。

因为,我既没有足够的天赋,也没有其他天赋异禀的人努力。

自己的能力与努力,远没达到自己的期望,更别谈达到那些真正的强者了。

我看到wxh,我才知道,原来我真的是在浪费时间。

我相比起他们,就是玩了一年高二。

我浪费了那么多时间,我该干的事情都没干;

甚至占走了那些还有着梦想的人的一个省队名额。

 

可我还不想退役啊……

我还有……

好多事没完成啊……

我还有……

好多东西没学啊……

……

但,也许,几天后我就要止步了。

 

至少我这一路走过来,还是付出了一点努力的吧。

不管怎么样,我做过的题虽然少,但是还是比大多数人多了吧。

在弱校搞oi不是借口,但的确有好多好多我在七中同学身上感受不到的无奈。

我能够走到现在,运气的确占了很大成分,但是自我奋斗也许还是有的吧。

虽然,一切我做的事情都太无力太卑微了,更何况我还水。

 

入阵曲,伴我无悔的狂妄。

在两年前…我就想搞一个五子棋bot来愉快玩耍。然后在这么久之后,我不想写题然后颓废…我才搞出一个棋力一般的五子棋bot。(智障选手生无可恋)

当我第一次想写这个bot的时候,我就想肯定价值越大的位置越好嘛!于是直接判可以成5的位置,计算分数,然后贪最大的。当时我甚至没有怎么了解OI,所以根本不知道这个东西被称为估价函数。

结果呢?跑起来被我自己吊着打……于是当时我弃疗了,留下了一个vb写的对局棋盘框架。

究其原因,我的估价函数是非常不优秀……因为我直接取了做了估价函数;并且统计方式是,从一个点向上下左右扩展,这导致本来成不了5的点都会被统计进入答案。

一年后(去年)我重新看代码的时候发现了这个问题,于是我改变了估价方式,从统计一个点变成了对于所有成5的可能全部判一遍,并且给每种可能成5情况的所有点同时加上价值。这样做,虽然似乎不能准确地判断出死活(例如死4仍然有活4一半的价值),但是已经可以比较清晰的体现棋子位置的价值了。同时经过手动退火(……),找到了一些看起来比较优秀的估价值。跑起来,终于能下赢我自己啦!同时百度上面的智障五子棋小游戏也下平了。

然后拿去班上给同学玩,结果被吊着打。(……)

首先,这样做的话估价函数的强弱完全决定了这个bot棋力的强弱,但是事实上找到的估价函数并没有非常优秀。其次,我的统计方式本来就不太科学,例如上面的判死活等等。

然而最重要的是,贪心短视地令人嗤之以鼻。

Now Turn : #
+ 010203040506070809101112131415
01                              
02                              
03                              
04                              
05                     O        
06               #   #          
07     O ? O   O O #   #        
08       ? # O # # # O          
09         O # # O O            
10       # O O   #              
11                              
12                              
13                              
14                              
15

考虑如上的局面。此时如果是纯贪心,那么通常来说都会选择(7, 5),因为按照估计函数的计算(7, 5)更加优秀;然而事实上,如果不走(8, 5),那么白棋走(8, 5)就已经是杀棋了。

于是那时的我想起,有往后算XX步的说法,恍然大悟:哦原来可以使用搜索。然后我写了一个搜三步的程序……不过因为我当时对局面的判断取得是总和而不是最大值,效果非常差。

然后今年我又想颓废,于是我就重新看了看自己的程序,发现简直是个逗逼……

重新写了一个基于以下策略的五子棋bot:
1. Min-Max搜索,加上Alpha-Beta剪枝;
2. 为方便Alpha-Beta剪枝,每步对决策按估价函数排序,选择尽量大的先搜索;
3. 估价函数应设计为一定要能够体现出输赢,并且尽量反映局势。注意到五子棋的输赢和全局关系不大,只要一个地方非常优就可以赢了,所以这里我采用的是max(我)-max(敌)作为反应局势。

看起来非常靠谱……事实上,我调调写写搞了很久,结果效果和贪心差不多。

直到一天半后,我才发现:

哇,我botzone上面的黑白读反了。

改了以后瞬间在botzone上登顶了。(UPD: 已经被打爆啦 QAQ)

(2017.06.12 17:05)

然而实际上这个bot棋力是不够的……甚至我随便下了一个手机五子棋都下不过;一些同学也可以轻易手爆这个bot。

假定估价函数足够准确,那么采用Min-Max搜索出的结果应该是非常好的。
然而现实总是没有那么令人满意……总是。很难找到一种准确的评价局面的方式,原因和贪心的错误类似。这里如果没法准确评价局面,那么Min-Max搜出来的最好结果也不是最好的。

更正确的姿势是用蒙特卡洛树搜索,即基于一定程度随机化的搜索。这种搜索通常来说都有一个特性,以随机化为基础,并且只看游戏终局带来的影响。即,不到游戏结束,不停止往更深的地方搜索。这样虽然是随机化的,但是效果会好很多。Hob让我写uct……然而我觉得我不能继续颓废在bot上面了,于是就暂时先写到这里了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <ctime>
#include <cstdlib>
#include <iomanip>
using namespace std;

inline int min(int a, int b) {return a < b ? a : b;}
inline int max(int a, int b) {return a > b ? a : b;}
inline double min(double a, double b) {return a < b ? a : b;}
inline double max(double a, double b) {return a > b ? a : b;}

#define Lim 15
const double eps = 1e-4;

struct point {
    int x,y;
    double v;
    point () {}
    point (int a, int b, double c) {x = a, y = b, v = c;}
    bool operator < (point a) const {
        return v>a.v;
    }
} tmp[23][233];

double Src[Lim + 1];

int G[Lim + 1][Lim + 1],cnt[3];
double t1[Lim + 1][Lim + 1], t2[Lim + 1][Lim + 1], (*att)[Lim + 1] = t1, (*dfn)[Lim + 1] = t2;

string myData;

char tt[Lim * Lim];

void printBoard() {
    myData += "+ 010203040506070809101112131415\n";
    for (int i = 1; i <= Lim; i++) {
        sprintf(tt, "%02d",i); myData += tt;
        for (int j = 1;j <= Lim; j++) {
            myData += ' ';
            switch (G[i][j]) {
                case 0: myData += ' '; break;
                case 1: myData += '#'; break;
                case 2: myData += 'O'; break;
            }
        }
        myData += '\n';
    }
}

inline void check(int a,int b) {
    memset(att,0,sizeof(double) * (Lim + 1) * (Lim + 1));
    memset(dfn,0,sizeof(double) * (Lim + 1) * (Lim + 1));
    for (int i=1;i<=Lim;i++) {
        cnt[1] = cnt[2] = 0;
        for (int k = 0; k <= 3; k++) cnt[G[i][1 + k]]++;
        for (int j=1;j<=Lim-4;j++) {
            cnt[G[i][j+4]]++;
            if (cnt[b]==0) for (int k=0;k<=4;k++) att[i][j+k] += Src[cnt[a]];
            if (cnt[a]==0) for (int k=0;k<=4;k++) dfn[i][j+k] += Src[cnt[b]];
            cnt[G[i][j]]--;
        }
    }
    for (int j=1;j<=Lim;j++) {
        cnt[1] = cnt[2] = 0;
        for (int k = 0; k <= 3; k++) cnt[G[1 + k][j]]++;
        for (int i=1;i<=Lim-4;i++) {
            cnt[G[i+4][j]]++;
            if (cnt[b]==0) for (int k=0;k<=4;k++) att[i+k][j] += Src[cnt[a]];
            if (cnt[a]==0) for (int k=0;k<=4;k++) dfn[i+k][j] += Src[cnt[b]];
            cnt[G[i][j]]--;
        }
    }
    for (int i=1;i<=Lim-4;i++) {
        for (int j=1;j<=Lim-4;j++) {
            cnt[1]=cnt[2]=0;
            for (int k=0;k<=4;k++) cnt[G[i+k][j+k]]++;
            if (cnt[b]==0) for (int k=0;k<=4;k++) att[i+k][j+k] += Src[cnt[a]];
            if (cnt[a]==0) for (int k=0;k<=4;k++) dfn[i+k][j+k] += Src[cnt[b]];
        }
    }
    for (int i=5;i<=Lim;i++) {
        for (int j=1;j<=Lim-4;j++) {
            cnt[1]=cnt[2]=0;
            for (int k=0;k<=4;k++) {
                cnt[G[i-k][j+k]]++;
            }
            if (cnt[b]==0) for (int k=0;k<=4;k++) att[i-k][j+k] += Src[cnt[a]];
            if (cnt[a]==0) for (int k=0;k<=4;k++) dfn[i-k][j+k] += Src[cnt[b]];
        }
    }
}

inline void upd(int x, int y, int a, int b, int f) {
    for (int i = max(1, x - 4); i <= x && i + 4 <= Lim; i++) {
        cnt[1] = cnt[2]=0;
        for (int k=0;k<=4;k++) cnt[G[i+k][y]]++;
        if (cnt[b]==0) for (int k=0;k<=4;k++) att[i+k][y] += f * Src[cnt[a]];
        if (cnt[a]==0) for (int k=0;k<=4;k++) dfn[i+k][y] += f * Src[cnt[b]];
    }
    for (int j = max(1, y - 4); j <= y && j + 4 <= Lim; j++) {
        cnt[1] = cnt[2]=0;
        for (int k=0;k<=4;k++) cnt[G[x][j + k]]++;
        if (cnt[b]==0) for (int k=0;k<=4;k++) att[x][j + k] += f * Src[cnt[a]];
        if (cnt[a]==0) for (int k=0;k<=4;k++) dfn[x][j + k] += f * Src[cnt[b]];
    }   
    for (int d = min(4, min(x - 1, y - 1)), i = x - d, j = y - d;i <= Lim-4 && j <= Lim-4 && i <= x;i++, j++) {
        cnt[1]=cnt[2]=0;
        for (int k=0;k<=4;k++) cnt[G[i+k][j+k]]++;
        if (cnt[b]==0) for (int k=0;k<=4;k++) att[i+k][j+k] += f * Src[cnt[a]];
        if (cnt[a]==0) for (int k=0;k<=4;k++) dfn[i+k][j+k] += f * Src[cnt[b]];
    }
    for (int d = min(4, min(Lim - x, y - 1)), i = x + d, j = y - d;i >= 4 && j <= Lim-4 && j <= y;i--, j++) {
        cnt[1]=cnt[2]=0;
        for (int k=0;k<=4;k++) cnt[G[i-k][j+k]]++;
        if (cnt[b]==0) for (int k=0;k<=4;k++) att[i-k][j+k] += f * Src[cnt[a]];
        if (cnt[a]==0) for (int k=0;k<=4;k++) dfn[i-k][j+k] += f * Src[cnt[b]];
    }
}

inline void update(int x, int y, int a, int b, int c) {
    upd(x, y, a, b, -1);
    G[x][y] = c;
    upd(x, y, a, b, 1);
    swap(att, dfn);
}

const int X = 8;

double dfs(int a, int b, int dep, double alpha, double beta) {
//  printBoard();
    if (!dep) {
        double ma = 0, mb = 0;
        for (int i = 1; i <= 15; i++)
            for (int j = 1; j <= 15; j++) {
                ma = max(ma, att[i][j]);
                mb = max(mb, dfn[i][j]);
            }
        return ma - mb;
    }
    int tot = 0;
    for (int i = 1; i <= 15; i++)
        for (int j = 1; j <= 15; j++) {
            if (att[i][j] > 1e8) return 1e20;
            else if (dfn[i][j] > 1e8) return -1e20;
            if (!G[i][j]) {
                tmp[dep][++tot].x = i;
                tmp[dep][tot].y = j;
                tmp[dep][tot].v = att[i][j] + dfn[i][j];
            }
        }
    nth_element(tmp[dep] + 1, tmp[dep] + min(tot, X), tmp[dep] + tot + 1);
    sort(tmp[dep] + 1, tmp[dep] + min(tot, X) + 1);
    for (int i = 1; i <= min(tot, X); i++) {
        nth_element(tmp[dep] + 1, tmp[dep] + i, tmp[dep] + tot + 1);
        update(tmp[dep][i].x, tmp[dep][i].y, a, b, a);
        double val = -dfs(b, a, dep - 1, -beta - eps, -alpha - eps);
        update(tmp[dep][i].x, tmp[dep][i].y, b, a, 0);
        if (val >= beta) return val;
        alpha = max(alpha, val);
    }
    return alpha;
}

int now, ene, First;

point work() {
    int stp = min(X, cnt[1] * 3);
    check(now, ene);
    int tot = 0;
    for (int i = 1; i <= 15; i++)
        for (int j = 1; j <= 15; j++) {
            if (!G[i][j]) tmp[Lim][++tot] = point(i, j, att[i][j] + dfn[i][j]);
        }
    //printBoard();

    sort(tmp[Lim] + 1, tmp[Lim] + tot + 1);
    double ma = -1e233; int x = tmp[Lim][1].x, y = tmp[Lim][1].y;
    time_t st = clock();
    for (int i = 1; i <= min(11, tot) && (clock() - st) * 1. / CLOCKS_PER_SEC  < 800; i++) {
        if (tmp[Lim][i].v <= tmp[Lim][1].v / 10) break;
        update(tmp[Lim][i].x, tmp[Lim][i].y, now, ene, now);
        double pos = -dfs(ene, now, stp, -1e233, -ma - eps);
    //  myData += to_string(pos) + " -> " + to_string(tmp[Lim][i].x) +  " " + to_string(tmp[Lim][i].y) + "\n"; 
        update(tmp[Lim][i].x, tmp[Lim][i].y, ene, now, 0);
        if (pos - eps > ma) {
            ma = pos;
            x = tmp[Lim][i].x, y = tmp[Lim][i].y;
        }
    }
    return point(x, y, 0);
}
#ifdef _BOTZONE_ONLINE
#include "jsoncpp/json.h"

int tot = 0;

void placeAt(int x, int y, int c) {
    if (x < 0) return;
    G[x + 1][y + 1] = c; cnt[c]++;
}

Json::Reader reader;
Json::Value input;

int A, B;

void read() {
    string str;
    getline(cin, str);
    reader.parse(str, input); 
    int turnID = input["responses"].size();
    for (int i = 0; i < turnID; i++) {
        placeAt(input["requests"][i]["x"].asInt(), input["requests"][i]["y"].asInt(),2);
        placeAt(input["responses"][i]["x"].asInt(), input["responses"][i]["y"].asInt(),1);
    }
    placeAt(input["requests"][turnID]["x"].asInt(), input["requests"][turnID]["y"].asInt(),2);
    if (tot&1) {
        First=0;now=2;ene=1;
    }
    else {
        First=1;now=1;ene=2;
    }
    A = cnt[1], B = cnt[2];
    cnt[0] = Lim * Lim - cnt[1] - cnt[2];
}

Json::Value Position(int x,int y) {
    Json::Value action;
    action["x"] = x-1;
    action["y"] = y-1;
    return action;
}

void print(int x,int y) {
    Json::Value ret;
//  myData = "---- " + to_string(A + B) + " ----\n" + myData + "\n";
    ret["response"] = Position(x,y);
//  if (A + B < 3) ret["globaldata"] = myData;
//  else ret["globaldata"] = input["globaldata"].asString() + myData;
    Json::FastWriter writer;
    cout << writer.write(ret) << endl;
}

#else 
void read() {
    freopen("board.in","r",stdin);
    scanf("%d",&now);
    ene=3-now;
    //printf("[%d %d]\n", now, ene);
    for (int i=1;i<=15;i++) {
        for (int j=1;j<=15;j++) {
            int ch=getchar();
            while (ch<'0') ch=getchar();
            G[i][j]=ch-'0';
            cnt[G[i][j]]++;
        }
    }
    freopen("/dev/tty", "r", stdin);
}

void print(int x, int y) {
//  cout << myData << endl;
    freopen("decision.out","w",stdout);
    printf("%d %d\n", x, y);  
    fclose(stdin);
    fclose(stdout);
}
#endif

int main() {
    for (int i = 0; i < 5; i++) Src[i] = pow(10, i);
    Src[2] *= 2.501;
    Src[5] = 1e10;
    read();
    if (cnt[0] == Lim * Lim) {
        print((Lim + 1) / 2, (Lim + 1) / 2);
        return 0;
    }
    if (cnt[1]==cnt[2]) First=1;
    else First=0;
    point p = work();
    print(p.x, p.y);
    return 0;
}

看到akb在冬令营就切了好多点分治就好慌啊qaq,然后机房里也有一堆人写点分治qaq,然后我就被点分治虐了啊qaq……

树上的点分治是一种针对树上路径统计的问题的算法,通过找到重心使得子问题规模快速下降,再将所有子问题答案合并起来,通常能够将\(O(n ^ 2)\)规模的问题优化为\(O(n \log n)\)或者\(O(n \log ^ 2 n)\)。

先看一道题:
给定一颗\(n \leq 10 ^ 5\)个节点的带权无根树,设\((i, j)\)之间的简单路径边数为\(dis(i, j)\),求所有满足\(dis(i, j) \leq K\)且\(i \lt j\)的数对\((i, j)\)的数量。(CWOJ1201

暴力做法显然,从每个节点开始dfs (bfs是等价的,后文dfs均可以用bfs解决),记录答案即可。时间复杂度为\(O(n ^ 2)\)

但是这样太慢了!我们想要更快的做法。

Continue reading

异或(exlusive OR, XOR, \( \oplus \))是一种非常优美的逻辑/集合运算符。
数学上,对于两个取值为\(S = \{ 0,1 \} \)的量\( p, q \),异或被表示为$$
\begin{alignat}{1}
p \oplus q &=& (\lnot p \land q) &\lor& (p \land \lnot q) \\
&=& (p \lor q) &\land& (\lnot p \lor \lnot q) \\
&=& (p \lor q) &\land& \lnot (p \land q)
\end{alignat}
$$如果用Venn图来表示,就是这样:(From Wikipidia)

其实我们可以用更简洁的语言描述这个运算符$$
p \oplus q = [p \neq q]
$$或者$$
p \oplus q = (p + q) \mod 2
$$异或之所以优美,是因为这是一个满足以下性质的运算符:

Continue reading

莫比乌斯反演通常是利用莫比乌斯函数来简化一类逆向求函数的问题。
设\(F(n)\)与\(f(n)\)是定义在自然数集合上的两个数论函数,并且满足条件$$
F(n) = \sum_{d|n}f(d)
$$或者$$
F(n) = \sum_{n|d}f(d)
$$已知的\(F(n)\),求\(f(n)\)的表达式。

观察\(F(n)\)式:\(F(n)\)被\(F(xn)(x > 1)\)所包含。所以只需容斥就可以逐个求出\(f(n)\)。

但是这样太慢了!于是我们想加速这个过程。
我们希望,存在一个函数,使得\(F(n)\)可以直接被表示出来。

/*** UPD 2018.3.13

如何容斥呢?

我们以第一个函数举例子。

考虑每个约数对答案的贡献,比如 6:
6: +1, 首先 \(F(6)\) 一定要包含进答案;\((f(6)+f(3)+f(2)+f(1))\)
3: -1, 我们发现去掉 \(f(3)\) 只能删掉 \(F(3)\);(\(f(6)+f(2))\)
2: -1, 我们发现去掉 \(f(2)\) 只能删掉 \(F(2)\);(\(f(6)-f(1))\)
1: +1, 我们发现这个时候好像 \(f(1)\) 被删多了,所以加回来。

我们可以发现,这个过程是一个“奇消偶不消”的,也就是说,删去质数个数为奇数时为 -1,否则为 +1;
我们还可以发现,我们对于一个质数不会删第二次,比如对于 \(F(12)\), \(f(12) = F(12)-F(6)-F(4)+F(2)\),和 \(F(6)\) 几乎一样,而没有 \(F(3), F(1)\) 什么事,因为他们相比起 \(12\) 多删了一次 \(2\)。

这样,我们就得到了莫比乌斯函数。

***/

这里给出结论,有莫比乌斯反演公式$$
f(n) = \sum_{d|n} \mu(d) F(\frac nd)
$$或者$$
f(n) = \sum_{n|d} \mu(\frac dn) F(d)
$$其中,莫比乌斯函数\( \mu(n) \)即是我们所要的容斥函数,\( \mu(n) \)定义为$$ \mu(n)=
\begin{cases}
1 \ \quad \quad d = 1 \\
(-1)^k \ n = p_1 p_2 \ldots p_k ,p_i为互异的质数\\
0 \ \quad \quad else \\
\end{cases}
$$同时,\( \mu(n) \)还有几个性质:
(1)\( \mu(n) \)是积性函数,即对于互质的正整数\(a,b\)有$$ \mu(ab) = \mu(a) \mu(b) $$(2)对于任意正整数\(n\)有$$\sum_{d|n} \mu(d) = [n = 1]$$(3)对于任意正整数\(n\)有$$\sum_{d|n} \frac{\mu(d)}{d} = \frac{\varphi(n)}{n}$$这些性质都是可以证明的,详见最后。
利用莫比乌斯函数的第二个性质,可以证明第一个莫比乌斯反演公式:$$
\begin{align*}
f(n) &= \sum_{d’|n}[d’=1]f(\frac N{d’}) \\
&= \sum_{d’|n}f(\frac n{d’}) \sum_{d|d’} \mu(d) \\
&= \sum_{d|n} \mu(d) \sum_{k | \frac n d} f(\frac n {dk}) \\
&= \sum_{d|n} \mu(d) F(\frac n d)
\end{align*}
$$类似的可以证明第二个公式。
当然,因为我们用到了函数的性质,这给人一种钦定的感觉。所以我找到一篇文章完整讲了莫比乌斯函数的朴素证明和构造性证明: http://blog.csdn.net/danliwoo/article/details/51866867

求莫比乌斯函数的话,可以利用莫比乌斯函数的定义在\(O(\sqrt{n})\)的时间内通过分解质因数的方法得到任意\( \mu(n) \)的值:

int mu(int x) {
	int ret = 1;
	for (int i = 2, sqx = (int)sqrt(x); i <= sqx; i++) {
		if (x % i == 0) {
			ret = -ret;
			if ((x /= i) % i == 0) return 0;
			sqx = (int)sqrt(x);
		}
	}
	return ret;
}

也可以在\(O(n)\)的时间内通过线性筛法在筛素数的同时求得\( \mu(1 \ldots n) \)的值:

const int N = 1000000;
const int CNT = 78498;
int prime[CNT + 5], pcnt = 0, mu[N + 5];
bool vis[N + 5];
void linearSieve() {
	mu[1] = 1;
	for (int i = 2; i <= N; i++) {
		if (!vis[i]) prime[++pcnt] = i, mu[i] = -1;
		for (int j = 1; j <= pcnt && i * prime[j] <= N; j++) {
			vis[i * prime[j]] = 1;
			if (i % prime[j]) mu[i * prime[j]] = -mu[i];
			else {mu[i * prime[j]] = 0; break;}
		}
	}
}

首先先看一个并不需要莫比乌斯反演的问题,求$$
\sum_{a=1}^N \sum_{b=1}^N [\gcd(a,b) = 1], \ N \leq 10^7
$$我们发现这个式子后半部分和欧拉函数\( \varphi(n) \)的定义是类似的。因为数对\( (x,y) \)是有序的,所以当\( x \neq y \)时需要算两遍,注意到\( \gcd(x, x) = 1\)的充要条件是\( x = 1\),所以答案就是$$
\sum_{d = 1}^{N} 2\varphi(\lfloor \frac nd \rfloor) \ – 1
$$
那么再来看一个问题,求$$
\sum_{a=1}^N \sum_{b=1}^M [\gcd(a,b) = 1], \ N \leq \ M \leq 10^7
$$对于这道题就不能只用欧拉函数解决了,需要用莫比乌斯反演来解决。我们考虑定义\(F(n)\)与\(f(n)\),然后利用莫比乌斯反演公式来进行转换。
我们发现这样定义\(F(n)\)与\(f(n)\)比较友好:$$
f(n) = \sum_{i = 1}^N \sum_{j = 1}^M [\gcd(i,j)=n] \\
F(n) = \sum_{n|d} \sum_{i = 1}^N \sum_{j = 1}^M [\gcd(i,j)=d]
$$其中,\(f(1)\)就是我们要求的答案,\(F(d)\)就是统计所有\(a|d\)且\(b|d\)的合法的数对\( (a,b) \)的个数。那么就有$$
F(n) = \lfloor \frac Nn \rfloor \lfloor \frac Mn \rfloor
$$于是我们代入前面提到的第二种莫比乌斯反演公式得到$$
f(n) = \sum_{n|d} \mu(\frac dn) F(d) = \sum_{n|d} \mu(\frac dn) \lfloor \frac Nd \rfloor \lfloor \frac Md \rfloor
$$此时我们令\(n = 1\),有$$
f(1) = \sum_{d = 1}^N \mu(d) \lfloor \frac Nd \rfloor \lfloor \frac Md \rfloor
$$这个式子就是答案。

如果通过质因数的方法求\(\mu(1 \ldots N)\),时间复杂度为\(O(N \sqrt N)\),过不了;
如果线性筛预处理\(\mu(1 \ldots N)\),预处理\(O(N)\),查询\(O(N)\),已经能过了;

其实还有更快的查询方法。事实上\(\lfloor \frac Nd \rfloor \)的取值个数非常小(易证一定不大于\(2 \sqrt N \)),并且在\(d\)递增时,\(\lfloor \frac Nd \rfloor \)均是单调不升并且连续的,这意味着,\( \lfloor \frac Nd \rfloor \lfloor \frac Md \rfloor \)的取值对总数是\( O(\sqrt M) \)的!
所以我们可以在\(O(\sqrt M) \)的时间内完成一次查询,实现如下:

for (int i = 1, j; i <= n; i = j + 1) {
	j = min(n / (n / i), m / (m / i));
	ans += (long long)(sum_mu[j] - sum_mu[i - 1]) * (n / i) * (m / i);
}

差不多就这样辣……

用类似的方法,推出和式,有时再加一点其他的优化(比如杜教筛),就是莫比乌斯反演的套路了。
(然而不是莫比乌斯模板题我还是不会做QAQ)

这里有一个Po姐的PPT,写的非常棒,反正能看懂很多东西吧……
PoPoQQQ的良心PPT