見出し画像

オセロAIの教科書 1 概観

にゃにゃん(山名琢翔)

こんにちは、にゃにゃんです。

この記事は私が所属する筑波大学理工学群工学システム学類のアドカレ、esys Advent Calendar 2021の3日目の記事です。

この記事集「オセロAIの教科書」は私の世界1位AIの技術を中心に、オセロAI(オセロの相手をしてくれるプログラム)を初歩から段階を踏んで作っていく記事集です。全編無料でこちらから読めます。

この記事について、わかりにくい点や疑問点、おかしな点がありましたら気楽にコメントとかTwitterとかで教えて下さい。みなさんの力で記事を洗練したいです。


自己紹介

名前をにゃにゃんと言います。本名から派生したあだ名を変形したものです。

人生初の本格的なゲームAIとしてオセロAIを制作し、制作開始から半年くらいかけて世界1位になりました。

私が世界1位になったオセロAIのコンテストサイトはこちらです。

コンテスト優勝後も改良を重ね、現在はパソコン向けのアプリとして、またスマホからでもWebブラウザで遊べるWebアプリとして、オセロAIを公開しています。

ちなみに世界1位AIのコードを流用して3時間で最弱オセロAIも作りました。

余談ですが、私自身はオセロAI制作をきっかけにして人力でもオセロを打つようになりました。ですので、オセロAIを作る上で作者が人力オセロに強い必要は全くありません。ただ私自身の経験では、作者がオセロに強くなることは、AIの変な挙動を見つけやすくなったりと、少し良いこともあると感じています。もし人力オセロに興味が湧いてきたら、そちらもぜひやってみましょう。オセロを機械と人力で遊び尽くしましょう。


この記事集の読み方

この記事集は最初から順番に読む必要は全くありません。ある程度順番に読むと良いようにしましたが、途中で詰まってもとりあえず先に進んだり、別の記事を読んだり、自由に使ってください。

なお、この記事で解説するように、オセロAIは主に3つの技術で構成されています。各記事の題名には、その記事がどの技術について解説しているかわかりやすく書いていますので、必要なところだけつまみ食いしてください。

この記事集の終盤は、読むのにある程度プログラミングの知識が必要になります。わからない場合は適宜調べつつお読みください。ただ、なるべく読みやすくなるよう心がけて書いたつもりです。

この記事では、アルゴリズムなどの考え方に重点を置いて解説します。これは、実装について細かく解説すると記事が冗長になってしまうのと、サンプルプログラムを公開しているので気になる方は気になる部分だけ読んでくだされば良いという考えによるものです。

オセロAIは、細かな実装を解説するとキリがないので、この記事集では各技術の概観を述べるに留めます。しかし、それだけでは何の役にも立たないので、必要なところを各自で確認できるよう、サンプルプログラムを充実させました。

また、この記事集は完璧ではありません。疑問やわからない点、おかしな点はぜひ報告してください。


サンプルプログラム

この記事集ではサンプルとしてC++によるコードを公開しています。

サンプルプログラムは最終的なプログラムだけではなくて、記事集で踏む段階ごとに別ファイルとして作ってあります。記事の中で適宜参照するので、手元などで実行してみたり、中身を読んでみたりと使い倒してください。

自由度の高いMITライセンスで公開していますので、改変するなり流用するなり、好きに使ってください。


この記事を読むのに必要な知識

この記事を読むのに必要な(ある程度前提とする)知識を列挙します。これらの知識がない状態で読んでもある程度理解できるとは思いますが、途中でわからなくなったらキーワードとして使ってください。

  • オセロのルール


概観

オセロAIは3つの主な技術で構成されています。

定石・探索・評価

順番に見ていきましょう。


定石

定石は序盤の展開をある程度覚えておいて、覚えている盤面に出くわしたら定石として登録された手を打つだけにします。パワープレイではあるのですが、定石に当たれば不利な手を絶対に打たないため、とても有効です。

定石はある程度強い人間がオセロをする場合にも重要になります。私自身も人力でオセロを打つときには暗記した定石をある程度使っています。

この記事集では後半に定石を紹介しますが、定石の理解は比較的簡単なので、先に読んでしまっても良いかもしれません。


探索

探索は、何手か先まで盤面の変化を読むことを言います。人間でもよくやりますね。

オセロに限らず様々なゲームにおいて、考えうる盤面は深く読めば読むほど指数的に増えていきます。ですので、いかにして高速に深くまで読むかが大事になってきます。

探索はオセロAIを作る中で一番アルゴリズムの知識を必要としますので、この記事集では丁寧に単純なところから順番に追っていきます。

少し先取りした余談です。2022年現在では、ゲームAIには最新のPV-MCTSというアルゴリズム(2010年代中盤に囲碁AIのAlphaGoが発展させたアルゴリズム)が広く用いられていますが、この記事では昔からあるminimax探索という系統のアルゴリズムを主に紹介します。これは、私が両方のアルゴリズムを試した結果、オセロAIにはminimax探索が向いていると思ったからです。なお、これは私がそう思っているだけです。


評価

何手か先まで探索を行った後、そこで出くわした盤面がどれくらい自分にとって有利かを判定します。この判定を行う関数を評価関数と言います。

評価関数の精度が限りなく良ければ別に深くまで探索を行う必要はなく、自分が打った後の盤面において評価を行うだけで事足ります。しかし、現実は評価関数をうまく作ることはとても難しく、そのために探索と評価を組み合わせて強いオセロAIを作ります。

この記事集では、まずはとりあえず簡単な評価関数を作ってみて、後半でその弱点を克服する性能の良い評価関数を作ります。


まとめ

このように、オセロAIは定石・探索・評価の3つの技術を総合して作ります。とは言え、いきなりこの全部を考えると大変なので、たくさんのステップに分けてこれらを学んでいきます。

特に紹介した3分野が互いに干渉し合うことはほとんどないので、例えば探索アルゴリズムが途中でわからなくなったからと言って以降の記事が読めなくなるわけではありません。そのような場合は評価や定石に関わるところだけつまみ食いしてくださったら嬉しいです。特に定石は比較的簡単な内容です。


次回予告

次回はオセロAIを作る上で必須なボードの実装方法について解説します。

オセロAIはルールの単純さから、ゲームAI入門にとても良いと思います。この記事が一人にでも役に立てば嬉しいです。


スキと投げ銭で喜びます

noteではログインなしでスキできます！役に立ったぞ、面白かったぞ、という方はぜひハートマークをポチッと押してください！

この記事は全編無料ですが、投げ銭してくれたら私が喜びます。喜ぶだけです。何も見返りはありません。「役に立ったし投げ銭してやっても良いぞ」という方はポチっとしてくださると嬉しいです。


変更履歴

2021/12/03

公開

2022/12/24

内容が古くなってきたので大幅に改変

ここから先は

0字

¥ 100

この記事が気に入ったらサポートをしてみませんか？