人工知能 オセロ。 ゲームの世界にもAIが?ゲームAIの仕組みと勉強方法をチェック!

NHKスペシャル「人工知能」~将棋と囲碁~

人工知能 オセロ

推論と探索が中心の第一次AIブーム時代 第一次AIブーム時代は、推論と探索の研究が中心となっていました。 探索とは、最初に与えられた状態から、目的の状態に至るまでの状態の変化を、場合分けをしながら探し出すことです。 推論とは、与えられた既知の情報をもとに、未知の事柄を推測し、答えを導くことです。 具体的にオセロで考えてみましょう。 最初に与えられた状態が黒で、最終目的の状態が黒が多くなるようにすることですね。 オセロでは、相手を挟める場所にしか打つことができませんので、置く場所というのは限られています。 なので、人間はどこに置いたら自身にとって有利になるかをいろんなパターンを考えています。 ある場所に置いたら相手は何処においてくるだろうかを推測して、最も最適な手を探し出して選びます。 これが、探索と推論となります。 ただ、このように、ルールが決まっている問題にしか当時は解くことができなかったので、 第一次AIブームが終焉することとなりました。 そのため、第一次AIブームが終焉することになったのが、人工知能がトイプロブレムしか解けないということで、 トイプロブレムという言葉が、重要になってきます。

次の

AIの実装/ミニマックス法

人工知能 オセロ

画像クリックで遊べます。 みなさんは勝てましたか? 作り方を解説していきます。 方針 世の中には強いオセロ AI がたくさんあります。 ブラウザ js で動く強豪 AI も既にあります。 参考: 今回はゲーム AI の仕組みを理解することを目的として、以下の方針で作りました。 簡単に実装できる ゲーム AI として最小限のコンポーネントのみを備える• そこそこの強さ 人間初心者に負けないくらい、できれば自分より強くしたい 全体像 ゲーム AI は概ね以下の部品を持っています。 静的評価関数• 探索処理• ビットボード 軽量で高速に処理可能な局面データ構造 静的評価関数は、局面のスコアを計算する関数です。 膨大な回数実行されるため、スコアの正確性と処理の軽量さのトレードオフをうまくとる必要があります。 探索処理は文字通りゲーム木を辿る処理です。 ビットボードはオセロの局面を管理するデータ構造です。 局面をビット列とみなして 1 つか複数の int に押し込んでしまいます。 データサイズが軽くなるだけでなく、局面に対する演算 合法手列挙、着手、白黒反転など をプリミティブなビット演算で行えるようになり、高速処理可能となります。 それぞれの部品について説明します。 静的評価関数 静的評価関数はある局面が自分にとって有利な度合いを表す関数です。 一般に 0 点が形勢互角な状態、プラスなら自分が有利な状態、マイナスなら相手が有利な状態を表すように設計します。 ゲーム AI では一般に静的評価関数をゲーム木の末端に適用します。 つまり、次の 1 手を直接評価するのではなく、探索処理によってあらかじめ決めた深さ n 手先 まで潜り、その局面に対して静的評価関数を適用します。 強豪 AI は静的評価関数のパラメータを膨大な棋譜データからの機械学習や強化学習で調整しています。 盤面を様々な部分形に分割し、学習済みパラメータで部分形をスコアリングし、その累積和を最終的なスコアとしているようです。 今回は実装を簡単にするため、以下のようにシンプルなスコアリングとしました。 着手可能数は次の一手を指せる場所の数です。 四隅周辺の形の良さについて 角から 3 マスの石の有無について、スコアを割り振っていきます。 スコアは感覚で恣意的に決めます。 実際のスコア計算では、図のように各四隅の縦横斜めを切り取り、スコアを合計します。 探索処理 探索処理では n 手先に潜って静的評価関数を適用します。 n 手先のスコアを元に n - 1 手先のスコアを決め、n - 1 手先のスコアを元に n - 2 手先のスコアを決め…、という風に再帰的に処理を行い、最終的に次の 1 手のスコアを決めます。 この再帰処理では、自分も相手も常に最善手を指すことを仮定します。 つまり、自分の手番ではスコアが最も高い手を選び、相手の手番ではスコアが最も低い手 相手にとって最も高い手 を選びます。 n 手先が自分の手番だとすると、以下のようになります。 しかし最終的には石の数を最大化する必要があります。 今回は、ラスト 12 手 空きマスが 12 箇所になった状態 になった時点で評価関数・探索処理を切り替え、最終局面まで全探索し自石数を最大化するようにしています。 反復深化 探索深さを決めるのは難しい問題です。 同じ探索深さでも合法手が多い局面ではゲーム木が大きくなり、計算時間が長くなります。 実際のゲーム AI ではユーザー体験やルール上の制約のために、計算時間の上限を設ける必要があります。 これを実現するのが反復深化と呼ばれる手法です。 反復深化はとても単純です。 時間が無くなった時点で探索を打ち切り、最後に探索が完了した深さのスコアを結果とします。 今回は 500 ms で探索を打ち切るようにしました。 ほとんどの局面で深さ 6 程度まで探索できるようです。 move board , place. x , place. オセロでよく用いられるのは、2 つの 64 bit 整数で黒石・白石の 64 マスの有無を表現する手法です。 この方法だと 64 マス全てに対する着手可能性判定が数十回のビット演算で出来てしまうようです。 すごい…。 今回は実装が面倒くさかったため簡易な手法を選びました。 これを縦横斜めにそれぞれ保持します。 まとめ シンプルな構成でそこそこの強さの AI を作ることができました。 ただし評価関数がキモで、恣意的にパラメータを決めているため AI のクセが出やすいようです。 実際に自分が対局すると勝率 5 割程度ですが、勝った対局では四隅を取らせて辺を奪うような結果が多いです。 辺の形が評価関数に反映できていないためだと思います。 辺の形を反映するように評価関数を設計し直すと改善するはずですが、ここから先の職人芸的なチューニングのことを考えると、強豪 AI のように機械学習してしまった方が実は簡単なのかもしれません。 今回はオセロ AI の仕組みを扱いましたが、将棋やチェスの AI も基本的には同じ仕組みで動いているようです。 いつか時間を見つけてトライしたい。

次の

人工知能の作り方【強化学習とは】

人工知能 オセロ

(C)FUTURUS ーー現在、大貧民はコンピュータと人間、どちらが強いのですか? 難しい問題です。 そもそも、大貧民はコンピュータにとって有利なゲームなんです。 コンピュータは場に出たカードをすべて覚えていますが、人間にはなかなか真似できませんよね(笑)。 ですが、誰がどのカードを捨てたか後から確認できる状況でも、私はコンピュータには勝ち越せないです。 ーーそれはなぜでしょうか? コンピュータは人間には見えにくい差を見つけるのが上手です。 たとえばハートの4とスペードの5を持っているときに、どちらを出せば勝ちやすいかの判断は人間には難しいですよね。 一方でコンピュータは誰がどのカードを持っているか?後々の試合展開はどうなるか?を1つずつ推測して優劣をつけていきます。 ただし、将棋や囲碁はプロ棋士というものが存在しますが、大貧民においてはそれがないため、人間のトップが戦った場合、どちらが勝つかは正直分からないですね。 ーー大貧民において、人工知能はどのくらいの速度で成長しているのですか? 現在、大会は11回行われているのですが、2009年の第4回大会までは人間のほうがはっきりと強かったと思います。 ただ、第4回大会でモンテカルロ法を使ったプログラムが出てきまして、それが発展し現在ではとても強くなっています。 2016年3月に囲碁で初めて人間のトップ棋士に勝利したGoogleの『AlphaGo』もこういった手法をベースにしていると考えられている。 現在、大貧民の人工知能の開発の核となっているのが、このシミュレーション試合のようである。 ランダムにカードを出すシミュレーション試合をするのではなく、実際の試合内容に近いシミュレーション試合を素早く大量にできるかにより、読みの精度が変わるようだ。 大渡さんが開発したプログラムでは1つの手を決めるのに1000局以上のシミュレーション試合を行う。 人工知能が自分で学習してカードを選択しています。 学習をした結果、「人間と違うな」と思う点は、強いカードの出し惜しみが少ないことです。 人間は2やジョーカーといったカードを最後までとっておく人が多いですが、人工知能は思い切ったタイミングで出してきます。 ジョーカーを使った革命も多くて、面白いですよ。 ただし、残り2人のときは全然ドキドキ感がありません。 お互いに相手の手札を特定していて、結果がわかっているので(笑)。 どのようにシミュレーションしても1位になるため、危険な橋を渡ってしまう時があります。 ーー大会のレベルは高いですか? プログラミング初心者でも参加できる大会です。 ゲームプログラミングに馴染みのない方でも開発しやすいように、運営側がライブラリやドキュメントを用意してくれています。 だけど、私自身が相当高いレベルまで持っていってしまったので、優勝はハードルが高いです(笑)。 私は学部を卒業後、1年間ニートだったんですが、その時期、ずっと大貧民の人工知能の開発していました。 なので、大貧民の開発時間は少なくとも1000時間は超えていると思います。 私のプログラムより強いプログラムは今後出てくるかもしれませんが、大貧民に対してここまで深く考える人は二度と現れないと思います(笑)。 ーーなぜそこまでの時間をかけて開発したのですか? 一番の理由は、やはり何かで一番になりたかったということですね。 また、私が開発を始めたころのチャンピオンのコードを見た時、「これが本当に最適な作り方なのか?」「もっと強くなるのでは?」と思ったのがきっかけです。 それで、一から実装をしました。 (C)FUTURUS コンピュータの「直感」と「先読み」 【大渡さんのコンピュータの仕組み】 大渡さんのプログラムは2つのパートに分かれている。 一つは、自分の手札を一見してどのカードを出すか選ぶ部分。 人間でいうところの直感にあたる部分だ。 二つ目は、頭の中でシミュレーション試合を行うモンテカルロ法によって手を決める部分。 こちらは先読みを担当している。 このうち「直感」は自身の過去の試合で選ばれた手を学習することによって、精度を高めることができる。 大渡さんのプログラムでは200万局以上の試合を学習している。 ここには機械学習と呼ばれる技術が使われる。 試合中は、プレーヤー全員が「直感で選ばれる手」を出すと仮定して頭の中で何度もシミュレーション試合行い、その都度順位を記録する。 多くのパターンの手札配置でシミュレーション試合を行うことで、自分がどの手を出せば平均的に勝ちやすいのか調べるというわけだ。 そして、試合後には自分が実戦で選んだ手を正解としてもう一度直感を鍛える。 時間をかけて選んだ手を直感で選べるようにしていく。 優れた直感により試合を先読みすれば、より正確な評価ができるようになる。 このサイクルを繰り返すことで、段々と強くなっていく仕組みになっている。 ーーなぜいろいろな大会に出るのですか? 人工知能の開発方法はゲームのルールによって大きく異なります。 将棋には将棋、囲碁には囲碁、大貧民には大貧民にあったアプローチ方法があります。 その違いを探るのは楽しいです。 それに、いろいろな大会に出る人は少ないので、自分がやる価値があると思いました。 幅広い知識を得られれば、より多くのゲームの人工知能を発展させられるかもしれないですから。 ボードゲーム・カードゲームの人工知能なら「こいつに聞けば間違いない」と言われるまでになりたいですね。 大貧民の人工知能は何の役に立つ? ーー実際に人工知能を作ろうと思った時、好きなボードゲーム・カードゲームを選択するべきですか? 好き 好きなゲーム、詳しいゲームをやると変な固定概念が入り、 開発がうまくいかないと言われることもあります。 ただ、好きなゲームだと開発をがんばろうと思えるので、私は好きなゲームをやるのはありだと思います。 ーー人工知能を作りたいと思う人は、最初はどのようにすれば良いと思いますか? 一流の人に会いに行くことが一番良いと思います。 実際に大会に出てみるとか、勉強会に行くとか…。 ハードルが高いと怖気づく人も多いのですが、決してそんなことはありません。 実際に足を運んでみると、「意外といけるかも」と思えるはずです。 また、開発者は基本的に話したがりなので、聞けばいろいろと教えてくれると思います(笑)。 (C)FUTURUS ーー大貧民の人工知能の知識がどのように実社会に活かされると思いますか? 人工知能自体は、翻訳、検索エンジン、広告のマッチングと様々な分野で活かされています。 ただ、大貧民の人工知能が直接的に「ここに活かされる」というのは難しいですね…。 将棋や囲碁の場合は、相手の情報がすべて見えているので、最善の手を出してくる想定で実装をします。 しかし、大貧民の場合は相手がどのようなカードをもっているか分かっていないので、過去の情報から推測する必要があります。 また、多人数なので相手の強さやプレースタイルによって適した戦い方が変わっていきます。 このように多様な状況に対応できる力が大貧民の人工知能には求められます。 こういった技術は、今話題の自動運転にもつながるかもしれません。 運転している時、運転者は通行人や対向車が次にどのような行動をするか認識できません。 人間の場合は「前の車、ふらふらしていて危ないな…。 速度を落としておこう」など経験や直感で、準備を行います。 人工知能もこのような感覚を持つ必要があります。 一方で、人間は自分自身の生死や他の人間との関係について優れた感覚を生まれたときから持っています。 ですので、人工知能が人間と同じだけの練習量で運転のような技能を習得することは難しいと考えられています。 それを補うためには、見えていない場所の状況や他の車の動きを色々なパターンでサンプリングし、頭の中で状況を進めて良し悪しを判断し、直感を鍛えるという手順を実際に道路に出るまでに数多くこなす必要があるでしょうね。 大貧民に限らず、ゲームの人工知能はそのための実験台と言えると思います。 ーー大渡さんは今後どのような活動をしていきたいと考えていますか? これまでは国内の大会だけに参加していましたが、今後は Facebookなどの大手企業も参戦している国際的な大会にも出ていきたいと思っています。 大渡さんが作成した大貧民の人工知能のプログラミングコードは無料で公開されている。

次の