終点枕崎

プログラミングとvimと音楽と地理

ABCに初参加した - 僕と競プロ

11/4の AtCoder Beginner Contest (ABC)に参加してきました。ABCはAtCoderが主催するプログラミングコンテストで、100分で4問、主に競プロ初心者を対象としています。

A問題

マス目の数が 2 x 3 で固定だったのでナイーブに実装しました。

#include <cstdio>
#include <cstdlib>

#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define repr(i, a, b) for(int i = (a); i >= (b); i--)
#define range(x) begin(x), end(x)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;

const int iinf = 1 << 29;
const ll linf = 1l << 61;

int main(int argc, char* argv[])
{
	char a[2][4];
	rep(i, 0, 2)
	{
		scanf("%s", a[i]);
	}
	if(a[0][0] == a[1][2] && a[1][1] == a[0][1] && a[0][2] == a[1][0])
	{
		printf("YES\n");
	}
	else
	{
		printf("NO\n");
	}
	return 0;
}

B問題

pow 使ってときました。模範解答は線形探索してたので、この解き方はちょっとずるかったかも。usingしてるのに、std::powとか頭悪いことしてます。

#include <cstdio>
#include <cmath>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;

int main(int argc, char* argv[])
{
	ll N;
	scanf("%lld", &N);
	ll s = std::pow(N, 0.5);
	printf("%lld", s * s);
	return 0;
}

C問題

サイズの小さい順にソートして、累積和 + 動的計画法 でときました。ソートを除けばO(n)。
解説は中段を走査 + 上段・下段を2分探索で解いてました。よく考えたら祭壇の段数は3段で固定なので、別に難しいこと考える必要なかったんですね...。頭が硬いです。

#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define repr(i, a, b) for(int i = (a); i >= (b); i--)
#define range(x) begin(x), end(x)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;

const int iinf = 1 << 29;
const ll linf = 1l << 61;

int N;
int size[3][100800];
// i + 1 段目 j 番目のパーツを一番上にして、i + 1 段目、...、3段目のピースを使ってできる祭壇の種類の数を今 comb[i][j] とする。
// ただしcomb[i][0] = 0 (i = 0, 1, 2), comb[2][j] = 1 (j = 1, 2, ..., N)
// sum[i][j] = comb[i][0] + comb[i][1] + ... + comb[i][j] と定義する。
// size[i][j] < size[i + 1][k] を満たす最小のkをk(i, j)とすると、(満たすkがない時k(i, j) = N + 1)
// comb[i][j] = comb[i + 1][k(i, j)] + comb[i + 1][k(i, j) + 1] + ... + comb[i + 1][N] = sum[i + 1][N] - sum[i + 1][k(i, j) - 1]
// sum[i][j] = sum[i][j - 1] + comb[i][j]
// が成り立ち、結果
// sum[i][j] = sum[i][j - 1] + (sum[i + 1][N] - sum[i + 1][k(i, j) - 1])
// この漸化式を解いていけば良い(sum[0][N]が答えになる)
ll sum[3][100800];

int main(int argc, char* argv[])
{
	scanf("%d", &N);
	rep(j, 0, 3)
	{
		size[j][0] = 0;
		for(int i = 1; i <= N; i++)
		{
			scanf("%d", &size[j][i]);
		}
		sort(size[j] + 1, size[j] + N + 1);
	}

	for(int i = 2; i >= 0; i--)
	{
		int k = 1;
		sum[i][0] = 0;
		for(int j = 1; j <= N; j++)
		{
			if(i == 2)
			{
				sum[i][j] = j;
			}
			else
			{
				while(k <= N && size[i][j] >= size[i + 1][k]) k++;
				sum[i][j] = sum[i][j - 1] + (sum[i + 1][N] - sum[i + 1][k - 1]);
			}
		}
	}
	printf("%lld\n", sum[0][N]);

	return 0;
}

sumとsizeの添え字を1つずらしたせいで色々バグらせましたがなんとかAC。ただ、この解法なら任意の段数でも効率よく解けるはず。

D問題

意味不明でした。解説を見ても意味不明。グラフの問題に帰結させてる?01BFSってなんですか。

感想

楽しかったですが、C問題で、中段を中心に探索するのを思いつけなかったのが最大の心残りです。まだまだ頭が硬いですね...。

僕と競プロ

美談でもなく、競プロとの出会い、JOIが僕の人生に大きな影響を与えました。いずれ話したいなと思っていたことでしたが、今回この場を借りて語ろうと思います。



話は2年前のちょうどこの頃、高校2年の秋まで遡ります。地方の自称進学校でゴミみたいな成績に甘んじていた頃のことです。

中学生の時趣味でCを書いていたので、その惰性で高校でも細々とプログラミングをしていました。そのことを知った情報科目の教師が、JOI予選に出ることを勧めてきました。面白そうだったので参加することにしましたが、競技プログラミングというという単語を初めて聞いたレベルだったので全く期待はしていませんでした。

しかしなぜだか予選を突破してしまい、本選に出ることになりました。当時とても喜びましたが、その後すぐに、本選には進学校のパソコン部で鍛え上げられた強者がわらわら居るということを知って、戦意喪失。その代わり、プロと一度だけでも話してみたい、そう思うようになりました。

そして本選当日。案の定1完で敗退。夜の自己紹介で、約90人の前で「蟻本昨日買いました(本当)」という盛大なギャグをかましたところ「ひっでえなあww」という正直なコメントをもらったのをよく覚えています。そして、その懇親会で出会った情報のプロたちに圧倒されました。自分の遥か上には、頭が良くてかつ魅力的な人がたくさん居るということを、この時初めて知ったわけです。



しかしここで一つ、心の変化がありました。

「勉強は面白い。この人たちと一緒に勉強したい。いい大学に行きたい。」そう思うようになりました。それが、僕が受験勉強を続ける大きなモチベーションになったということは言うまでもありません。裏を返せば、もしもこの人たちに出会わなければ、僕は今の大学に進学していなかっただろうし、大学で勉強などほとんどしなかったことでしょう。



そしてもう一つ、考え方の変化がありました。

それまで僕は、プログラミングができることをあまり人に知られたくありませんでした。そう思っていた理由は今考えるとよくわかりませんが、多分変な奴だと思われたくなかったんだと思います。なので、学校でJOIについて表彰されることになった時、卑屈にも当時の僕はそれを拒否しました。当時の僕にとっては、表彰は全校生徒の前で腹踊りをすることに等しかったのです。しかしながら、先生に「いいから、いいから」と押し切られ、表彰されることになりました。

当日、なぜか自分はトリ。すでに帰りたさ度MAX。そのうち、とうとう僕の番が回ってきました。穴があったら入りたい。

校長「右は何たらかんたら〜〜〜代読。おめでとう。」
校長「みなさん何の事だか分からないと思うので、ちょっと情報オリンピックについて簡単に説明してください。」 え、説明しろなんて聞いてないんだが
僕 「えー...、与えられた問題をプログラムを組んで解く能力を競う、えっと...まあニッチな大会です。」 ちょっとウケた。よかった。
校長「えーみなさんよく分からないと思いますが、彼は灘や開成の生徒たちに混じって戦ってきました。これは非常に名誉なことです。どうぞ拍手を送ってください。」

友人曰く、僕の表彰が一番拍手が大きかったそうです。思ってもみませんでした。みんな「?」みたいな顔をしながらまばらな拍手が起こるのが関の山だと思っていました。

その後、友達やクラスメイト、先生から賞賛を受けて、「プログラミングは胸を張って言える特技の一つなんだ」と気づかされました。自分の好きな事、得意なことを知ってもらうのに、後ろめたさを感じる必要はないのです。それ以来、プログラミングに限らず、自分の特技や趣味を知ってもらうことに抵抗感を持たなくなりました。この考え方の変化は、僕にとって大きなプラスとなりました。それまでと比べて、胸のつかえが取れた気がしました。

本選を通して、僕が競プロ初心者以上の何かになれたかと言えばなれなかったのですが、その代わりに大きな刺激を受けることができました。本選に出場できたことを本当に幸福に思います。



現在、僕は大学で競技プログラミングの自主ゼミに参加し、競プロを一から学んでいます。他にも数学の自主ゼミにも楽しく参加させてもらっています。一緒に勉強できる仲間がいるということは素晴らしいことです。しかし、2年前もし考え方を変えていなかったら、一緒に学ぶ仲間を作ろうともせず、一人細々と趣味に興じていたことでしょう。自分よりも遥か上の存在を知って、刺激を受ける。これが何事においても向上の近道となるわけですね。

区間スケジューリング問題

蟻本p43。社畜の問題です。

問題

{N} 個の仕事 {w_i\ (i=1, 2, \cdots, N)} がある。各仕事 {w_i} の開始時刻は {s_i} 、終了時刻は {t_i} である。あなたは各仕事について参加するか参加しないかを選ばなければならない。ある仕事に参加するならば、その仕事に始めから終わりまで参加しなくてはならない。すなわち、他に参加する仕事と時間か重なってはならない。開始・終了の瞬間だけが重なるのも許されない。

参加できる仕事の数の最大値を求めよ。

制約

  • {1 \leq N \leq 10^5 }
  • {1 \leq s_i < t_i \leq 10^9 }

例えば次のような仕事の集合が入力として与えられた時、
f:id:uchifuji:20171024025451p:plain
最適なスケジュール(のうちの一つ)は赤の仕事。つまり解は4。
f:id:uchifuji:20171024025445p:plain

頭の悪い人

f:id:uchifuji:20171024030424j:plain
計算量のオーダーが { O(2^n) }なのでだめ。

頭のいい人

f:id:uchifuji:20171024030920j:plain
終了時刻の早い順に貪欲に仕事を選んでいくけば最適解が求まります。計算量は平均で {O(n \log n)}。というかソートアルゴリズムに依ります。

開始時刻の早い順に貪欲に選ぶのは不正解です。
次のような仕事の場合、間違った解を導きだします。
f:id:uchifuji:20171024031738p:plain

そうパッと思いつく解法ではないですね。蟻本に証明の概略が載っていましたがいまいちピンとこないので自分で考えます。

証明

アルゴリズム {A} : 選べる仕事(今まで選んだ仕事と重なっていない仕事)の中で終了時刻が最も早いものを選ぶ。これを繰り返す。

与えられた {N} 個の仕事の集合 {W = \{ w_1, w_2, \cdots, w_N \} } に対してアルゴリズム {A} が導きだしたスケジュールに含まれる仕事の個数を {M} 、スケジュールに含まれる仕事の集合を {W' = \{ w_{k_1}, w_{k_2}, \cdots, w_{k_M} \} } とする。ただし { t_{k_1} < t_{k_2} < \cdots < t_{k_M} }{ a = \min\{ s_1, s_2, \cdots, s_N \}, b = \max\{ t_1, t_2, \cdots, t_N \} } とする。

ある仕事 {w_i \in W} があって、適当な仕事 {w_{k_j} \in W' }{W'} から選べば { t_{k_j - 1} < s_i < t_i < t_{k_j} } となる...(1) 、又は { a \leq s_i
 < t_i < t_{k_1} \lor t_{k_M} < s_i < t_i \leq b } ...(2) となると仮定する。

(1)の場合
アルゴリズム {A}{ w_{k_{j-1}} } が選ばれた時点で、開始時刻が { t_{k_{j-1}} } よりも遅い仕事を選ぶことができることは保証される。よって {w_i} は選ぶことができる仕事である。{ t_i < t_{k_j} } であるから、この時アルゴリズム {A} は仕事 {w_{k_j}} ではなく仕事 {w_{i}} を選んでいるはずである。

(2)の場合
(1)と同様の理由で、{w_i}アルゴリズム {A} によって選ばれているはずだが実際には選ばれていない。

いずれにせよ矛盾が発生するから、仮定が間違っていることがわかる。

これを言い換えると、任意の仕事 {w_i \in W} に対し、{ s_i \leq t_{k_j} \leq t_i } となるような仕事 {w_{k_j} \in W'} が存在する。

任意の合法な(時間のかぶる仕事が存在しない)仕事スケジュールを考える。その仕事スケジュールに含まれる仕事の個数を {M''} とし、このスケジュールに含まれる仕事の集合を { W'' = \{ w_{l_1}, w_{l_2}, \cdots, w_{l_{M''}} \} } とする。{ i = 1, 2, \cdots, M'' } に対し { s_{l_i} \leq t_{k_j} \leq t_{l_i} } を満たす {j} のうちの一つを {u_i} とおく。({1 \leq u_i \leq M}) このスケジュールは合法であるから、{u_1, u_2, \cdots, u_{M''}} は互いに異なる。鳩の巣原理から、{M'' \leq M} である。

より、任意の合法なスケジュールの仕事の個数は {M} を超えない。よってアルゴリズム {A} は正しい。

簡単なことを言っているのに

改めて読むと物凄く分かりにくい気がします。説明が下手なのか、はたまたアルゴリズムを数学の言葉で説明すること自体が難しいのか。図を使って説明した方がよかったと今更ながら思います。

急性腸炎にかかった

急に寒くなったと思えば真夏の天気になったりと、体に優しくないこの頃。風邪が流行っていますね。僕の周りでも数人がダウンしている模様です。

そんな中、空気を読まずに腸炎にかかりました。俗に胃腸風邪とか、ノロウイルスとか言われるやつです。胃腸炎という病気は胃腸に炎症が起こる病気全般を指すっていう中々にガバガバ定義で、原因は大きく分けて2つ、細菌が原因のものとウイルスが原因のものがあるそうです。細菌が引き起こす胃腸炎で、食事が原因になるものは食中毒って言われます。O-157とか有名。原因となるウイルスもいくつか種類があって、ノロウイルスアデノウイルス、他にもたくさんあります。

ウイルスごとの特効薬とかないんで、どのウイルスであっても治療法は変わらないらしいです。なのでどのウイルスが原因か特定する必要はないと。詳しい検査もされませんでした。整腸剤を飲みながら自然治癒を待つしかないらしいです。

同じ病気にかかった人の参考になればということで、病状の経過を記したいと思います。

10/6(金)

サークルに行きました。いつもよりも疲労感が溜まって「ちょっといつもと違うな」と感じました。

10/7(土)

朝起きたら鈍い腹痛が。眠気と倦怠感のせいで、なかなかベッドから起きられませんでした。この時点ではただの腹痛だろうと思っていたのでバイトに行きましたが、いざ働き出すと腹痛と倦怠感で死にそうになりました。4時間働いたのち、上司に言って早めに上がらせてもらいましたが、家に帰るのも精一杯な状態。

ここでカレーを食べるという悪手を打ちました。あとで知りましたが、カレーは胃腸に負担がかかるので胃腸炎の時は食べてはいけないらしいです。

家について秒で眠りに落ちて、3時間後に起床。熱を測ると39.7度。これはまずいことになったと思い、この時間でもやってる病院を探して診察を受けました。
しかし症状を話しても「よくわかんない」と言われる始末。解熱剤と整腸剤を処方されました。

10/8(日)

解熱剤が効いたのか38.5度まで熱が下がりました。何食べても下痢で出て辛いので、食事の量を絞り始めました。夜中に腹痛で叩き起こされた上に吐き気まで出てきました。

10/9(月)

日中は平熱まで下がりましたが下痢が続きます。もう出すものもないはずなのに腹痛と水っぽい下痢だけは続くんですよね。夕方から微熱。

10/10(火)

症状変わらず。夜に吐き気が出ました。絶食を始めました。

10/11(水)

近くの総合病院の外来に行って、血液検査とエコー検査、尿検査を受けました。血液検査の結果は、CRP定量が3.5(基準0.3)と高値。これは炎症反応の度合いを示す度数で、この数値が高いと体のどこかで炎症が起きていることがわかります。「小腸のリンパ節が腫れています。ウイルス性の腸炎でしょう。他の臓器に異常はありません。」との診断でした。土曜日に行った病院でもらった整腸剤が効いてる気がしないので、違う種類の整腸剤を処方してもらいました。

夜、とうとう絶食に耐えられなくなり天一のチャーハンを食べたら案の定死にました。

10/12(木)

ようやく熱が下がりました。下痢も一番ひどかった時期に比べれば少なくなりましたね。

10/13(金)

やっと下痢が止まりました。大学にも少し行きました。全快です。

本来2、3日で治る病気らしいんですけど、多分バイトとカレーのせいで引きずった気がします。バイトやめたいです。

std::arrayの初期化

次のコードをclangで-Wallでコンパイルすると警告が出ます。gccでは出ないです。

clangのバージョン : Apple LLVM version 9.0.0 (clang-900.0.37)

[test1.cpp]

#include <array>
#include <iostream>

int main(int argc, char* argv[])
{
	std::array<int, 4> ar = { 0, 1, 2, 3 };

	for(int i : ar)
	{
		std::cout << i << std::endl;
	}

	return 0;
}

[コンパイル]


clang++ test1.cpp -std=c++11 -Wall -o test1.out

test1.cpp:6:28: warning: suggest braces around initialization of subobject [-Wmissing-braces]
std::array ar = { 0, 1, 2, 3 };
^~~~~~~~~~
{ }
1 warning generated.

中括弧の数が足りないと言っています。次のコードでは警告は出ません。

#include <array>
#include <iostream>

int main(int argc, char* argv[])
{
	std::array<int, 4> ar = { { 0, 1, 2, 3 } };

	for(int i : ar)
	{
		std::cout << i << std::endl;
	}

	return 0;
}

std::arrayの実装を読むと、かなり大雑把に言えば次のようになっています。

template<typename _Tp, std::size_t _Nm>
struct array
{
    _Tp _M_elems[Nm];
    //以下メンバ関数
    //......
};

std::arrayには、publicなメンバ変数である_Tp型配列以外のメンバ変数がありません。さらにaggregateの条件を満たしているため、通常の配列と同様の初期化の仕方が可能になります。ただし、std::arrayは配列そのものではなくて配列を唯一メンバ変数に持つ構造体なので、括弧が二重に必要です。

つまり、一重括弧の方が文法的にグレーなのであって、二重括弧の方が本来正しい記述の仕方というわけです。しかしstd::arrayは_M_elemsよりも前にメンバ変数を持たないため、一重括弧でも意図した通りに動くというわけです。

結論としては、二重括弧で書いた方がいいと思います。

余談ですが、std::arrayでも生配列と同じように0初期化が可能です。

std::array<int, 4> ar = {};
std::array<int, 4> ar = { 0 };

clangでは、前者だとワーニングは出ませんが後者だと出ます。

二次元配列でも同じように初期化が可能です。{}内の要素が足りない場合、
・数値なら0で初期化
・ポインタならnullptrで初期化
・aggregateならこのルールを再帰的に適用
というルールで初期化を行うからです。次のコードも全て0で初期化できますね。

#include <array>
#include <iostream>

struct vec
{
	int x;
	int y;
};

int main(int argc, char* argv[])
{
	std::array<std::array<vec, 4>, 4> ar = {};

	for(const auto& line : ar)
	{
		for(const auto& cell : line)
		{
			std::cout << "(" << cell.x << ", " << cell.y << "), ";
		}
		std::cout << std::endl;
	}

	return 0;
}

[実行結果]
(0, 0), (0, 0), (0, 0), (0, 0),
(0, 0), (0, 0), (0, 0), (0, 0),
(0, 0), (0, 0), (0, 0), (0, 0),
(0, 0), (0, 0), (0, 0), (0, 0),

モンテカルロ木探索でBlokusのAIを作った

タイトルの通りです。モンテカルロ木探索と呼ばれるアルゴリズムの習作として、blokusというボードゲームの対戦AIを作りました。

Blokus

まずはBlokusについてご説明。4人のプレイヤーはそれぞれ自分の色(赤・黄・青・緑)のピースを持ち駒として持ち、4人で順番に持ち駒を20x20のマス目状のボードの上に配置していく。ピースは正方形が1〜5個繋がったもので、全部で21個ある。(余談だが、このように正方形を辺でつなげた図形をポリオミノといい、特にn個の正方形をつなげた図形をn-オミノと呼ぶ。blokusのピースはモノミオ、ドミノ、トリオミノ、テトロミノ、ペントミノからなる。)

ピースを置く際には、以下の制約に従う。

  • 初めの順番が来たら、ボードの角のマスを埋めるようにピースを置く。
  • それ以降は、自分のすでに置いたピースと角で接するように、そして辺で接しないようにピースを置いていく。色の違うピースは辺で接していても構わない。

f:id:uchifuji:20170914235542j:plainf:id:uchifuji:20170914235546j:plain

全員がピースを置けなくなったらゲーム終了。

f:id:uchifuji:20170914235548j:plain

勝ち負けの計算方法は2通りあって、単純に残りの手持ちピースのマス目の総数が少ない人が勝者という方法と、前者に付け加えて全部置けた時にボーナス得点が入るような方法があります。今回は前者の方法を採用しました。

モンテカルロ木探索

囲碁などによく使われるゲーム木探索のアルゴリズムであるモンテカルロ木探索について軽く説明します。

ある程度までゲーム木を展開したら、残りは終局までランダムに手を打って(これをプレイアウトと呼ぶ)勝率を計算し、最善手を近似的に導き出す探索方法を原始モンテカルロ法と言います。この探索方法は囲碁と相性がいいです。理由は2つあって、

  • ランダムに打っても必ず終局を迎える。(将棋などはランダムに打っても終局に向かう確率はほぼ0に等しい)
  • 囲碁の評価関数を作るのは困難である。

評価関数とは、盤面が自分にとってどれくらい有利な状況であるかを評価する関数です。ミニマックス法などの有名な戦略アルゴリズムに必要となります。囲碁は他のゲームと違って優劣を決める決定的ものが全くありません。プロでさえ経験から生まれる第六感で判断するほどです。それに対し、原始モンテカルロ法は終局で勝ち負けを判断するだけでいいので、評価関数が不要です。

ただ当然この原始モンテカルロ法は弱いです。特にハメ技に弱い。多くの場合有利な状況になるが、相手がうまい手を打てば一気に不利になるといった状況で逆転されやすいのです。それを防ぐにはより深くゲーム木を展開できるようにする必要があります。

この欠点を解消したのがモンテカルロ木探索です。説明は下記のページに任せます。簡単に言えば、有望な手(=暫定の勝率が高い手)を優先的に深読みしつつ、まだ未探索の手もバランスよく探索する仕組みになっています。時間をかければいつか最善手に収束するらしいです。今回は、ゲーム木を展開する優先度としてUCB値を利用したUCTアルゴリズムを使うことにします。

参考にしたページ:
http://repository.essex.ac.uk/4117/1/MCTS-Survey.pdf
http://ustimaw.hatenablog.com/entry/2014/12/14/081423
モンテカルロ木探索についての文献をいくつか見ましたが、文献によって言ってることが違って非常に困りました。最終的に上の2つを参考に実装することにしました。)

モンテカルロ木探索のBlokusへの適応

Blokus囲碁は共通点が多いです。

  • 陣取りゲームである。
  • ランダムに手を打って終局に向かう。
  • 評価関数を作るのが難しい。
  • 将棋のように「勝ち筋」を見極めるよりかは、大局的な判断が重要になる。

なのでBlokusにもモンテカルロ木探索が有効なのではないかと考えました。

問題点は、Blokusが4人対戦ゲームであることです。これは、1位を1.0勝、2位を0.75勝、3位を0.5勝、4位を0.25勝として扱うことで対応しました。

実装

プログラミング言語C++を採用しました。

Blokusの対戦AIを実装するにあたって難点が一つあって、Blokusは合法手(ゲーム違反にならない手)を列挙するのが大変です。なぜかというと、まず合法手の数が多い。そして、2つ目は合法手を列挙する処理に工夫が必要なことです。

事前にテストした結果、一番最初のプレイヤーの合法手は232通り、ゲーム序盤〜中盤には合法手は800手を超えてくるようです。囲碁は盤面の大きさから高々400通り、将棋は最大593通りです。単純計算では、多いときは2手先を全て読むのに640000通り、3手先は512000000通りの盤面を展開しなければならないわけです。

囲碁の合法手の列挙は楽です。ルール違反のマスを除いて、空いているマスのほとんどの場所に駒が置けます。それに対して、Blokusの合法手の条件は些か複雑です。ピースの種類と向き、そしてピースを置く位置によってピースの置き方を区別するとおよそ15万通りあるため、ナイーブに実装すると時間がかかりすぎます。

なので、今回は合法手の列挙の処理の記述が作業の大部分でした。約0.1msで全手列挙できるまで削りました。ゲーム開始から終局までのプレイアウトは約6msです。時間があればもう少し高速化したいです。

ソースコードは後日一週間以内にアップします。

結果

AIの思考時間は15秒以内に絞りました。
単純に僕がクソ弱いのもありますが、僕が先手でも最下位になってしまうくらいには強かったです。2位は一度だけとれました。1位は…いつかとりたいです。

f:id:uchifuji:20170915012122p:plainf:id:uchifuji:20170915012118p:plain(赤が僕)

ただゲーム序盤はやはり弱いです。合法手が多いからでしょうか。UCB値の定数の設定にもよりますが、どうやら最大で3手先くらいまでしかゲーム木を展開していないようです。

なので今後の課題は、序盤の定石を学習させることでしょうか。機械学習のこと全然わからないので、実現はまだまだ先になりそうです。

映画で泣く方法

皆さんは子供の頃、(例えば口喧嘩とかして)怒りながら泣いてしまった経験はないでしょうか?僕はあります。全然悲しくないのに。割とそういう経験ある人はいるみたいです。

最近まで人は悲しいから泣くのだと、なんとなく思ってましたが、どうやら違うようです。単純な話、感情が高ぶった時に涙が溢れてくる。その原因は、悲しみでも、怒りでも、喜びでも、虚しさでも関係ないのですね。考えてみれば、「嬉し泣き」って言葉があるくらいだから至極当たり前です。

ところで、記憶のある限り、僕は映画とかドラマで泣いたことがありません。まあ両者とも元々あまり見ないということは置いといて、最近「泣ける!!感動作!!」の触れ込みで見に行った映画も泣けませんでした。ええ!!あれほど泣けるって評判だったのに!!!って、逆に泣けない自分が不安になるほど。あ、秒速5cmはとても面白かったです。

なんか巷ではやる「泣ける!!!」的な映画って、大半が恋愛がらみな気がします。で、大抵「めちゃ共感した笑!!」みたいな感想なんですけど、「共感した」ってつまり、過去か現在進行形で恋人がいたり、または好きな人がいたりみたいなことが前提になってるんですよね。なんなんですか!!!「少子高齢化が深刻!!若者が恋愛しない!」とか言っときながら結局は恋愛至上主義なんじゃないか!!!!!!

大衆ってのは結構想像力に乏しくて、結局自分が経験した感情につながりのあるものしか想像することができないんだと思います。恋人が死ぬというシーンでも、恋人がいた経験のある人とそうでない人では悲しみの度合いが違うはず。逆に言えば、泣けない人ってのは恋愛経験に乏しい人ってことになりますね。はて誰のことでしょう?

泣ける映画、もっと大きなくくりで言えば面白い物語を作るのって、多くの人が経験したことのある強い感情を想起させるようなシナリオにすれば間違い無いのではないでしょうか。

僕の場合、合格発表の動画を見るとジーンってきます。僕以外にも、人生でおそらく一番努力するであろう受験勉強に思い入れがある人も多いはず。なんというか、合格発表動画の詰め合わせみたいな動画ないですかね。それこそ理屈抜きで泣けると思います。

あと先生や上司に怒られてすごく悔しい経験をした人も多いと思います。そういう上司を見返す映画があったら売れそうな気がします。あ、でもそう言えばそんなドラマありましたね。

思うんですけど、もらい泣きって、一番泣かせ力が高い気がします。一番感情移入がしやすい。ど直球で「泣くほど悲しいのだ」と伝えてくるから、逃れようがありません。実際、僕は人が泣くのを見てもらい泣きした経験が多いです。バライティ番組で感動話のあとタレントがみんな泣いてるのも、まぁきっとそういうことなんでしょう。

やっぱ感情移入って大事ですよねー。年をとるにつれ苦手になっていった気がします。といより、安い感動話とかを純粋に楽しむ心が失われつつある。小学生くらいまでは心霊番組を本気で怖がってたし、中学生くらいまでは、インターネットに乗ってた感動話を友達と読みあったりしてた覚えがあります。しかし、そういった話を楽しむのには余計なことを知りすぎました。もう手遅れ。というかインターネット全体にも同じような変化が起きている気がします。10年くらい前までは感動系のSSやコピペがたくさん転がっていたのに、最近めっきり目にしません。これは皆のネットリテラシーが高まったと喜ぶべきことなのか、はたまた。。。

でも結局、映画で泣ける人ってのはそういった雑念抜きで映画を楽しめる人なんでしょう。それって本当に素晴らしいことだと思います。だってそっちの方が絶対人生楽しいでしょ。

でも卑屈なのって、僕は別にマイナス要素ではないと思うんですよ。むしろパワー。日本文学なんか卑屈さの権化じゃないですか(偏見)。それに卑屈さは時に笑いを生む。逆に卑屈さゼロの太陽100%みたいな人って、付き合ってても疲れそうだし。太宰治が日本を代表する文豪になり、ちびまる子ちゃんが国民的アニメになったのも、日本人のほとんどが卑屈さを持っている確かな証拠だし、それをエンターテインメントとして活用しているのです。

なので僕は、卑屈さを持ちながらも映画で泣けるような人になりたい。

とにかく新しい来年の目標ができました。来年は映画で見事泣いてみせましょう。

僕は耳と目を閉じ口をつぐんだ人間になろうと考えた

今日は攻殻機動隊のおはなしです。まだテレビシリーズしか見ていませんが、何回でも見返したくなるカッコよさ。

知ったきっかけは、S.A.C. 2nd GIGの劇中歌の「トルキア」でした。荘厳な英語とロシア語のボーカル、現代的なシンセサイザーの音作り、それでいてエスニックな曲調。たまらんです。

攻殻機動隊の劇中歌はどれも素晴らしいですよね。もっとたくさんの人に知ってもらいたいです。

そういうわけで、僕のお気に入りをいくつかあげようと思います。

www.youtube.com
みんな大好きトルキア。一番のお気に入りです。

www.youtube.com
あえてアニメシーンの動画にしました。サイトーさん渋すぎますよね。流れるシーンも含めて好きな曲です。

www.youtube.com
S.A.C.のオープニング曲ですね。サビ前の不穏な感じが心をくすぐりますね。

www.youtube.com
言わずと知れた名曲。アニメシリーズを見終わった前と後とで全く印象が違う曲でした。見終わる前はいたって普通の曲って印象でしたが、見終わった後はより孤独感とか終末感を感じますね。

やはり見れば見るほど完璧なアニメだと思います。話の展開やシーンとBGMの絡み合いが絶妙。一話完結のストーリーは初見でも理解できるので、一周目でも内容が訳分からなさすぎてつまらなくなるってことがありませんでしたね。ミーハーでも楽しめるように気遣いができています。

そういうわけで、是非アニメみてくださいな。