プログラマ専用SNS ミクプラ

最近、遊びでCUIのオセロを作りました。
しかし、コンピュータ（AI）を製作できませんでした。
（思いつくのは打てる場所に打つAIくらいしか・・・）

ボードゲーム全般のAIはどのような考え方を元に実装すればいいでしょうか。
人間が考えて打つようなことを理論的な形としてプログラムすれば良いのでしょうか。
市販のオセロなどは強いAIがありますが、あれはどうやったら作れるんだろうか・・・。

私はAIの知識は全くありませんので宜しければ参考になる良いサイトや技術書を教えてもらえないでしょうか。

オセロ、チェス、将棋関連のAIは研究論文級な話のような気がしますが・・＾＾；

なんちゃってAIなら、私はよくバーチャルシミュレートします。
例えばですが、私がぷよ○よ作った時の敵AIは、
ぷよを落とす前に一度COMの頭の中ですべてのパターンで落としてみています。

・一番左で一度回転して落とす
・一番左で二度回転して落とす
・一番・・・

こんな感じですべてのパターンで落としてみて（実際に落とすわけじゃないです。落としたとしてどうなるか計算します）
どの操作が最適か判断します。

落ちた状況について点数を私は付けました。
ぷよ○よは左から３つ目がつみあがると負けですから、その列が高くなるとマイナスポイント。
両サイドが高くなる方がプラスポイント。
落としたことによってぷよが消えればかなりプラスポイント。
連鎖するならもっとプラスポイント・・。

みたいな感じで、4手位先まで全てのパターンで落としてスコアを計算し、
パターンの最適解を見つけました。
でもぷよは１手が最大２４種類しか無いので(6列にぷよの方向が4)４手先まで読んだとしても
24*24*24*24でそう多くありません。

でも将棋でこんなことをやったらとんでもないことに・・。
その分野によって適切なアルゴリズムは違うでしょう。
ゲームAIは私も興味があって調べましたが、本格的なものを作るのはやはり難しいですね。
私の知識では回答出来ないので、関連がありそうなキーワードを置いておきます。

・ニューラルネットワーク
・遺伝的アルゴリズム
・ベイジアンネットワーク
・モンテカルロ法

後こんなページもあるようです。

http://uguisu.skr.jp/othello/algo.html

既に調べていらっしゃると思いますが一応・・。
http://www.google.co.jp/search?hl=ja&so ... 4&gs_rfai=

オセロでしたら、参考サイトをいくつか紹介出来ます。

http://www.kitsunemimi.org/vsotha/algorithm.html
http://fible.s5.xrea.com/laboratory/othello/
http://hp.vector.co.jp/authors/VA015468/platina/algo/

参考になれば幸いです。
ちなみに私はオセロは思考ルーチンを組んだことが無いので、突っ込まれると細かいところは応えられないかも知れません。

ざっとだけ思考ルーチンの考え方のひとつを示しておきます。
(1)自分の石を置ける所を探索します。
(2)順番に置いてみて評価点をつける。　→　端は点数が高い。ひっくり返せる数が多ければ点が高い。
(3)次に相手が石を置ける場所を探索します。
(4)相手の石を置いてみて、評価点を付けます。
(5)一番、評価点の高い所を相手の石の評価点とします。
(6)自分の石の評価点から相手の石の評価点をマイナスします。これが今自分が置いた石の評価点です。
(7)自分が石が置ける所全部の評価点を算出して、一番点が高い場所に石を置きます。
で、実はこれだと２手先までしか読んでいませんから、(5)で止めずに自分→相手→自分→相手となるべく深い手の先まで評価点を付けていけば強くなります。
ただ、当然ながら読み手の分岐は指数関数的に増えていくので何十手も読むとすごく遅くなっていきます。なので途中で遅くなりすぎない程度の先読みで先読みをやめる必要があります。

あと定石と呼ばれる置き方がありますので、そのパターンデータを持っていて一致したら、その手を打つと強くなります。これが出来るのは終盤での戦いになりますが。

書籍を紹介します。
『リバーシのアルゴリズム C++&Java対応―「探索アルゴリズム」「評価関数」の設計と実装』
http://www.amazon.co.jp/dp/4875934289

この本を参考に作ってみたら、私如きでは勝てないプログラムができました。
うれしいやら悲しいやら。まぁどっちも低レベルってことなんだけど。

評価関数は作れますか？
後、ミニマックス法やアルファベータ法を理解していますか？

>キューさん
助言ありがとうございます。
研究論文並みなんですね（＾＾；
ニューラルネットワークについては今期の講義で学習する予定なのでそこで詳しく学んでみようと思います。

点数を付けてやるというのは評価関数というものですか？
これは少し自分でAIについて調べたとき出てきました。
評価関数を作ったことないので2、3手先まで評価する関数を作ってみようかと思います。

参考URL助かりました！！キーワードを「アルゴリズム」じゃなく「AI」と入れていたためか、良いのが出てこなかった・・・



>softyaさん
参考サイト、思考ルーチンを示してくださりありがとうございます。
まだ評価関数については最近その単語を知ったばかりで知識がありませんが・・・
　>端は点数が高い。ひっくり返せる数が多ければ点が高い。
この部分を盤自体に外枠なら～点、その一つ内枠なら～点と予め点数を付けて評価してみることにします。

>たいちうさん
返信ありがとうございます。
ここに示された本の表紙を見てみるとC++＆JAVA対応とありますが、主にどの言語が使われてるのでしょうか？
一応CとC++はできます。（C++は最近、入門書を1冊読んだ程度ですが）
JAVAも一応入門書を読みましたが私には合わなかったため深く学んでません。

>lbfuvab
他の方への返信にも書きましたが、評価関数については最近知ったばかりです。
探索アルゴリズムについてはリストと初歩的な木くらいしかの知識しかありません。

------------------

評価関数という言葉がキーワードになるみたいなので皆さんから頂いたサイトや書物などを参考に学んでみます。

> ここに示された本の表紙を見てみると C++＆JAVA対応とありますが、
> 主にどの言語が使われてるのでしょうか？

両方のサンプルが載っていますので、どちらか片方だけ知っていれば理解できます。
別の言い方をすれば、ソースコードの部分は内容が半分しかありません。
長所と見るか短所と見るか。私には冗長に思えました。

＞探索アルゴリズムについてはリストと初歩的な木くらいしかの知識しかありません。
ぶっちゃけると、再帰さえ知っておけば何とかなります。
私はNegaMax法とAlphaBeta法を合わせたNegaAlpha法で組みました(http://ray.sakura.ne.jp/search_problem/が分かりやすく、詳しいです)


分かりやすい評価関数としては
・重み付け評価(http://uguisu.skr.jp/othello/index.html等に詳しいです)
・発展的開放度理論(↑のサイト内に詳しく書いてあります)
・確定石の数(後半になると重要度が増しますが、正確に見積もるのは難しい)
などがあります。



もっと強くしたい時は
http://sealsoft.jp/thell/や
http://www.kitsunemimi.org/vsotha/等を見るといいかもしれません。

>たいちうさん
両方のサンプルが載ってるんですか・・・。
いつかJAVAもしっかり学ぶと思うので前向きに捉えます。
この本のレビューを見ると皆さんが絶賛しているので購入を考えてみます。

>lbfuvabさん
参考サイトの紹介ありがとうございます。
一通り目を通してみることにします。


-------------

＞皆さん
ご親切にありがとうございました（＾-＾
CUIで作ってのでできても公開はしませんがもしGUIに移植する機会があればせっかくなので公開しようかと思います。
だけど、暇つぶしに少し作ったオセロがAIを追加しようとするだけでこんな本格的なものになるなんて・・・。

これで解決とさせてもらいます。