弱い オセロ。 「わざと負けようとしても無理」と話題 プロも挑戦する“世界最弱のオセロAI”、生みの親に聞く開発の裏話 (1/2)

「わざと負けようとしても無理」と話題 プロも挑戦する“世界最弱のオセロAI”、生みの親に聞く開発の裏話 (1/2)

弱い オセロ

画像クリックで遊べます。 みなさんは勝てましたか? 作り方を解説していきます。 方針 世の中には強いオセロ 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 も基本的には同じ仕組みで動いているようです。 いつか時間を見つけてトライしたい。

次の

オセロAI入門

弱い オセロ

人気MOBAタイトル『Dota 2』のAIチームがプロプレイヤーをなどゲーム業界でたびたび話題になる「AI」。 凄まじい処理速度で圧倒的な力を見せることもある存在ですが、日本のAI会社AVILENは、『オセロ』で逆に負けることが難しい「 最弱AI」を開発しました。 この記事では、同社CTOの吉田拓真氏が本AIを開発するに至った経緯などをメールインタビュー。 本当に負けることが難しいのかも含め、ご紹介します。 Web上でされている「最弱オセロ」は、スマホだけでなくPCでも遊べるオセロゲーム。 記事執筆時点のAI戦績は、21勝5609敗6引分ということでハンパない負けっぷりです。 では、このAI本当に弱いのでしょうか。 自他共に認めるボードゲーム下手の筆者がさっそく挑んでみます。 まずは普通に負けたら恥ずかしいので、真面目にやってみました。 ほ、ほんとに弱い… このあと数回挑んでみたのですが、やはり勝ってしまう……。 というかどうやっても角を4つ取ってしまう……。 というわけではこの戦績に偽り無しのようです。 「AI」というワードからは連想しづらい「最弱」ですが、では、なぜこの「AI」が生まれたのでしょうか。 前述の吉田氏にメールで話を伺ってみました。 吉田拓真氏(以下、吉田氏):このオセロAIは2016年私が東大工学部の学生のときに個人で開発しました。 当時のAlphaGoの影響で、興味本位・勉強も兼ねて始めたのです。 開発自体は5ヶ月ほどで完成して放置しましたが、だれでも楽めるように、AVILENのメンバーの手も借りてwebに公開したところです。 もちろん、強いAIは他にもたくさんあるのですが、ちょうどそのときにYouTubeで負けに来るオセロの動画を見ました。 それは相手が最善を打つ前提で、評価の悪い手を選んでるだけなので、あまり弱くなく、ランダムに勝ってりもしてます。 そこで、私のコードは1行変えれば、とことん弱いAIを学習できることに気づきました。 深層強化学習AIの他の手法にないメリットは2点 1.人間が教えるわけではないので、どんなルールにも対応できる。 2.自己対戦で学習するので、棋譜がいらない(人間の手を全く学習しない) やってみたところ、絶対に相手に勝たせるAIができたのですね。 オセロというゲームが、「少なく取る」で成立するのも成功した一因です。 とても面白いのは、真逆のはずのゲームですが、負けオセロの序盤の動きは勝ちオセロそのものです。 だんだんありえない動きをしていきますが、オセロというゲームのさらに深い一面を見られたような気がします。 Twitterなどで調べると、本当に強い有段者がかれこれ工夫して、まれに負けて(勝って)いるみたいです。 人間はすごいですね。 ただ、いくつかこちらの「手抜き」もあるので、ありえないことではないと思っています。 ・本来12手探索できるところをサーバー負荷や、ユーザー体験のため、6手探索と半分に設定しています。 (AIの計算は0. 1秒) ・ユーザー体験のためランダム性をもたせています。 必ず最善を打つわけではありません。 ・強さを比べる対象がないので、あまり検証をせずに学習を止めています。 ということで、非常に面白いお話を聞くことができました。 相当に頭を凝らせば負けることもできるそうなので、興味のある方はチャレンジしてもよいかもしれませんね。 なお、吉田氏は、7月27日(土)に行われる機械学習 AI・人工知能 に関するカジュアルトークイベント「第38回 Machine Learning 15minutes! 」にする予定。 ここでオセロの話も少しするということです(記事執筆時点で定員50名のうち40名が埋まっています)。 《秋夏》.

次の

「世界最弱のオセロAI」が話題…一体何のために作ったの?開発者に聞いた

弱い オセロ

ちなみにAIZINEの母体のお多福ラボでも将棋のAI(人工知能)開発をしています。 そんなニュースを聞いていると、「AI(人工知能)って人間よりも強いのでは?」と不安がる方も多いはず。 ところがそんな中で、なんと 「世界最弱のオセロのAI(人工知能)」が登場しました!社が開発したは3477勝1134616敗187引分(2019年8月21日現在)とのこと。 実際に開発者がこんなツイートをしています。 世界最弱のオセロAI作りました すでにたくさんの方にプレイされて、いまの戦績は5勝2110敗4引き分け! 負けられるなら負けてみてくれ! — 吉田 拓真 TakuAtCoder1 圧倒的に負けてばかりなのに、 自ら負けにいくって一体どういうことなんだろう?そもそも、 オセロAIはそんなに弱いのか?など気になりますよね。 はやっ! あっという間に私の完封勝ちになりました。 とはいえ、 やっぱりあっさり勝ってしまうともの足りなく、やっていくうちにさらに「負けたい!」という願望がむくむくと出てきました。 こうなったら、意地でもオセロAIに負けてやる! 最弱王決定戦・オセロAIvs私〜3回戦〜 ということで、「勝ちに行く」ではなく 「負けに行く」勝負、3回戦。 「負けられるなら負けてみてくれ!」と言われたなら、今回は「あえて自ら負けに行く」スタイルで行きましょう。 つまり提示されたガイドの中でも、 一番取れる数が少ないところを狙う見込みです。 この赤線で囲われた部分のことです なぜこのマスは危険なのかというと、 その後四隅のマスやその周辺で相手が石をおいたら、確実にひっくり返されるためです。 (わかりやすく言うと、自ら一人で100人いる敵陣に突っ込んでいく感じです)確かにその後ひっくり返して取り戻せる確率が低そうです。 もちろんオセロAIがとっている戦略はこれだけではなく、まだまだたくさんありますが、このような工夫をしながら、オセロAIが自分の打てる場所を減らしていくことで「負ける」方に進んで行くのです。 さあ、負け方の原因がわかったところで最後の試合をしてみましょう。 最弱王決定戦・オセロAIvs私〜5回戦〜 さて、最後の試合も「序盤から攻める」などの負けパターンを使って戦ってみましょう。 負けの道を極めたオセロAI、恐るべし・・・! 世界最弱のオセロAIは全日本チャンピオン以上に「弱かった」! さて、これだけ戦ってきて結果はすべて 「私の圧勝・オセロAIの負け」となりました。 やはり「世界最弱」を名乗っているだけあって、負け方をわかっていてすごいですよね。 でも、そもそもボードゲームって普通では「勝ち」を目指すのに、なぜこのAI(人工知能)は「負け」にこだわるのか、詳しく見ていきましょう。 開発したAVILEN社の吉田拓真さんがオセロのAI(人工知能)を開発する最初のきっかけは、 囲碁のAI(人工知能)「AlphaGo」でした。 「AlphaGo」が学習を続けて人間のチャンピオンに勝ったというニュースは、実際にAIZINEが編集部のテツヤやつっちーがその衝撃を記事にしています。 そこで 「自分も同じものを、オセロで作りたい!」と考えプログラミングを勉強するようになりました。 とはいえ、それなら 「オセロに勝ちまくるAI(人工知能)」を作ればいいのでは?と考えますよね。 吉田さんが「わざと負けようとするオセロAI」を作るきっかけとなったのは、Youtube・ニコニコ動画の「」を見たことでした。 この動画ではAI(人工知能)が勝つ試合が多かったので、吉田さんが 「自分の手でもっと弱いAIを作ろう!」と考えて生まれたのが「最弱オセロAI」でした。 最弱オセロAIは、 通常のAI(人工知能)とは逆に「石を少なくとったほうが勝ち」というルールのもとで学習を続けつつ、私たち人間の打つ先まで読むことができるようになりました。 逆にいうと他の人が3000回もこのオセロAIに「負けている」だなんて、私たち人間もすごいですよね・・・! さて、今回は「世界最弱のオセロAI」と戦ってみました。 この試合から• オセロAIはやっぱり最弱だった(5戦5勝)• オセロAI「負け方」を極めているため、こちらが負けに行こうとしても難しい• オセロAIは全日本オセロチャンピオンが負けに行こうとしても負けない• オセロAIは「全力で負けに行くオセロAIの動画を見て、これならさらに弱いものを作ることができる」という理由で生まれた• 一見すると弱いオセロAIも、「石を少なく取る」「私たちの手の内を読む」などで学習を続けている ということがわかりましたよね。 世界最弱、と言ってもただのヘタレのような負け方ではなく、 「計算して負けていく」という姿勢がなんだか面白い感じがします。 また、「オセロ弱いんだよね・・・」と感じている皆さん、ぜひオセロAIに挑んでみて「どっちが弱いか」という競争をしてみるのもありかもしれません。 頭のいい人は「オセロの負け方」から学んで自分のオセロの戦い方に活かすこともできるでしょう。 とはいえ、「弱い」オセロAIは今後も負け記録を伸ばしていくに違いありません。 どんどん「弱く」なっていくオセロAIにも期待が高まりますよね!.

次の