群の公理と同値関係

はじめに

こんにちは。KazukiOtaです。

TSG Advent Calendar 2019 - Adventarの17日目の枠埋めとして書きました。

ちこくしたのはゆるして...(12/17よりも後にAdventarに登録したためです。)


概要

 Gの部分群 Hを用いて、 {\displaystyle a \sim b \stackrel{{\rm def}}{\iff} ab^{-1} \in H}として定められる関係を考えます。

この \simが同値関係であることは、それぞれ次のように対応する群の公理から導かれます。
 {\displaystyle 
\begin{eqnarray}
&群の公理&Ⅰ&:&単位元の存在 &\implies& &同値関係の公理&Ⅰ&:&反射律\\

&群の公理&Ⅱ&:&逆元の存在 &\implies& &同値関係の公理&Ⅱ&:&対称律\\

&群の公理&Ⅲ&:&結合法則 &\implies& &同値関係の公理&Ⅲ&:&推移律\\

\end{eqnarray}
}

準備

  • まず、準備として必要な直積という概念を説明します。
  • 次に、群の公理と同値関係の公理について説明します。
  • 既知の人は飛ばして大丈夫です。
集合の直積

定義 (直積)

 A, Bを集合とします。このとき、 A Bの直積集合 A \times Bを次のように定めます。

 A \times B \stackrel{{\rm def}}{=} \{(a, b) | a \in A, b \in B\}


定義 (群)

集合 Gと演算 *:G\times G \to Gについて、 (G, *)が次の3つの性質を満たすとき、 (G, *)を群と言います。

1.  \exists e \in G, \forall x \in G, e*x=x*e = x
2.  \forall x \in G, \exists y \in G, x*y = e
3.  \forall x, y, z \in G, x*(y*z) = (x*y)*z



注意

  • 1.で与えられる元 e単位元といい、以降 eとして表します。この記事では、1. の性質を「群の公理Ⅰ」と呼びます。
  • 2.で与えられる元 y xの逆元といい、以降 x^{-1}として表します。この記事では、2. の性質を「群の公理Ⅱ」と呼びます。
  • 3.の性質を結合法則といいます。この記事では、3. の性質を「群の公理Ⅲ」と呼びます。
  • 以降 x*yを単に xyと表します。

定義 (部分群)

 (G,*)を群とし、集合 H Gの部分集合とします。このとき、 (H,*)が群であるならば、 (H, *) (G, *)の部分群と言います。



注意

  •  (H, *) (G, *)の部分群であるとき、単に H Gの部分群であると言います。
  •  H Gの部分群であるとき、 Hが演算で *閉じていることも必要です。これは、 (H, *)が群であるとき、 *:H\times H \to Hになる、という条件に反映されています。
同値関係

定義 (二項関係)

 Sを集合とします。

 \sim S上の二項関係であるとは、 \sim S\times Sの部分集合となることを言います。

また、 (a, b) \in S \times Sに対して、 (a, b) \in \;\sim a \sim bと表記します。



定義 (同値関係)

 Sを集合とし、 \sim S上の同値関係とします。 \simが次の3つの性質を満たすとき、 \simは同値関係であると言います。

1.  \forall x \in S, x \sim x
2.  \forall x, y \in S, x \sim y \implies y \sim x
3.  \forall x, y, z \in x \sim y \wedge y \sim z \implies x \sim z



注意

  • 1.の性質を反射律といい、この記事では同値関係の公理Ⅰとも言います。
  • 2.の性質を対称律といい、この記事では同値関係の公理Ⅱとも言います。
  • 3.の性質を推移律といい、この記事では同値関係の公理Ⅲとも言います。

本編

関係の定義
  •  Gを群とし、 H Gの部分群とします。
  •  G上の関係 \sim Hを用いて次のように定めます。
  •  {\displaystyle a \sim b \stackrel{{\rm def}}{\iff} ab^{-1} \in H}
  • これが、同値関係の3つの公理を満たすことは、それぞれ次のようにして示されます。
反射律

 {\displaystyle 
\begin{eqnarray}
    && e \in H \tag{Hの群の公理Ⅰ:単位元の存在}\\
    &\iff& \forall x \in G, xx^{-1} \in H \\
    &\iff& \forall x \in G, x \sim x
    \end{eqnarray}
}

対称律

 {\displaystyle 
\begin{eqnarray}
&& x \sim y \\
&\iff& xy^{-1} \in H \\
&\iff& yx^{-1} \in H \tag{Hの群の公理Ⅱ:逆元の存在} \\
&\iff& y \sim x
\end{eqnarray}
}

推移律

 {\displaystyle 
\begin{eqnarray}
&&x \sim y \;\wedge \;y \sim z \\
&\iff& xy^{-1} \in H \;\wedge\; yz^{-1} \in H \\
&\implies& (xy^{-1})(yz^{-1}) \in H \\
&\iff& x(y^{-1}y)z^{-1} \in H \tag{Hの群の公理Ⅲ:結合法則}\\
&\iff& xz^{-1} \in H \\
&\iff& x \sim z
\end{eqnarray}
}

本編まとめ
  • 以上から、 \simは同値関係であることがわかり、同値関係の公理がそれぞれ群の公理から導かれることがわかりました。

まとめ

 Gの部分群 Hを用いて、 {\displaystyle a \sim b \stackrel{{\rm def}}{\iff} ab^{-1} \in H}として定められる関係を考えると、 \simが同値関係であることは、それぞれ次のように対応する群の公理から導かれました。
 {\displaystyle
\begin{eqnarray}&群の公理&Ⅰ&:&単位元の存在 &\implies& &同値関係の公理&Ⅰ&:&反射律\\&群の公理&Ⅱ&:&逆元の存在 &\implies& &同値関係の公理&Ⅱ&:&対称律\\&群の公理&Ⅲ&:&結合法則 &\implies& &同値関係の公理&Ⅲ&:&推移律\\\end{eqnarray}
}


おわりに

いかがでしたでしょうか。それぞれの公理で、一対一に対応が取れるのが面白いですね。

明日の記事は、Szkieletorさんの、Brainf*ckで九九表に載っているか判定するプログラム - モモをたずねてです。ぜひお読みください。

遺伝的アルゴリズムでゲームAIを作ろう

概要

東京大学理学部情報科学科の2019年アドベントカレンダー、15日目の記事です。

遺伝的アルゴリズムでゲームAIを作りました。プログラムを実行すると、AIが進化する様を見られます。

はじめに

本記事について

こんにちは。KazukiOtaです。

本記事では、遺伝的アルゴリズムという手法を用いて、恐怖の30というゲームをプレイする人工知能の実装方法をお伝えします。

読者について

本記事は、「ゲームAIを作ってみたいけど、どうすればいいのかわからない」という読者を想定しています。

たとえば、遺伝的アルゴリズムと聞くと、スーパーマリオブラザーズを学習させてみた(1-1) niconico動画を思い出す人もいるかもしれません。動画を見たことはあるけど、自分の手でゲームAIを実装したことはない、という人も多いかもしれません。本記事では、そのような、「興味はあるけど実装したことがない」という人を対象に、実装の仕方を解説します。

本記事の構成

第1節 恐怖の30では、本記事で扱うゲームについて、ルールや基本的な戦術を解説します。

第2節 遺伝的アルゴリズム では、遺伝的アルゴリズムとはどういう手法なのかを、概念的に説明します。

第3節 実装編 では、遺伝的アルゴリズムを用いて、恐怖の30をプレイするAIを作ってみます。

第1節 恐怖の30

f:id:kazukiota:20191216010408p:plain

1.1 この節で学ぶこと

この節では、恐怖の30のルールを学びます。

また、基本的な戦術を知り、必勝法があることを学びます。

1.2 ルール

恐怖の30とは、2人で行うゲームです。

数字を順番に言い合っていき、1ターンに少なくとも1つ、最大3つ言うことができます。

30を言ったら負け、というシンプルなルールのゲームです。

例えば、つぎのように進行します。

先手「1, 2, 3」

後手「4, 5, 6」

先手「7, 8」

後手「9, 10, 11」

先手「13, 14, 15」

後手「16」

先手「17, 18, 19」

後手「20, 21, 22」

先手「23, 24, 25」

後手「26, 27」

先手「28, 29」

後手「30」

この場合、後手の負け、先手の勝ちです。

1.3 必勝法

f:id:kazukiota:20191216010433p:plain
「このゲームには、必勝法がある...!」

この恐怖の30には、先手が絶対に勝てる必勝法があります。それは、

最後に言う数字を「1, 5, 9, 13, 17, 21, 25, 29」のどれかにする

という方法です。

これがなぜ必勝法になるのかを解説します。

まず、29を言えれば、相手に30を言わせられるので、勝利します。つまり、恐怖の30は「29を言ったら勝ちゲーム」であると言えます。

次に、25を言えれば、絶対に次の自分の手番で29を言えます。相手が1つ言ってきたら3つ、2つ言ってきたら2つ、3つ言ってきたら1つ言えばいいからです。つまり、恐怖の30は「25を言ったら勝ちゲーム」であると言えます。

同様にして、恐怖の30は「21を言ったら勝ちゲーム」であり、「17を言ったら勝ちゲーム」であり、...、「1を言ったら勝ちゲーム」です。

先手は、最初のターンに「1」と言うことができます。

以上のように、恐怖の30は先手に必勝法があり、その方法は、

最後に言う数字を「1, 5, 9, 13, 17, 21, 25, 29」のどれかにする

すなわち、

最後に言う数字をnを整数として、4n+1と表せる整数にする

という方法なのです。

1.4 この節で学んだこと

この節では、恐怖の30というゲームのルールを学びました。

また、恐怖の30は先手必勝であり、

最後に言う数字をnを整数として、4n+1と表せる整数にする

と言う方法が必勝法であることを学びました。

1.5 演習問題

  • 同様に恐怖の31というゲームを考えた時、これが先手必勝であることを示せ。
  • 同様に恐怖の29というゲームを考えた時、これが後手必勝であることを示せ。
  • 恐怖の30を3人でプレイした場合、どのプレイヤーにも必勝法がないこと、すなわち2人で協力すれば残りのプレイヤーを負かせることを示せ。

2. 遺伝的アルゴリズム

2.1 遺伝的アルゴリズムとは

遺伝的アルゴリズムはデータ(解の候補)を遺伝子で表現した「個体」を複数用意し、適応度の高い個体を優先的に選択して交叉・突然変異などの操作を繰り返しながら解を探索する。適応度は適応度関数によって与えられる。

Wikipediaより引用)

本記事では、ゲームのAIを遺伝子として表現し、お互いに対戦させ、その勝率の高いものほど評価値が高いとします。

2.2 本記事での遺伝子

本記事では、遺伝子は長さ32の小数のリストとして表現されます。

それぞれの小数は評価値を表します。リストの1番目の要素は自分の番を1で終わらせることの評価値、リストの29番目の要素は自分の番を29で終わらせることの評価値を表します。

3. 実装編

3.1 この節で学ぶこと

恐怖の30を攻略するAIを、遺伝的アルゴリズムによって作ります。

3.2 全体の構成

まずは、プログラムの全体を眺めてみましょう。

これがプログラムの全文です。108行からなります。

今全部読もうとする必要はありません。ざっと眺めてもらえればそれで大丈夫です。

from numpy import argmax
from numpy.random import random
from matplotlib.pyplot import plot

def whiteWin(white_gene, black_gene):
    # 恐怖の30を行う。
    # 先手(white)の遺伝子と後手(black)の遺伝子を受け取り、対戦させ、先手が勝つならTrue, 後手が勝つならFalseを返す。
    turn = 0
    number = 0
    while True: 
        if turn % 2 == 0:
            choice = 1+argmax(white_gene[number:number+3])
        else:
            choice = 1+argmax(black_gene[number:number+3])
        number = number + choice
        if number >= 30:
            if turn % 2 == 0:
                return False
            else:
                return True
        turn = turn + 1

def leagueMatch(genes):
    # 長さ20, 要素が全て0のリストを作成。
    victories = []
    for i in range(20):
        victories.append(0)

    # 総当たりで対戦し、勝利数を計算。
    for i in range(20):
        for j in range(20):
            if whiteWin(genes[i], genes[j]):
                victories[i] = victories[i] + 1
            else:
                victories[j] = victories[j] + 1
    return victories

def roulette(victories):
    # ルーレット選択を行う。
    summention = sum(victories) #sum
    value = summention*random() #random
    i = 0
    while True:
        if sum(victories[:i+1]) > value: #スライス表記
            return i
        i = i + 1

def randomGene():
    # 新規ランダム遺伝子の生成
    gene = []
    for j in range(32):
        gene.append(random())
    return gene

def nextGeneration(genes, victories):
    # 前の世代の遺伝子と、各遺伝子の成績を受け取って、次の世代を生成する。
    new_genes = []

    # 最高成績者 1名
    for i in range(1):
        index = argmax(victories)
        new_genes.append(genes[index])

    # ルーレット選択 4名
    for i in range(4):
        index = roulette(victories)
        new_genes.append(genes[index])

    # 交叉 10名
    for i in range(10):
        father = genes[roulette(victories)]
        mother = genes[roulette(victories)]
        child = []
        for j in range(32):
            if random() < 0.5:
                child.append(father[j])
            else:
                child.append(mother[j])
        new_genes.append(child)

    # 新規ランダム遺伝子 5名
    for i in range(5):
        new_genes.append(randomGene())

    return new_genes

def printGene(gene):
    # リストを受け取って、要素の大きさを*の数で表現。
    length = 100
    for j in range(32):
        star = int(length*gene[j])
        print(j+1, "\t",  "*"*star+" "*(length-star), "\t", j+1)

def main():
    # 新規ランダム遺伝子を20名作成。
    genes = []
    for i in range(20):
        genes.append(randomGene())

    # 200世代進化させる。
    for k in range(201):
        victories = leagueMatch(genes)
        genes = nextGeneration(genes, victories)

        # 50世代ごとに、もっとも成績の良い遺伝子を表示する。
        if k%50==0:
            print("第", k, "世代")
            printGene(genes[argmax(victories)])
            print()

main()

このプログラムは、基本的には関数の組み合わせで動いています。

それぞれの関数は、次のように役割を分担しています。

  • whiteWin: 2つの遺伝子を受け取って恐怖の30を対戦させ、勝者を決めます。
  • leagueMatch: 20の遺伝子を受け取って、総当たり戦を行い、勝利数のリストを返します。
  • roulette: ルーレット選択をします。
  • randomGene: 新規ランダム遺伝子を生成します。
  • nextGeneration: 現在の遺伝子のリストと勝利数のリストを元に、新しい世代を生成します。
  • printGene: 遺伝子を可視化します。
  • main: 遺伝的アルゴリズムを200世代実行し、50世代ごとにもっとも戦績の良い遺伝子を表示します。

関数は、以下のような依存関係になっています。

f:id:kazukiota:20191216010503p:plain

3.3 遺伝子の表現

このプログラムでは、遺伝子は長さ32の小数のリストとして表現されます。

それぞれの小数は評価値を表します。リストの1番目の要素は自分の番を1で終わらせることの評価値、リストの29番目の要素は自分の番を29で終わらせることの評価値を表します。

3.4 個々の説明

個々のプログラムについて説明します。

急いでいる方は先に進み、この節は参照用としても構いません。

ライブラリの使用

from numpy import argmax
from numpy.random import random

上記の2つの関数をimportしています。

argmaxはリストの最大元のindexを返す関数です。

randomは0~1の一様乱数を返す関数です。

whiteWin

def whiteWin(white_gene, black_gene):
    # 恐怖の30を行う。
    # 先手(white)の遺伝子と後手(black)の遺伝子を受け取り、対戦させ、先手が勝つならTrue, 後手が勝つならFalseを返す。
    turn = 0
    number = 0
    while True: 
        if turn % 2 == 0:
            choice = 1+argmax(white_gene[number:number+3])
        else:
            choice = 1+argmax(black_gene[number:number+3])
        number = number + choice
        if number >= 30:
            if turn % 2 == 0:
                return False
            else:
                return True
        turn = turn + 1

whiteWin関数は、恐怖の30を行います。

choice = 1+argmax(white_gene[number:number+3]) は、white_gene[number], white_gene[number+1], white_gene[number+2]の中でどれが最大なのかを求め、それぞれの場合についてchoiceの値を1, 2, 3に対応させます。

leagueMatch

def leagueMatch(genes):
    # 長さ20, 要素が全て0のリストを作成。
    victories = []
    for i in range(20):
        victories.append(0)

    # 総当たりで対戦し、勝利数を計算。
    for i in range(20):
        for j in range(20):
            if whiteWin(genes[i], genes[j]):
                victories[i] = victories[i] + 1
            else:
                victories[j] = victories[j] + 1
    return victories

leagueMatch関数は、whiteWin関数を利用して、総当たり戦を行います。

roulette

roulette関数は、それぞれの評価値を元に、ルーレット選択を行います。

def roulette(victories):
    # ルーレット選択を行う。
    summention = sum(victories) #sum
    value = summention*random() #random
    i = 0
    while True:
        if sum(victories[:i+1]) > value: #スライス表記
            return i
        i = i + 1

randomGene

randomGene関数は、新しいランダム遺伝子を生成します。

def randomGene():
    # 新規ランダム遺伝子の生成
    gene = []
    for j in range(32):
        gene.append(random())
    return gene

nextGeneration

nextGeneration関数は、現在の遺伝子のリストと勝利数のリストを元に、新しい世代を生成します。

def nextGeneration(genes, victories):
    # 前の世代の遺伝子と、各遺伝子の成績を受け取って、次の世代を生成する。
    new_genes = []

    # 最高成績者 1名
    for i in range(1):
        index = argmax(victories)
        new_genes.append(genes[index])

    # ルーレット選択 4名
    for i in range(4):
        index = roulette(victories)
        new_genes.append(genes[index])

    # 交叉 10名
    for i in range(10):
        father = genes[roulette(victories)]
        mother = genes[roulette(victories)]
        child = []
        for j in range(32):
            if random() < 0.5:
                child.append(father[j])
            else:
                child.append(mother[j])
        new_genes.append(child)

    # 新規ランダム遺伝子 5名
    for i in range(5):
        new_genes.append(randomGene())

    return new_genes

printGene

printGene関数は、遺伝子を可視化します。

def printGene(gene):
    # リストを受け取って、要素の大きさを*の数で表現。
    length = 100
    for j in range(32):
        star = int(length*gene[j])
        print(j+1, "\t",  "*"*star+" "*(length-star), "\t", j+1)

main

main関数は、遺伝的アルゴリズムを200世代実行し、50世代ごとにもっとも戦績の良い遺伝子を表示します。

def main():
    # 新規ランダム遺伝子を20名作成。
    genes = []
    for i in range(20):
        genes.append(randomGene())

    # 200世代進化させる。
    for k in range(201):
        victories = leagueMatch(genes)
        genes = nextGeneration(genes, victories)

        # 50世代ごとに、もっとも成績の良い遺伝子を表示する。
        if k%50==0:
            print("第", k, "世代")
            printGene(genes[argmax(victories)])
            print()

3.5 出力

次のような出力を得ると思います。

f:id:kazukiota:20191216010523p:plain

注目して欲しいのは、1, 5, 9, 13, 17, 21, 25, 29が、他の近傍の数字よりも大きくなっていることです。

これは、1.3節で学んだ必勝法を、AIが習得していることを意味します。

4 まとめ

いかがでしたでしょうか。

若干尻切れな感じになってしまいましたが、楽しんでいただけたなら幸いです。