イントロ
AI、何かと流行ってますよね。でもなんか「え？あれ？その「AI」って呼んでるもの、数年前はビッグデータ解析とか言ってもてはやしてなかったっけ…？ビッグデータ解析だけがAIなの…？」ってことありません…？
将棋やチェスのAIが人間より強くなってしまったのは皆さんご存じかと思います。将棋やチェスの対戦相手がAIなら、対戦ゲームの一人用モードの対戦相手（よく「CPU」と呼ばれがちな奴）って、AIじゃない…？ファミコンにもAIあったんじゃない…？
というわけで、タイトルでちょっと釣りましたが、「ファミコンレベルでいいから対戦相手を作って遊ぼう」という話になります。
厳密には人工知能って呼んでもらえないかもしれないけど…。
Wikipedia:コンピュータゲームにおける人工知能
ま、「広義の」、「広義のAI」の話です。
昔話
個人的な昔話になりますが、仕事でネットがつながらない場所でただひたすら待機させられていたことがあり、あまりにも暇すぎるのでそのときPCに入っていたVisual Basicでリバーシを作って一人で遊んでいたんですね。
一人で白黒やっても面白くないので、対戦相手（今回作ろうとしてるAIです）を作って遊びはじめ、次第にAI同士で戦わせ始めたということがありました。
その時の再現みたいな話になります。
※ネットのない環境でひたすら待機していた精神状態によって発生した与太話を多めに含みます
リバーシを作る
というわけで、まずはリバーシを作っていきましょう。本題ではないのでサクッといきます。
処理の流れは
- 盤面の初期化
- 石を置く
- 裏返す
- 終了判定
- 手番変更
- 2に戻る
- 終了したら結果表示
ざっくりこんな感じですね。
Intの2次元配列で盤面を管理して、「-1」は置かれていないマス、0と1は黒と白ということにします。
裏返せる場所にしか置けないことと、置ける場所がない場合は強制的にパスになるルールがあるので、置ける場所のリストを保持しておきます。
また、盤面サイズの変更が容易なように盤面の半分のサイズを定数にしています（幅が奇数の場合どう初期化していいかわからないため、偶数サイズにしたい）
他に特筆すべきこともないのでテキトーにメインだけ貼ってしまいます。
令和の今、新しいプログラミング言語を使って昭和みたいなゲームを作っていくぞ！！
const val widthHalf = 4
var blackWin = 0
var whiteWin = 0
fun main() {
println("回数？") // 一度に1000回くらい対戦してもらって、結果を学習させる予定
val n = readLine()!!.toInt()
val player1: Player = HumanPlayer()
val player2: Player = HumanPlayer()
for (i in 0 until n) {
val board = Array(widthHalf * 2) { IntArray(widthHalf * 2) { -1 } }
val puttablePlace = mutableSetOf<Pair<Int, Int>>()
var turn = 0
init(board) // 中央付近に黒と白の石を置く
puttableCheck(board, turn, puttablePlace) // 置ける場所のリストを作る
while (puttablePlace.isNotEmpty()) {
val newStone = put(
board, turn, puttablePlace,
if (turn == 0) player1 else player2
) // 次の手の入力
reverse(board, newStone, turn) // 裏返し
turn = turnChange(turn) // 手番の変更
puttableCheck(board, turn, puttablePlace) // 置ける場所のチェック
if (puttablePlace.isEmpty()) {
turn = turnChange(turn) // 置ける場所がなかったらパス
puttableCheck(board, turn, puttablePlace)
}
}
result(board) // 両者ともに置けなくなったら終了して結果表示
player1.finish(board, 0) // 結果を学習させるための部分
player2.finish(board, 1)
}
player1.close() // 学習結果の記録
player2.close()
println("${n}回戦の結果 $dispBlack:$blackWin 勝 $dispWhite:$whiteWin 勝") // 最終結果表示
}
interface Player {
fun play(board: Array<IntArray>, turn: Int):Pair<Int, Int>
fun finish(board: Array<IntArray>, turn: Int) { }
fun close() { }
}
Playerインターフェイスを実装して、手を考える処理を作ります。
class HumanPlayer: Player {
override fun play(board: Array<IntArray>, turn: Int, puttablePlace: Set<Pair<Int, Int>>):Pair<Int, Int> {
display(board)
println("${if(turn == 0) dispBlack else dispWhite} の番です。")
val input = readLine()!!.split(" ").map { it.toInt() }
return input[0] to input[1]
}
}
リバーシができることの確認のため、あるいは一人遊びのために標準入力から受け付けるプレイヤーです。
また、盤面の表示などは人間用の機能なので、メインに置かずここに書いています。
人工無能を作る
賢いものを作るのは難しいのでまずは「置けるマスをランダムに選んで置く」ということをやってもらいます。
class RandomPlayer: Player {
override fun play(board: Array<IntArray>, turn: Int):Pair<Int, Int> {
val puttablePlace = mutableSetOf<Pair<Int, Int>>()
puttableCheck(board, turn, puttablePlace)
return puttablePlace.toTypedArray()[(0 until puttablePlace.size).random()]
}
}
とりあえずこれを相手に学習させてみましょう。
学習するイマドキっぽいAIを作る
というわけで本題です。あまり複雑なことは考えずに
- 盤面の状態、どこに打ったか、最終的に獲得した石の数
- 経験済みの盤面に対して同じ手を打った場合、最終成績を累計していく
- 勝ちの場合は石の数をプラス、負けの場合はマイナス
こんな感じの記録積み重ねさせて、
- 初めて見る盤面の場合はランダムに選ぶ
- 経験済みの盤面の場合は成績が良かった手を選ぶ
- 成績1位が複数の場合もランダムに選ぶ
ができれば良いかもしれない。
この学習のさせ方だと「先手専門」「後手専門」になってしまいますが、ランダム同士の対決だと後手の勝率が65%くらいになったので「先手専門」で学習させて勝率50%くらいを目指したいと思います。
class StudyPlayer: Player {
private val history: MutableMap<String, MutableMap<Pair<Int, Int>, Int>> = mutableMapOf()
private val selected: MutableSet<Pair<String, Pair<Int, Int>>> = mutableSetOf()
override fun play(board: Array<IntArray>, turn: Int):Pair<Int, Int> {
val puttablePlace = mutableSetOf<Pair<Int, Int>>()
puttableCheck(board, turn, puttablePlace)
val (state, ptn) = boardToString(board)
return if(history[state] != null) { // 既知の盤面の場合
val historyForBoard = history[state]!!
val maxScore = historyForBoard.values.maxOrNull() // 成績が良い手を選ぶ
val maxHistories = historyForBoard.filter { it.value == maxScore }.map{ it.key }
val pos = maxHistories[(maxHistories.indices).random()]
selected.add(state to pos)
posRotateReverse(board.size, pos, ptn)
} else { // 未知の盤面の場合
// 学習記録用データを作る
val puttablePlaceArray = puttablePlace.toTypedArray()
if (state.replace(" ", "").length < 20) {
val newHistory = mutableMapOf<Pair<Int, Int>, Int>()
puttablePlaceArray.forEach {
newHistory[posRotate(board.size, it, ptn)] = 0
}
history[state] = newHistory
}
val pos = puttablePlaceArray[(0 until puttablePlace.size).random()] // ランダムで選ぶ
selected.add(state to posRotate(board.size, pos, ptn))
pos
}
}
}
学習記録のの入出力とかは省略。historyが読み込んだ学習記録で、selectedが今回打った手。historyとselectedをマージして試合終了時に学習ファイルに出力します。
また、リバーシの盤面の状態は、左右反転・上下反転・90度回転・180度回転・270度回転・対角線で反転（2つ）した7つの状態と等価であると言えます。状態の記憶をする時は、これら等価の状態の辞書順最小にまとめて行うことにします。
1回学習させた結果がこちら。
一行は盤面の情報.打てる位置X_打てる位置Y_成績,打てる位置X_打てる位置Y_成績,… という感じになっています。
10 01 .2_2_0,2_3_0,2_4_0,2_5_0,3_2_0,3_5_34,4_2_0,4_5_0,5_2_0,5_3_0,5_4_0,5_5_0,
1100 01 .2_1_0,2_2_0,2_3_0,2_4_34,2_5_0,2_6_0,3_1_0,3_6_0,4_1_0,4_2_0,4_5_0,4_6_0,5_2_0,5_3_0,5_4_0,5_5_0,
1 1 1100 01 .0_2_0,0_3_0,0_4_0,1_2_0,1_4_0,1_5_0,2_1_0,2_2_0,2_3_0,2_5_0,2_6_0,3_1_0,3_6_0,4_1_0,4_2_0,4_5_0,4_6_0,5_2_0,5_3_34,5_4_0,5_5_0,
11 1 1100 00 0 .0_1_0,0_2_0,0_3_0,0_4_0,1_1_0,1_4_0,1_5_0,2_1_0,2_2_0,2_3_0,2_5_0,2_6_0,3_1_0,3_6_0,4_1_0,4_2_34,4_5_0,4_6_0,5_2_0,5_4_0,5_5_0,6_2_0,6_3_0,6_4_0,
1 11 1 1000 000 0 .0_1_0,0_3_0,0_4_0,1_1_0,1_4_0,1_5_0,2_1_0,2_2_0,2_3_0,2_5_0,2_6_0,3_1_34,3_6_0,4_1_0,4_5_0,4_6_0,5_1_0,5_2_0,5_4_0,5_5_0,6_2_0,6_3_0,6_4_0,
1 11 1 1 00001 001 0 .0_1_34,0_3_0,0_4_0,1_1_0,1_4_0,1_5_0,1_6_0,1_7_0,2_0_0,2_1_0,2_2_0,2_3_0,2_5_0,2_7_0,3_0_0,3_6_0,3_7_0,4_0_0,4_1_0,4_5_0,4_6_0,5_1_0,5_2_0,5_4_0,5_5_0,6_2_0,6_3_0,6_4_0,
01 11 1 1 1 10001 101 0 .0_0_0,0_3_0,0_4_0,1_0_0,1_1_0,1_4_0,1_5_0,1_6_0,1_7_0,2_1_34,2_2_0,2_3_0,2_5_0,2_7_0,3_0_0,3_6_0,3_7_0,4_0_0,4_1_0,4_5_0,4_6_0,5_1_0,5_2_0,5_4_0,5_5_0,6_2_0,6_3_0,6_4_0,
01 11 10 1 1 10001 1101 0 .0_0_0,0_3_0,0_4_0,1_0_0,1_1_0,1_4_34,1_5_0,1_6_0,1_7_0,2_2_0,2_3_0,2_5_0,2_7_0,3_0_0,3_6_0,3_7_0,4_0_0,4_5_0,4_6_0,5_0_0,5_1_0,5_2_0,5_4_0,5_5_0,6_2_0,6_3_0,6_4_0,
011 100 10 0 1 10001 1101 0 .0_0_0,0_4_0,0_5_0,1_0_0,1_1_0,1_5_0,1_6_0,1_7_0,2_2_0,2_3_0,2_5_0,2_7_0,3_0_0,3_6_0,3_7_0,4_0_0,4_5_0,4_6_0,5_0_34,5_1_0,5_2_0,5_4_0,5_5_0,6_2_0,6_3_0,6_4_0,
011 100 10 0 1 10001 0101 0 1 1 .0_0_0,0_4_0,0_5_0,1_0_0,1_1_0,1_5_0,1_6_0,1_7_0,2_2_0,2_3_0,2_5_0,2_7_0,3_0_0,3_6_0,3_7_0,4_0_34,4_5_0,4_6_0,5_1_0,5_2_0,5_4_0,5_5_0,6_0_0,6_1_0,6_3_0,6_4_0,7_1_0,7_2_0,7_3_0,
011 100 11 0 1 110001 10101 0 1 1 .0_0_0,0_4_0,0_5_0,1_0_0,1_1_0,1_5_0,1_6_0,1_7_0,2_2_0,2_3_0,2_5_34,2_7_0,3_6_0,3_7_0,4_5_0,4_6_0,5_1_0,5_2_0,5_4_0,5_5_0,6_0_0,6_1_0,6_3_0,6_4_0,7_1_0,7_2_0,7_3_0,
1111 100 11 001 110001 10101 0 1 1 .0_4_0,0_5_0,1_0_0,1_1_0,1_5_0,1_6_0,1_7_0,2_2_0,2_3_0,2_7_0,3_6_0,3_7_0,4_5_0,4_6_0,5_1_0,5_2_0,5_4_34,5_5_0,6_0_0,6_1_0,6_3_0,6_4_0,7_1_0,7_2_0,7_3_0,
1111 100 11 001 110001 10100 0 10 1 1 .0_4_0,0_5_0,1_0_0,1_1_0,1_5_0,1_6_0,1_7_0,2_2_0,2_3_0,2_7_0,3_6_0,3_7_0,4_5_0,4_6_0,5_1_0,5_2_0,5_5_34,6_0_0,6_1_0,6_3_0,6_4_0,6_5_0,7_1_0,7_2_0,7_4_0,
1111 100 11 001 110001 10100 1 100 1 1 1 .0_4_0,0_5_0,1_0_0,1_1_0,1_5_0,1_6_0,1_7_0,2_2_0,2_3_0,2_7_0,3_6_0,3_7_0,4_5_34,4_6_0,5_1_0,5_2_0,5_6_0,6_1_0,6_3_0,6_4_0,6_5_0,6_6_0,7_0_0,7_1_0,7_2_0,7_4_0,
1111 100 11 001 111001 101101 1 111 1 1 1 1 .0_4_0,0_5_0,1_0_0,1_1_0,1_5_0,1_6_0,1_7_0,2_2_0,2_3_0,2_7_0,3_6_34,3_7_0,4_6_0,5_1_0,5_2_0,5_6_0,6_1_0,6_3_0,6_4_0,6_6_0,7_0_0,7_1_0,7_2_0,7_4_0,7_5_0,7_6_0,
1111 1 100 11 001 1110000 101100 1 111 1 1 1 1 .0_4_0,0_5_0,1_1_0,1_5_0,1_6_0,1_7_0,2_2_0,2_3_34,2_7_0,3_7_0,4_6_0,4_7_0,5_1_0,5_2_0,5_6_0,6_1_0,6_3_0,6_4_0,6_6_0,7_0_0,7_1_0,7_2_0,7_4_0,7_5_0,7_6_0,
1111 1 000 11 0001 1100000 101100 1 111 1 1 11 1 .0_4_0,0_5_0,1_1_0,1_5_0,1_6_0,1_7_0,2_2_0,2_7_0,3_7_0,4_6_0,4_7_0,5_1_0,5_2_0,5_6_0,5_7_0,6_1_0,6_3_34,6_4_0,6_7_0,7_0_0,7_1_0,7_2_0,7_4_0,7_5_0,7_6_0,7_7_0,
1111 1 010 11 0101 1100011 1011111 1 001 1 10 11 1 .0_4_0,0_5_0,1_1_0,1_5_0,1_6_0,1_7_0,2_2_0,2_7_0,3_7_0,4_7_0,5_1_0,5_2_0,5_6_0,5_7_0,6_1_0,6_4_0,6_7_0,7_0_0,7_1_0,7_2_0,7_4_0,7_5_0,7_6_34,7_7_0,
1111 1 010 11 0101 1100011 1011111 1 001 1 10 01 1 01.0_4_0,0_5_0,1_1_0,1_5_0,1_6_34,1_7_0,2_2_0,2_7_0,3_7_0,4_7_0,5_1_0,5_2_0,5_6_0,5_7_0,6_1_0,6_4_0,6_7_0,7_0_0,7_1_0,7_2_0,7_4_0,7_5_0,
1111 1 010 0 11 011111100011 1011111 1 001 1 10 01 1 01.0_4_0,0_5_0,0_6_0,0_7_0,1_1_0,1_5_0,1_7_0,2_2_0,3_7_0,4_7_0,5_1_0,5_2_0,5_6_0,5_7_0,6_1_0,6_4_0,6_7_0,7_0_0,7_1_34,7_2_0,7_4_0,7_5_0,
1111 1 010 0 11 011111100011 1011111 1 0011 1 00 01 0 1 01.0_4_0,0_5_0,0_6_0,0_7_0,1_1_0,1_5_34,1_7_0,2_2_0,3_7_0,4_7_0,5_1_0,5_2_0,5_7_0,6_1_0,6_4_0,6_7_0,7_0_0,7_2_0,7_4_0,7_5_0,
1111 1 01000 11 00011110000111011101 1 0001 1 00 01 0 1 01.0_4_34,0_5_0,0_6_0,0_7_0,1_1_0,1_7_0,2_2_0,4_7_0,5_1_0,5_2_0,5_7_0,6_1_0,6_4_0,6_7_0,7_0_0,7_2_0,7_4_0,7_5_0,
10000 1 01000 11 00011110000111011101 1 000111 00 01 0 1 01.0_5_0,0_6_0,0_7_0,1_1_0,1_7_0,2_2_0,4_7_0,5_1_0,5_2_0,6_1_0,6_4_0,6_7_0,7_0_0,7_2_34,7_4_0,7_5_0,
10000 1 01111111 00011110000111011101 1 000111 00 01 001 01.0_5_0,0_6_0,0_7_0,1_1_0,2_2_0,4_7_0,5_1_0,5_2_0,6_1_0,6_4_0,6_7_0,7_0_0,7_4_0,7_5_34,
10000 1 01111111 00011110000111111101 11 000111 10 00 001 001.0_5_0,0_6_0,0_7_0,1_1_34,2_2_0,4_7_0,5_2_0,6_1_0,6_4_0,6_7_0,7_0_0,7_4_0,
10000 1001111110 00011100000111011101 11 000111 10 10 0011111.0_5_0,0_6_0,0_7_0,2_2_0,4_7_0,5_2_0,6_1_0,6_4_34,6_7_0,7_0_0,
10000 1001111110 00011100000111111101 111111111 11000 0011111.0_5_0,0_6_0,0_7_0,2_2_34,4_7_0,6_1_0,6_7_0,7_0_0,
10000 1000111110000011100000111111101 111111111 111111 0011111.0_5_34,0_6_0,0_7_0,4_7_0,6_1_0,7_0_0,
100000 1000000110000011100000111111101 1111111111111111 0011111.0_6_0,0_7_0,4_7_34,7_0_0,
1111111 100001111000101010010000111110001111110011111010 0011111.0_7_0,7_0_34,
学習の方針について
5000回ほど学習させてみた結果、7手目以降の「既知の局面」というのがほとんど出てこなくなったのが学習データからわかりました。「既知の局面の勝率の高い手を選ぶ」という方式では、後半戦のデータは役に立たないことになります（何億回も回す場合は別として）。
というわけで、石の数が10個未満の局面だけ記録して、「序盤戦でいい感じにしてそのまま勝てないか」という戦法を取ることにします。Wikipediaにも、序盤戦でアドバンテージ作れそうなことが書いてありますし。
Wikipedia:コンピュータオセロ
で、2万回ほど学習させてみましたが、後手ランダムの勝率65%のまま変化せず…
1000回戦の結果 x:315 勝 o:633 勝
4*4でやってみる
88では無理そうなので、盤面を縮小して44で再挑戦します。4*4のランダム同士の対戦成績はこんな感じです。
1000回戦の結果 x:146 勝 o:701 勝
学習データの作り方は8*8の時ののままにして勝率を上げるのを目指します。
4*4で後手を10万回ほど学習させた結果
1000回戦の結果 x:22 勝 o:818 勝
44で後手の場合、学習回数2万回あたりで勝率8割前後に達して、そこから10万回まで増やしてもあまり変化が見られませんでした。
ランダム同士の対決で勝率7割だった（また、88の盤では勝率が全く変化しなかった）ことを考えると健闘できてるんじゃないかと思います。
試しにこれを相手に先手人間で3戦してみましょう
3回戦の結果 x:2 勝 o:1 勝
真面目にやって1敗したのと、そもそも後手有利だとしても「ちゃんと学習した」っぽい雰囲気を感じることができました。
4*4で先手を10万回ほど学習させてみた結果
1000回戦の結果 x:524 勝 o:438 勝
ランダム同士の勝率を考えるとこれはかなりいい感じの結果が出たんじゃないでしょうか。
試しにこれを相手に後手人間で3戦してみましょう
3回戦の結果 x:0 勝 o:3 勝
強いと思い込んでる同じ手しか打ってこないから弱すぎる…
まとめ
88の盤面では取りうる状態数が多すぎるため、学習によってうまく結果が出ませんでしたが、44の場合は目に見える変化があったと思います。
ただ、学習のさせ方が悪いんでしょう。一度強いと思い込んだらその思い込みが抜けないように学習させてしまったのは失敗でした。やっぱり機械学習についてちゃんと勉強しないとダメですね（あたりまえ）。
まあ、こうやって学習させた相手とリバーシで暇つぶしできなくても、学習させること自体で暇がつぶれるので、ネット環境がないところに放り込まれても安心ですね。