Obsidian の Canvas json を Python で扱う方法を考えてみた

こんにちは。突然ですが、Obsidian というメモアプリはご存知でしょうか?
obsidian.md

Markdown のメモの他、Canvas という機能で簡単な図式を書くこともできます。下記は適当に落書きしてみたものです。

Canvas は .canvas というファイルで保存されますが、今回はこのファイルを Python で取り扱う方法について紹介します。

.canvas ファイルの正体 = json

Canvas 機能で図を作成すると、Obsidian Vault のフォルダ内に ***.canvas というファイルが生成されます。このファイルの拡張子を .json に変えて VSCode などのエディタで開いてみると、図に対応するデータが書かれたファイルになっていることが分かります。下記は冒頭の落書きのファイルを .json に書き換えて出てきたものです。

{
	"nodes": [
		{
			"id": "c2a6cd9bac5f3f55",
			"x": -600,
			"y": -153,
			"width": 250,
			"height": 60,
			"color": "1",
			"type": "text",
			"text": "ポテチを食べる"
		},
		{
			"id": "52239ae6b4f15e84",
			"x": 215,
			"y": -126,
			"width": 221,
			"height": 67,
			"color": "1",
			"type": "text",
			"text": "アイスを食べる"
		},
		{
			"id": "2e8cca1b99c9b22e",
			"x": -242,
			"y": -340,
			"width": 302,
			"height": 80,
			"color": "4",
			"type": "text",
			"text": "甘いものが食べたくなる"
		},
		{
			"id": "7488195feb97e72c",
			"x": -242,
			"y": 60,
			"width": 312,
			"height": 80,
			"color": "4",
			"type": "text",
			"text": "しょっぱいものが食べたくなる"
		}
	],
	"edges": [
		{
			"id": "6e26c77fac2ea559",
			"fromNode": "c2a6cd9bac5f3f55",
			"fromSide": "top",
			"toNode": "2e8cca1b99c9b22e",
			"toSide": "left"
		},
		{
			"id": "52c6c125ab12ce78",
			"fromNode": "2e8cca1b99c9b22e",
			"fromSide": "right",
			"toNode": "52239ae6b4f15e84",
			"toSide": "top"
		},
		{
			"id": "474cd8063e26d8fa",
			"fromNode": "52239ae6b4f15e84",
			"fromSide": "bottom",
			"toNode": "7488195feb97e72c",
			"toSide": "right"
		},
		{
			"id": "e1703f60094f0881",
			"fromNode": "7488195feb97e72c",
			"fromSide": "left",
			"toNode": "c2a6cd9bac5f3f55",
			"toSide": "bottom"
		}
	]
}

似たような記述の繰り返しになっているので、すこし丁寧に構造を見てみましょう。
まず、全体は dict の形になっています。key は "nodes" と "edges" の二つです。それぞれグラフ理論の用語で頂点と辺を表すものです。下図でいうと〇がノード、線分がエッジです。

では "nodes" と "edges" には何が格納されているのか見てみましょう。それぞれ list の形になっていて、いくつかの dict が格納されているようです。便宜的に nodes の要素を node、edges の要素を edge と呼ぶことにします。

node は以下のような形をしています。各 node は各カードの情報を記述しているようです。

{
	"id": "c2a6cd9bac5f3f55",  # 各カード(文字が書かれた枠のこと)に対応する ID
	"x": -600,  # カードの左上の頂点の x 座標。単位はピクセル。右方向が正
	"y": -153,  # カードの左上の頂点の y 座標。単位はピクセル。下方向が正
	"width": 250,  # カードの横幅。単位はピクセル。
	"height": 60,  # カードの縦幅。単位はピクセル。
	"color": "1",  # カードの色。"1" は赤、"4" は緑。
	"type": "text",  # カードの中に記述するデータのタイプ
	"text": "ポテチを食べる"  # カードの中に記述するデータ
}

edge は以下のような形をしています。各 edge は各矢印の情報を記述しているようです。

{
	"id": "6e26c77fac2ea559",  # 矢印に対応する ID
	"fromNode": "c2a6cd9bac5f3f55",  # 矢印の根本のカードの ID
	"fromSide": "top",  # カードのどこから矢印が生えるか。top/bottom/left/right のいずれか
	"toNode": "2e8cca1b99c9b22e",  # 矢印の先端のカードの ID
	"toSide": "left"  # カードのどこへ矢印が刺さるか。top/bottom/left/right のいずれか
}

Canvas で書かれた図式は、カードが node(頂点)にあたり、カード同士を結ぶ矢印を edge(辺)とみなしている、という訳ですね。そして各 node と edge の内容には、それらを既定するのに必要な情報がシッカリと書かれているようです。

Pythonjson を扱いたい

ところで Python には json ファイルを取り扱うための機能が標準ライブラリにあります。名前は json と言います。ドストレートですね。
docs.python.org

例えば図式のファイルが "fat_cycle.canvas" だったら、こんな感じ↓で読み込むことができます。

import json

with open("fat_cycle.canvas", "r") as f:
    canvas_data = json.load(f)

print(canvas_data)  # 上記の json が表示される

json.load という関数がファイルの中身を自動で読み取って、Python で扱いやすい dict と list の入れ子に自動変換してくれるというスグレモノです。逆に dict と list の入れ子json ファイルとして保存することももちろん簡単です。そのときは json.dump という関数を使います。

import json

data = {
    "stomach": "empty", 
    "food": "Pudding", 
    "tasks": ["Bath", "Homework"],
}

with open("status.json", "w") as f:
    json.dump(data, f)  # json ファイルとして保存

ここでは保存先の拡張子を .json としましたが、この部分を .canvas とすることももちろん可能です。

Python で .canvas を扱いたい

ここまでの内容から、Python を使えば .canvas ファイルを自在に操ることが可能であることが分かったと思います。しかし、dict と list の入れ子のデータを直接いじいじするのって結構大変そうです。そこで、クラスを使ってもう少しだけプログラムしやすいように整理してみましょう。

.canvas ファイルを構成する要素は node と edge の二つでした。それぞれをクラスで表現することを考えてみます。
まず node に対応するクラス Node を定義します。

from typing import NamedTuple

class Node(NamedTuple):
    id: str
    x: int
    y: int
    width: int
    height: int
    color: str
    text: str

    def to_json(self) -> dict:
        return {
            "id": self.id,
            "x": self.x,
            "y": self.y,
            "width": self.width,
            "height": self.height,
            "color": self.color,
            "type": "text",  # 今回は text の場合のみを扱うので type はハードコード
            "text": self.text,
        }

一対一に構造を対応させるのであれば type も Node クラスのデータに含めるべきですが、今回は type="text" の場合のみを取り扱うと心に決めて、あえて type は外しています。今着目したい目的に合わせて、必要以上の一般化を行わない、というのも時には必要な判断です。

同様に edge に対応するクラス Edge を定義します。

from enum import Enum, auto
from typing import NamedTuple

class Node(NamedTuple):
    ... # (略)


class NodeSide(Enum):
    TOP = auto()
    BOTTOM = auto()
    LEFT = auto()
    RIGHT = auto()


class Edge(NamedTuple):
    id: str
    from_node: Node
    from_side: NodeSide
    to_node: Node
    to_side: NodeSide

    def to_json(self) -> dict:
        return {
            "id": self.id,
            "fromNode": self.from_node.id,
            "fromSide": self.from_side.name.lower(),
            "toNode": self.to_node.id,
            "toSide": self.to_side.name.lower(),
        }

いくつかポイントがあります。

  • from_node, to_node の型は str ではなく Node にしています。最終的には str が渡されるわけですが、プログラムで扱う場合は直接 Node 型のインスタンスが入っていた方が直観的な上、id を取り違えるといったミスも防げます。
  • from_side, to_side は str ではなく NodeSide という enum にしました。入るデータの種類があらかじめわかっていて数えるほどしかない場合は、Enum として定義したほうがプログラムしやすいです。書き間違いも防げます。*1
  • json の key は lowerCamelCase ですが、Python のプロパティは snake_case を採用しています。同じように lowerCamelCase を使ってもよいのですが、一応 PEP8 的な流儀に従ってみました。ここでのポイントは、プログラムを書くときに扱いやすいように決める、ということです。
  • 上記の工夫に伴って、to_json の中では str を作るためのルールが記述されるようになりました。

node と edge をクラスで表現できたので、.canvas のデータ全体に対応するクラスも作っておきます。

from enum import Enum, auto
from typing import NamedTuple

class Node(NamedTuple):
    ... # (略)


class NodeSide(Enum):
    ... # (略)


class Edge(NamedTuple):
    ... # (略)


class Canvas:
    def __init__(self):
        self.nodes: [Node] = []
        self.edges: [Edge] = []
    
    def to_json(self) -> dict:
        return {
            "nodes": [node.to_json() for node in self.nodes],
            "edges": [edge.to_json() for edge in self.edges],
        }

これで .canvas ファイルは Canvas クラスのインスタンスとして表現できるようになりました!*2

Python で .canvas を作る

ここまでのクラスを使って、冒頭の図式っぽいものを Python で作ってみましょう。説明するよりコードを見た方が早いと思うので、いきなりコードを書きます。

# 前略。各クラスを定義しておく


def main():
    import json

    canvas = Canvas()
    canvas = Canvas()
    node_potechi = Node("Potechi", -300, 0, 300, 50, "1", "ポテチを食べる")
    node_want_sweet = Node("WantSweet", 0, -100, 300, 50, "4", "甘いものが食べたくなる")
    node_icecream = Node("Icecream", 300, 0, 300, 50, "1", "アイスを食べる")
    node_want_salty = Node("WantSalty", 0, 100, 300, 50, "4", "しょっぱいものが食べたくなる")
    edge_p2sw = Edge("P2SW", node_potechi, NodeSide.TOP, node_want_sweet, NodeSide.LEFT)
    edge_s2i = Edge("S2I", node_want_sweet, NodeSide.RIGHT, node_icecream, NodeSide.TOP)
    edge_i2sl = Edge("I2SL", node_icecream, NodeSide.BOTTOM, node_want_salty, NodeSide.RIGHT)
    edge_s2p = Edge("S2P", node_want_salty, NodeSide.LEFT, node_potechi, NodeSide.BOTTOM)

    canvas.nodes = [node_potechi, node_want_sweet, node_icecream, node_want_salty]
    canvas.edges = [edge_p2sw, edge_s2i, edge_i2sl, edge_s2p]

    with open("fat_cycle.canvas", "w") as f:
        json.dump(canvas.to_json(), f)


if __name__ == '__main__':
    main()

上記プログラムで生成される fat_cycle.canvas を Obsidian Vault の下において Obsidian で読み込むと、以下のような画像が表示されます。いい感じですね。

プログラムを使って図式を書くことに成功したので、もっと変態的な図式を書くことも可能です。例えば100個のカードが規則的に並んだ複雑な図式なんかも書けそうですね。

Python で .canvas を読み込む

疲れてきたので実装の詳細は省きますが、一応既存の .canvas ファイルを読み込む方法についても述べておきます。
前のセクションでは Node や Edge のインスタンスたちを手で作った上で .canvas ファイルを生成しましたが、ファイルを読み込む場合はこのインスタンスを作る工程をファイル準拠で行うことになります。これを達成するには、以下のように実装すると見通しが良いと思います。

  • Canvas クラスに from_json というクラスメソッドを定義します。実装は「引数に与えられた json のデータの "nodes" に入っているものたちから Node のインスタンス群を作り、そのあと "edges" に入っているものたちから Edge のインスタンス群をつくる」という風に与えます。
  • 上記の Node や Edge を作る部分は、Node と Edge の中で実装を与えるようにします。つまり Node, Edge にも from_json というクラスメソッドを定義するという具合です。こちらも引数で受け取った dict からインスタンスを作れるようにします。

読み込む処理を実装する場合の注意点としては、Node や Edge のクラスの構造としては、読み込む対象に見合うだけのものを準備する必要があることが挙げられます。読み込むファイルが冒頭の落書きのファイルだけなら、ここまでのクラスに新たにメソッドを追加するだけで済むと思いますが、もっと多種多様な機能を使った .canvas ファイル(例えば両方向向きの矢印を使っているとか、画像ファイルを使っているとか)を相手にしたい場合は、より一般的なケースに対応できるようなクラスに拡張することが必要となります。もし何かしら便利ツールを作りたい場合はご注意ください。

まとめ

Python を使って Obsidian の Canvas のファイルを扱う方法について紹介してきました。ぜひ自分で動かしてみて、変態的な図式をたくさん作ってみてください。

なお .canvas の中身である json の構造の仕様については、公式ドキュメントでかなり丁寧に説明されています。この記事で紹介した機能はこのうちのほんの一部なので、もしもっとたくさん機能を使って書きたい場合は参照しながら拡張してみてください。
公式ドキュメント↓
jsoncanvas.org

ではまた。

*1:ちなみに Node の color も Enum で管理するという手もあります。実際公式ドキュメントによれば "1"~"6" それぞれに対応する色があるようです。ただこっちは "1"~"6" の他にも "#FF0000" のようなカラーコードでもよいらしいので、どうすべきか悩みどころです。color に与えられるデータの詳細については、次のページの Color の部分を参照してください。JSON Canvas — JSON Canvas Spec

*2:この記事で与えているものは、Canvas json の仕様を網羅したものではありません。これらを利用する場合は、必要に応じて仕様を追加したり削ったりしてください。Canvas json 自体の仕様は次の公式ドキュメントを参照してください。JSON Canvas — JSON Canvas Spec

円周率を一般化してみた

こんにちは。今回はタイトルの通り、円周率を一般化してみたいと思います。

円周率とは

小学校でも教わったとおり、円周率は円周の長さを直径の長さで割ったものです。大きさの異なる円であっても、この比の値は一定であることから、数学定数として定められています。

数学的に表現する

少し形式的に書き直してみましょう。半径の長さが1である円、いわゆる単位円は、以下の方程式で与えられます。

x^2+y^2=1 \qquad ((x, y)\in\mathbb{R}^2)

この曲線の長さの半分が円周率にあたります。この方程式の左辺はいわゆる2-ノルムを用いて表すことができます。2-ノルムとは u = (u_x, u_y) \in \mathbb{R}^2 に対して

\|u\|_2=\sqrt{u_x^2+u_y^2}

と定義されるものです。2-ノルムを使うと、円の方程式は

\|u\|_2 = 1 \qquad (u \in \mathbb{R}^2)

とシンプルな表現になります。

ノルム

2-ノルムは以下の性質を満たします:

  • \|u\|_2\geq 0
  • \|u\|_2=0 \Leftrightarrow u=0
  • \|cu\|_2=|c| \|u\|_2 \qquad (c\in\mathbb{R})
  • \|u+v\|_2 \leq \|u\|_2+\|v\|_2

一般に、関数 \|\cdot\|: \mathbb{R}^2 \to \mathbb{R} が上記の条件(の添字を除いたもの)をすべて満たすとき、その関数はノルムと呼ばれます*1。つまり2-ノルムはノルムの一種です。

曲線の長さ

次に円周の長さをどう定義するか考えてみます。きっちり書くのは面倒なのでふわっと書くと、曲線の長さは

\displaystyle\text{(曲線の長さ)} = \sup_{\text{折れ線近似全体}} \text{(折れ線を構成する各線分の長さ)}

と定義できます*2。円周を求める場合は、円に内接する多角形をたくさん考えたうえで、それぞれの辺の長さの和を計算し、それらの上限を求めればよいということです。

円周率を一般化する

ここまでは通常の円周率の定義について整理しました。これらを一般化してみましょう。
まず、2-ノルムを一般のノルムに置き換えます。すると一般化された単位円周は

\displaystyle \| u \| = 1 \qquad ( u \in \mathbb{R}^{2})

となります。例えば 3-ノルム:

\displaystyle \| (u_{x}, u_{y}) \|_{3} = ( | u_{x} |^{3} + | u_{y} |^{3})^{1/3}

の単位円周は以下のようになります。

次に円周の長さも一般のノルムで測ることを考えます。具体的には、近似曲線の長さを図っている部分をノルムの値に置き換えればよさそうです。

\displaystyle\text{(ノルム $\| \cdot \|$ での単位円周の長さ)}
\displaystyle= \sup_{\text{単位円周の折れ線近似}} \text{(折れ線を構成する各線分のノルム)}

ここで「線分のノルム」は、その線分を平行移動して、一方の端を原点に一致させたときにできるもう一方の端の値に対して、ノルムを取った値と考えます*3

最後に、一般化円周率を、この単位円周の長さの半分と定義します。

円周を手計算で求めるのは一般に難しいため、円周率も同様に厳しいですが、後ほど具体的な表示が得られるいくつかの場合について計算します。

与えられた図形から円周率を定義する

実は、単位円周にしたい図形を与えると、それを単位円周にするようなノルムがただ一つ定まります。ただしノルムが存在するためには、以下の条件をすべて満たす必要があります。

  • 有界な図形である。すなわちその図形をすっぽり覆うような円が存在する。
  • 凸である。すなわち内部または境界上にある任意の2点に対し、それらを結ぶ線分は内部または境界上にある。
  • 点対称である。

ノルムが定まれば、先ほどの議論を用いて一般化された円周率を求めることができます。つまり、(性質の良い)図形が与えられたとき、(それを単位円周とするような)円周率を定義することができます。

円周率の例

最後にいくつか例を挙げて、具体的に円周率を計算してみます。

例1. 正方形

下図の正方形の円周率を求めます。

この図形は有界かつ凸かつ点対称なので、これを単位円周とするノルムが存在します。実際、

\displaystyle \| (u_{x}, u_{y}) \| = \max ( |u_{x}|, |u_{y}| )

と定めると  \| u \| = 1 がこの正方形に対応します。このノルムの下では、各辺の長さは2になります。例えば (1, 1) から (1, -1) へ伸びるベクトルは、原点から (0, -1) に伸びるベクトルを2つ並べたものなので、半径(=1)の2つ分のため2になります。よって円周の長さは8なので、円周率は4となります。

例2. ダイヤモンド型

次に正方形を45度回転させたような以下の図の円周率を求めてみます。

この図形はノルムが存在するための各条件を満たします。対応するノルムは

\displaystyle \| (u_{x}, u_{y}) \| = | u_{x} | + | u_{y} |

と表されます。この正方形も各辺の長さは2です。よって円周の長さは8なので、円周率は4となります。

証明は省きますが、実は拡大・縮小、回転、反転で一致する図形の円周率は一致します*4

例3. 正六角形

次に下図の正六角形を考えてみます。

これはやはり性質の良い図形です。ノルムは省略します。
各辺の長さは1なので、円周の長さは6になります。よって円周率は3になります。

一般に正2n角形の円周率は以下のようになります。

\displaystyle\begin{cases}
2 n \sin\left( \dfrac{\pi}{2n} \right) & \text{($n$ が奇数の場合)} \\
2 n \tan\left( \dfrac{\pi}{2n} \right) & \text{($n$ が偶数の場合)}
\end{cases}

n = 2 のとき円周率が4になり、n = 3 のとき円周率が3になることを確かめてみてください。またこの式から、n \to \infty と極限をとると \pi に収束することが分かります。

例4. 3から4の円周率となる図形群

最後に、円周率が3と4の任意の値を取るような図形群を与えます。

上の図は以下の式で表されています:

  • 第1, 3 象限:|x|^p + |y|^p = 1 \quad (p \geq 1)
  • 第2, 4 象限:\max(|x|, |y|) = 1

周の長さを求めてみましょう。まず第2,4象限の部分は、各辺の長さが1なので、合計で4になります。第1,3象限の部分の長さを求めるために、下図を考えます。これは円周上に線分を引いたもので、折れ線の一部を取り出したものと考えてください。

濃い緑のベクトルは左上を向いていることから、x, y 成分それぞれの絶対値の最大値がそのノルムになることが分かります。これはちょうど縦の黄緑色の部分の(通常の)長さに相当します。

同様の議論を折れ線を構成する各線分について行い、少しだけ位置調整すると、下図のように正方形の2辺の形に揃えることができます。

この正方形の右上部分の頂点の座標は ( 2^{-1/p}, 2^{-1/p} ) なので、この2辺の長さの和は 2^{1 - 1/p} となります。第4象限も同じ長さなので、合わせると 2^{2 - 1/p} となります。

以上から、周の長さの合計は 4 + 2^{2 - 1/p} なので、円周率は 2 + 2^{1 - 1/p} となります。p = 1 のとき円周率は3で、p \to \infty とすると円周率は4に収束します。この円周率は p について単調増加かつ連続なので、3~4の任意の値を取りうることが分かります。

まとめ

円周率を一般化して遊んでみました。具体的には

  • 単位円周の定義
  • 円周の長さの定義

を一般のノルムに対して定義しなおすことで、円周率を一般化しました。具体的に計算できる例を考えて、3以上4以下の値を取る例を発見することができました。

円周率が3未満また4より大きくなる例も頑張って探してみたのですが、ちょっと見つけることができませんでした。見つけたという方、あるいは存在しないことが証明できたよという方がいれば、ぜひ教えてください。また、円周率が3や4になる例が本質的に*5この記事で計算したものしかないかも気になるところです。

ちなみにナントカ教育で円周率が3と教えられたという噂話があって、そのツッコミとして「円周率が3だったら円が六角形になる!!」とか言われてましたが、奇しくも今回の一般化でも正六角形の場合に円周率が3になりました。ちょっと面白いですね。

ではまた。

*1:通常、ノルムはより一般的な条件で定義されますが、ここではこれで十分です。

*2:より数学的な表現を知りたい方は、例えば解析入門I(杉浦光夫著) の 第IV章 §16 曲線の長さ 定義3 を参照してください。

*3:ここで端の選び方によらないことは \| - u\| = \|u\| であることから従います。

*4:さらに一般に、正則行列により移りあう図形同士でも円周率は一致します。

*5:つまり、正則行列による変換で一致するようなものを除いて。

2024年 京大理系数学 第5問 解いてみた

こんにちは。久しぶりに入試問題を解いたので、私の解答を記事にしたいと思います。

問.  aa \geqq 1 を満たす定数とする. 座標平面上で, 次の4つの不等式が表す領域を D_{a} とする.

  • x \geqq 0
  • \dfrac{e^{x} - e^{-x}}{2} \leqq y
  • y \leqq \dfrac{e^{x} + e^{-x}}{2}
  • y \leqq a

次の問いに答えよ.
(1) D_{a} の面積 S_{a} を求めよ.
(2) \lim\limits_{a \to \infty} S_{a} を求めよ.


※面倒だったのでグラフは用意していません。追う際に必要になったら手元で書いてください。

解答.
(1) x \geqq 0 に対し, f(x) = \dfrac{e^{x} + e^{-x}}{2}, g(x) = \dfrac{e^{x} - e^{-x}}{2} とする.
x > 0 に対し, f'(x) = g(x) および g'(x) = f(x) が成り立つ. x > 0 のとき f(x), g(x) > 0 であることから, f(x), g(x) は単調増加である.
さらに

  • f(0) = 1 \leqq a, g(0) = 0 \leqq a
  • \lim\limits_{x \to \infty}f(x) = \infty, \lim\limits_{x \to \infty}g(x) = \infty

であることから, f(x) = a を満たす x および g(x) = a を満たす x がそれぞれ一意的に存在することが従う. これらはそれぞれ具体的に

  • x = \psi(a) = \log\left( a + \sqrt{a^{2} - 1} \right)
  • x = \phi(a) = \log\left( a + \sqrt{a^{2} + 1} \right)

と書ける. 実際  a + \sqrt{a^{2} \pm 1} \geqq a \geqq 1 より \psi(a), \phi(a) \geq 0 であり, また

  • \dfrac{1}{ a + \sqrt{a^{2} - 1} } = a - \sqrt{a^{2} - 1}
  • \dfrac{1}{ a + \sqrt{a^{2} + 1} } = - a + \sqrt{a^{2} + 1}

より f(\psi(a)) = g(\phi(a)) = a である.
以上の記法を用いると
\displaystyle S_{a} = \int_{0}^{\psi(a)} f(x) dx + \int_{\psi(a)}^{\phi(a)} a dx - \int_{0}^{\phi(a)} g(x) dx
と表される. ただし f(x) > g(x) であることを用いた. 各項を計算すると

  • \displaystyle\int_{0}^{\psi(a)} f(x) dx = \left[ g(x) \right]_{0}^{\psi(a)} = g(\psi(a)) = \sqrt{a^{2} - 1}
  • \displaystyle\int_{\psi(a)}^{\phi(a)} a dx = a( \phi(a) - \psi(a) ) = a \log\left( \dfrac{a + \sqrt{a^{2} + 1}}{a + \sqrt{a^{2} - 1}} \right)
  • \displaystyle\int_{0}^{\phi(a)} g(x) dx = \left[ f(x) \right]_{0}^{\phi(a)} = f(\phi(a)) - 1 = \sqrt{a^{2} + 1} - 1

となる. したがって
\displaystyle S_{a} = 1 + \sqrt{a^{2} - 1} - \sqrt{a^{2} + 1} + a \log\left( \dfrac{a + \sqrt{a^{2} + 1}}{a + \sqrt{a^{2} - 1}} \right).
(2) 次をすべて満たす領域を E_{a} とする.

  •  0 \leqq x \leqq \psi(a)
  •  g(x) \leqq y \leqq f(x)

さらに次をすべて満たす領域を F_{a} とする.

  •  0 \leqq x \leqq \phi(a)
  •  g(x) \leqq y \leqq f(x)

このとき E_{a} \subset D_{a} \subset F_{a} である. よって E_{a}, F_{a} の面積をそれぞれ T_{a}, U_{a} とすると, T_{a} \leqq S_{a} \leqq U_{a} が成り立つ.
T_{a}, U_{a} を計算すると以下のようになる.

  • \displaystyle T_{a} = \int_{0}^{\psi(a)} (f(x) - g(x)) dx = \int_{0}^{\psi(a)} e^{-x} dx = 1 - e^{- \psi(a)}
  • \displaystyle U_{a} = \int_{0}^{\phi(a)} (f(x) - g(x)) dx = \int_{0}^{\phi(a)} e^{-x} dx = 1 - e^{- \phi(a)}

これと \lim\limits_{a \to \infty} \psi(a) = \infty, \lim\limits_{a \to \infty} \phi(a) = \infty から, \lim\limits_{a \to \infty}T_{a} = 1 および \lim\limits_{a \to \infty}U_{a} = 1 が従う. よってはさみうちの原理から \lim\limits_{a \to \infty} S_{a} = 1 である. □

最近やっていること

こんにちは。珍しく散文的な記事を書いてみようと思います。

最近、セカンドベストの必勝法を解析した記事をいくつか書きました。
smooth-pudding.hatenablog.com
smooth-pudding.hatenablog.com
smooth-pudding.hatenablog.com

一番最後の記事の最後で、「絶対に勝てないセカンドベスト作ったら面白いだろうな~」とか言っていましたが、それも実はもう完成しました(権利とか気になる&コードが汚いので広く公開はしません)。そのゲームを作るときに使ったのが Flet という python モジュールです。
flet.dev

Flet は裏側で Flutter というスマートフォンアプリ開発用のフレームワークを呼んでいる python モジュールです。以前はよく tkinter を使って GUI アプリを作成していたのですが、Flet の方が数倍楽ちんに作れる上に、デザインも "モダン"*1 な感じがしていい感じです。セカンドベストは白黒の石さえ表現できればいいので、シンプルなウィジェットの組み合わせでもなかなか悪くない出来になりました。

「絶対に勝てないセカンドベスト」のスクリーンショット

でまあこれはこれでめでたしめでたしなんですが、一つ作ると欲が出るのがエンジニアの性というものです。せっかく Flet 触ったんだから本丸の Flutter もやってみようじゃんということで、ググりながらぼちぼち触っているのが今です。
flutter_rust_bridge とかいう、Flutter で開発するときに Rust で書かれた関数を呼べるようにする機能が公開されていたので↓、これを使ってハトのゲームでも作ってやろうかなと画策しています。
github.com

これができれば、寝転んでハト遊び放題!!!

では、また。

*1:もちろんモダンがなにを指すのかは知りません。

セカンドベストの最適戦略ルートをグラフにしてみた

こんにちは。前回の記事↓では、後退解析の結果を深堀してみました。
smooth-pudding.hatenablog.com

この記事の中で、両者が最適戦略を取った場合の局面のバリエーションを数えました。今回は、この最適戦略のルートを可視化してみます。

なお今回の記事は以下のアドベントカレンダーに参加しています。
adventar.org

可視化の方針

前回の記事で書いた表の一部を抜粋します。

初期からの手数 局面数
0~8 1
9~11 2
12, 13 3

この表では各手数での局面の数しか分からないですが、実際にはどの局面からどの局面になるのかという対応関係があります。これを可視化してみることを考えます。
前回の記事の最後には8手までの進行を紹介しましたが、これは 0~8 の各局面が順番に矢印でつながっているという風に表現できそうです。例えば以下のような感じです。

0~8手目

記号は X{何手目か}_{同じ手数の0から始まる通し番号} という風にしてみました。
次に8手目から9手目に移る際は局面数が増えているので、次善手が2通りあることが分かります。この場合は、X8_0 から矢印をふたつ伸ばして X9_0, X9_1 につなげればよさそうです。同じ考え方で11手目までグラフにしてみるとこんな感じなります。

0~11手目

12, 13 手目に進むところも同様です。以下のような図になります。

0~13手目

どうやら11手目の一方が2つに分岐したようですね。

可視化

この方法で、42手までをすべてグラフにしてみたのがこちら・・・と言いたいところですが、局面数が多すぎて見切れないサイズになってしまうので、35手までの範囲でグラフにしたものを作りました。

0~35手目

これでもだいぶでかいですね。
このグラフをじ~っと眺めていると、途中で長い一本道があることに気づきました。

長い一本道

そこでこの一本道に入るところ以外の道を切って、もう少し先まで追いかけてみましょう。40手目まで出すとこんな感じになりました。

0~40手目(剪定あり)

どうやら一本道だったのは35手目までで、36手目以降はどんどん分岐が進んでいるようでした。

Graphviz と DOT 言語

さて、今回の可視化は Graphviz というツールを使いました。
graphviz.org
Graphviz は DOT 言語と呼ばれる形式で書かれた .dot ファイルを画像ファイルに変換してくれるツールです。
DOT 言語はグラフを記述するための形式で、かなり自由度があります。今回の0~13手目のグラフは、DOT言語で以下のように書いたものです。

digraph besttree {
    X10_1 -> X11_0;
    X6_0 -> X7_0;
    X10_0 -> X11_1;
    X5_0 -> X6_0;
    X7_0 -> X8_0;
    X8_0 -> X9_0;
    X4_0 -> X5_0;
    X12_0 -> X13_0;
    X11_1 -> X12_0;
    X11_0 -> X12_2;
    X12_1 -> X13_2;
    X1_0 -> X2_0;
    X9_0 -> X10_0;
    X0_0 -> X1_0;
    X3_0 -> X4_0;
    X9_1 -> X10_1;
    X11_1 -> X12_1;
    X12_2 -> X13_1;
    X2_0 -> X3_0;
    X8_0 -> X9_1;
}

今回は書き出す順番を気にせずプログラムで自動生成したのですが、結果のグラフはいい感じに整形されていたので、Graphviz が結構内部で頑張ってくれているのかなと思っています。
今回のグラフはシンプルなものでしたが、フローチャートを作ったり、部分的に色を塗ったりと、かなりいろいろなことができるようです。グラフを作ってみることに興味がでた方は、Graphviz や DOT言語というキーワードでぜひ検索してみてください。

おまけ

長い一本道に入った最初の局面は画像の通りです(先手黒手番)。さて、黒手番が次に選ぶべき次善手は何でしょうか?

一本道の最初の局面(先手黒手番)

セカンドベストの最善手・次善手について

こんにちは。前回の記事↓で行ったセカンドベストの解析結果を少し深堀します*1
smooth-pudding.hatenablog.com

この記事は下記のアドベントカレンダーに参加しています。
adventar.org

セカンドベストって何?

ダイソーで売っているとあるボードゲームです。100円とは思えないぐらい面白いゲームです。ルールについては下記動画を見てください。
www.youtube.com

石やボードがしっかりしたつくりのものも別途販売されているようなので、もしダイソーで販売終了しても(ダイソーよりかはかなり値が張るものの)手に入りそうです。
shop.jellyjellycafe.com

後退解析の結果をざっくり

後退解析では、各局面の価値の評価を行いました。ここで局面とは、石の並びと次の手番プレイヤーをセットにして考えたものとします*2。具体的には、すべての局面を以下のいずれかに分類しました。

カテゴリ 説明 総局面数*3
Win(n) n 手で手番プレイヤーの勝利が確定する
(n は 0 または正の整数)
3,842,910
Lose(n) n 手で手番プレイヤーの敗北が確定する
(n は 0 または正の整数)
3,056,738
Both 両者ともに勝利条件を満たしている 1,299,100
Draw 上記のどのカテゴリにも属さない 164,279

ただし Win(n), Lose(n) は「互いに最良のプレイングを行った場合」が前提となっています。
Both は例えば以下の画像のような局面です。Both になった場合は、直前の手番プレイヤーの勝利となります。

黒は横に、白は縦に並んでいる

前回「42手の後手必勝」と述べましたが、上記の表現を使うと「初期局面は Lose(42) に分類される」となります。
なお n の最大値は 140 でした。

最良のプレイングでの局面数

局面の分類が完了したので、各プレイヤーが最良の手(=次善手)ばかりを指した場合に、どれぐらい局面にバリエーションがあるのかを数えることができます。結果は以下のようになりました。

初期からの手数 局面数
0~8 1
9~11 2
12, 13 3
14 5
15 7
16 9
17 10
18 11
19 8
20~24 7
25 9
26 8
27 11
28 10
29 11
30, 31 12
32 17
33 23
34 30
35 42
36 72
37 103
38 147
39 231
40 344
41 800
42 2016

最後の数手は数がそこそこ増えますが、それまではかなりバリエーションが少ないことが見て取れます。特に8手までは一本道のようです。

最善手・次善手をつまみ食い

0手から8手までは一本道ということが分かったので、進行を見てみましょう。また相手がうっかりセカンドベスト宣言を間違えた場合を考えて、「本当は指したい最善手」もついでに見てみます。

0手目(初期局面)

まず初期局面です。説明の便宜のため、図のように各ポジションに1~8の番号を振っておきます。

0手目

1手目(黒手番)

1手目はどこにおいても同じなので1通りです。早速「セカンドベスト!」と宣言するギャグは鉄板です。

1手目

2手目(白手番)

2手目の次善手は1手目の対角線の位置に置く手です。

2手目

本当は指したい最善手は、ポジション1で黒石に重ねる手のようです。これを選べると詰みまで5手短縮できます。

3手目(黒手番)

3手目の次善手はちょうど間の位置に置く手です。

3手目

本当は指したい最善手は、ポジション5で白石に重ねる手のようです。これを選べると形勢逆転し、先手の勝ち局面になるようです。

4手目(白手番)

4手目の次善手は最初の黒石に重ねる手です。

4手目

本当は指したい最善手は、もう一つの白石があるポジション3に重ねる手のようです。これを選べると詰みまで10手短縮できます。

5手目(黒手番)

5手目の次善手は3手目の対角線の位置に置く手です。

5手目

本当は指したい最善手は、ポジション1に三個目として重ねる手のようです。これを選べると形勢逆転し、先手の勝ち局面になるようです。

6手目(白手番)

6手目の次善手はポジション4に置く手です。

6手目

本当は指したい最善手は、ポジション1に三個目として重ねる手のようです。これを選べると詰みまで20手短縮できます。

7手目(黒手番)

7手目の次善手はポジション5の白石に重ねる手です。

7手目

本当は指したい最善手は、ポジション1に三個目として重ねる手のようです。これを選べると形勢逆転し、先手の勝ち局面になるようです。

8手目(白手番)

8手目の次善手はポジション3の白石に重ねる手のようです。

Step8

本当は指したい最善手は、ポジション5に三個目として重ねる手のようです。これを選べると詰みまで16手短縮できるようです。

ちなみに9手目の次善手はポジション1または5に置く手で、本当は指したい最善手はポジション3に置く手のようです(やはり形勢逆転)。

感想

最良ルートを眺めて思ったことを書いてみます。

最初はすこし間をあけて等間隔が強い

最初はどちらも奇数のポジションに石を置いていく手ばかりでした。すこし開けておくことで、相手がどう来ても次の手で対応しやすくなる効果があるのかもしれません。

相手の石に重ねてつぶすのは強い

相手の石に重ねる手は、本当は選びたい最善手で何度も出てきました。相手の石の効果を消しつつ自分の力を得ることができるので、二重に強いといった感じでしょうか。

セカンドベスト宣言の判断をミスると致命的

いずれの局面でも、先手が本当は選びたい最善手を選べたら形勢が逆転しています。これは最善手を見通せるぐらい強い相手だと、1度のセカンドベスト宣言判断ミスで形成が逆転することを意味します。逆に言えば、一つだけ形成を逆転できる手が残るぐらいのバランスで指すのが一番強い、ということかもしれません。

最後に

今回解析により後手が必ず勝てる戦略があることが分かりましたが、これは「このゲームが終わった」ということを意味するのではなく、むしろ「このゲームで遊ぶためのポイントが見えたので、より深くゲームを楽しめるようになった」ということだと思っています。
せっかく後手必勝だと分かったので、今は「絶対に勝てないセカンドベスト」(コンピューターが後手になり、常に最善の動きをしてくる) のゲームを作っているところです。完成したら「くっそ~wwつえ~ww」とか言ってゲラゲラ笑いながら楽しもうと思っています。
ではまた。

*1:今回の記事のために行った追加の解析は、前回の記事で紹介したリポジトリの feature/evaluator ブランチに置いてあります。 GitHub - mat-der-D/second-best-analysis at feature/evaluator

*2:手番プレイヤーをセットにするのは、同じ石の並びでも、次が黒手番なのか白手番なのかで意味が変わりうるからです。

*3:反転や回転で一致するものは同一視します。また石が16個置かれている局面については、プレイヤーとボード上の色を同時に入れ替えることにより一致するものは同一視します。

セカンドベストは後手必勝だった

こんにちは。
先日の記事でセカンドベストというボードゲームの局面数を数えました。その結果、気合を入れて解析していた Tokyo Doves よりもはるかに局面数が少なく、解析の難易度もさほど高くなさそうなことが分かりました。

ということで、解析するコードを書きました↓
github.com

とりあえず実行

上記のプログラムは以下の手順で実行できます。
1. Rust をインストールします。
www.rust-lang.org
2. 先ほど紹介した git リポジトリをクローンします。git がインストールされていてインターネットに接続されている端末であれば、以下のコマンドでクローンできるはずです。

git clone https://github.com/mat-der-D/second-best-analysis

3. リポジトリ直下のところで端末を開き、以下のコマンドを実行します。

cargo run --release

4. 必要な追加のパッケージのダウンロードとビルドののち、計算が開始します。私の手元の環境ではビルド完了から測って35秒ほどで計算が終了します。
5. 画面に以下のように表示されます。

The second player wins in 42 steps

つまり、42手で終わる後手必勝です。

簡単に解説

今回やったことは、ハトの解析でも行った後退解析です。後退解析そのものについては↓の記事でしっかりめに説明したので今回は省略します。
smooth-pudding.hatenablog.com

ハトの解析との違いは以下の3つです。

  • 自滅する手しかない局面が存在すること
  • 最善手ではなく二番目の手しか選べないこと
  • 局面数が極めて少ないこと

自滅する手しかない局面が存在すること

ハトでは、以下の記事で説明したように、その手で負けが確定するような手は回避することができました。
smooth-pudding.hatenablog.com
それにより、ある局面が勝敗が確定しているとすれば、奇数手で勝つか、偶数手で負けるかの二択でした。
一方セカンドベストでは、自分の石を動かしたことにより相手の石がそろってしまうような手しか選べない局面が存在します。
したがってハトの後退解析の記事で説明したように

Win1 → Lose2 → Win3 → Lose4 → ...

という一列とはならず、

Win0 → Lose1 → Win2 → Lose3 → ...
Lose0 → Win1 → Lose2 → Win3 → ...

という二つの列を同時に追いかけることになります。
ちなみにこの追いかける計算は、冒頭のリポジトリでは "analysis::analyze_backward" という関数で行っています。

最善手ではなく二番目の手しか選べないこと

これがこのゲームの最大の特徴ですね。ゲームの実装以上に、探索プログラム部分の実装の方に注意が必要なポイントになっています。
例えば Win1 に属するための条件は、普通のボードゲームであれば

ある手を選べば、即座に自分の勝利が確定する局面

となります。一方セカンドベストでは

それを選ぶと即座に自分の勝利が確定するような手が、少なくとも2つ存在するような局面

となります。この部分に混乱があり、何度かプログラムの書き直しが必要になりました。

局面数が極めて少ないこと

こちらは嬉しい性質です。前回の記事で、各局面を4 byte で集めたとして、全体で 32MB 程度にしかならないと述べました(実際それぐらいでした)。
そのため、ひとつのプログラムですべての局面を列挙した上で、何度もループを回すということが現実的な時間で実行可能になります。
実際、冒頭のプログラムでは最初に 8,363,027 通りの局面を全列挙した上で何度もぐるぐるループして解析しています。
ハトの解析を終わらせるのに、データの工夫や並列計算を駆使しても数カ月かかった*1ことを思えば、はるかに楽な状況でした。

感想

今回もボードはビット演算で表現したのですが、それ自身がとても面白かったです。石を置ける場所の数が "8" だったり、各場所にある石の個数が "0~3" だったりと、ビット演算で表現することを見越して設計したのかと勘違いするぐらいピッタリの数値で、とても気持ちよかったです。実装はすべて冒頭リポジトリで公開しているので、よければその部分も読んで面白みを感じ取ってみてください。
気が向いたら、また別の記事でもう少し必勝の手についても紹介しようと思います。
ではまた。

追記 (2023/12/23)

この記事を作者のダイキチさんにリプライでお伝えしたところ、返信をいただけました↓

  • 返信うれしい!!!!!!
  • ビット演算で設計しやすいのは勘違いではなかった!!!
  • 作者の解析結果と一致していた!!!
  • というか作者も解析してたんだすげぇ!!!

さらに追記 (2023/12/23)


「作者も解析していてその結果と一致していた」は早とちりだったみたいです。
とはいえ経験豊富な作者の方の感覚ともズレていないようなので、きっと大外しはしてないでしょう。たぶん。

*1:実は解析完了しています。まとめたらまた記事にします。