いつの間にか「日記」なるリンクができてたんですね.
質問掲示板に,オセロのAIがどうの…という話題があるが,
そのAIとやらをとりあえず関数として書くとき,その関数の型を
int AI( 現在の盤面情報, 打てる場所の配列 )
みたいな形にすることを考えた.
「打てる場所はどこどこなのか」の判定までは関数外で行い,
AI関数は「打てる場所の配列」で指定された候補のうち何番目を選ぶのかを戻り値で返す,という形.
さて,(この関数仕様の是非はともかくとして)
この「打てる場所の配列」のためのバッファを固定長で用意することを考えるとき,
その配列サイズはいくつにすればよいのだろうか?
「十分なサイズ」が必要……
盤面のサイズたる8x8=64要素 というのが最初に思い浮かぶ候補だろうが,
オセロは開始状態で中央4マスに駒が置かれているのだから,空きマスは最大でも60カ所.
「打てる箇所」を格納する配列サイズとして64は明らかに過剰である.
↓
じゃあ60にするの?
しかし打てる箇所が60パターンある盤面は存在しない.
開始時点の空きマスが60カ所あるとはいえ,実際に打てる箇所は4カ所しかないのだし,
一手打つごとに空きマスが1つ減っていくわけだから,配列サイズ60も明らかに過剰だろう.
↓
じゃあ,いくつあれば良いのよ? というのが問題.
どうやってこの答えを導き出せばよいのだろう? うーん…困った.
オセロの問題難しすぎ
Re: オセロの問題難しすぎ
駒は必ず駒の隣にしか打てないのだから,
配置されている駒の塊の周囲長(8隣接)というのを考えればどうだろうか.
とりあえず
・ひっくりかえせる場所しか打てない
・オセロの初期配置からたどり着ける盤面パターンは限られている
という要素を度外視して考えたとして……
単純に8x8マスの中にひとつながりな島を作るとき,最も周囲長を長くするにはどういう形の島を作ればよいのだろうか?
……わ,わかりません ^q^
とりあえずでかくて中に穴がたくさんあるようなのが良いのかな?
それともヒートシンクみたいな形の方が良いのかな?
うーん,頭わるーい.
配置されている駒の塊の周囲長(8隣接)というのを考えればどうだろうか.
とりあえず
・ひっくりかえせる場所しか打てない
・オセロの初期配置からたどり着ける盤面パターンは限られている
という要素を度外視して考えたとして……
単純に8x8マスの中にひとつながりな島を作るとき,最も周囲長を長くするにはどういう形の島を作ればよいのだろうか?
……わ,わかりません ^q^
とりあえずでかくて中に穴がたくさんあるようなのが良いのかな?
それともヒートシンクみたいな形の方が良いのかな?
うーん,頭わるーい.
Re: オセロの問題難しすぎ
思考ルーチン本をそっ閉じした自分には、
「一番多くひっくりかえせる場所を選ぶぜ!ヒャッハー」な脳筋AIしか思いつかない\(^o^)/
「一番多くひっくりかえせる場所を選ぶぜ!ヒャッハー」な脳筋AIしか思いつかない\(^o^)/
Re: オセロの問題難しすぎ
それはちと思考停止が早すぎやしませんか?
【「常に一番多くひっくり返せる場所を選ぶ」のでは,どうやらいまいちダメっぽい?】
という過去(小学生頃?)の反省を生かせば……
そう,
「多くひっくり返せる場所上位3個くらいからランダムで選ぶぜ!」
という至高のAIにたどり着くことができるじゃないですか.
【「常に一番多くひっくり返せる場所を選ぶ」のでは,どうやらいまいちダメっぽい?】
という過去(小学生頃?)の反省を生かせば……
そう,
「多くひっくり返せる場所上位3個くらいからランダムで選ぶぜ!」
という至高のAIにたどり着くことができるじゃないですか.
Re: オセロの問題難しすぎ
オセロの正しいやりかた(?)を知らぬ私のような者が無理に
・角を取るのがどうの
・外周部を取るのがどうの
・3手先くらいまで全探索して一番自分の色が多くなるやつを選ぶべき?
・ひょっとして,自分の駒同士がなるべく連続してない形の方がいいんじゃねーの??
みたいな思いつきな内容を考えて入れ込んだりすると,
かえって完全ランダムよりも弱くなったりしそう.
まぁオセロって,自分の手番に
「うぉあああ,打てる場所がすごいたくさんあるし!!」ということは稀である気がするので
ランダムに選んでもそこそこ確率で「その場面での最善手」が勝手に選ばれるんじゃないでしょうか(なげやり)
・角を取るのがどうの
・外周部を取るのがどうの
・3手先くらいまで全探索して一番自分の色が多くなるやつを選ぶべき?
・ひょっとして,自分の駒同士がなるべく連続してない形の方がいいんじゃねーの??
みたいな思いつきな内容を考えて入れ込んだりすると,
かえって完全ランダムよりも弱くなったりしそう.
まぁオセロって,自分の手番に
「うぉあああ,打てる場所がすごいたくさんあるし!!」ということは稀である気がするので
ランダムに選んでもそこそこ確率で「その場面での最善手」が勝手に選ばれるんじゃないでしょうか(なげやり)
Re: オセロの問題難しすぎ
こういう場合は、可読性を重視するのが一番だと思いますよ。
変なチェックや条件分岐、助長なエラーチェックなどが、多少のメモリと引き替えにざっくりと削れるのなら、そうするのが良いと思います。
どうしても、消費メモリを削りたいのであれば、オセロの盤面は8x8マスなので、配列ではなく符号無し64ビット整数で保持するというのも1つの手です。
座標x、yにコマを打てる場合
打てる場所の変数 |= 1 << (x * 8 + y);
とでもしてフラグを立てます。
ただ、処理はとても煩雑になりますね。 コードの本質的な部分以外の箇所にも目を向けなくてはならなくなり、その分コードは肥大化しバグも仕込みやすくなります。
どうしても、固定長の配列で保持したいのなら、打てるマス数が最大になるのは多分
□□□□□□□□
□●○□□●○□
□○●□□○●□
●□□○●□□○
○□□●○□□●
□●○□□●○□
□○●□□○●□
□□□□□□□□
な形になると思うので、26マス分が最小値ということになるでしょうね。
思考ルーチンの中身については何とも言えませんが、
角に打てたら+5点。 最外周に打てたら+3点。 という風に全てのマスに重み付けをするのが一番簡単なんじゃないかなっと思います。
この方法の良いところは、どのマスにどれぐらいの重みを付けたら強くなるのか、遺伝的アルゴリズムで簡単に成長させられるところですね。
変なチェックや条件分岐、助長なエラーチェックなどが、多少のメモリと引き替えにざっくりと削れるのなら、そうするのが良いと思います。
どうしても、消費メモリを削りたいのであれば、オセロの盤面は8x8マスなので、配列ではなく符号無し64ビット整数で保持するというのも1つの手です。
座標x、yにコマを打てる場合
打てる場所の変数 |= 1 << (x * 8 + y);
とでもしてフラグを立てます。
ただ、処理はとても煩雑になりますね。 コードの本質的な部分以外の箇所にも目を向けなくてはならなくなり、その分コードは肥大化しバグも仕込みやすくなります。
どうしても、固定長の配列で保持したいのなら、打てるマス数が最大になるのは多分
□□□□□□□□
□●○□□●○□
□○●□□○●□
●□□○●□□○
○□□●○□□●
□●○□□●○□
□○●□□○●□
□□□□□□□□
な形になると思うので、26マス分が最小値ということになるでしょうね。
思考ルーチンの中身については何とも言えませんが、
角に打てたら+5点。 最外周に打てたら+3点。 という風に全てのマスに重み付けをするのが一番簡単なんじゃないかなっと思います。
この方法の良いところは、どのマスにどれぐらいの重みを付けたら強くなるのか、遺伝的アルゴリズムで簡単に成長させられるところですね。
Re: オセロの問題難しすぎ
という結果を果たしてどうやって導き出すのか? という話が元々の本題なのですが,そこらへんはどういう理屈(?)によるものなのでしょうか?へろりくしょん さんが書きました:5年前どうしても、固定長の配列で保持したいのなら、打てるマス数が最大になるのは多分
□□□□□□□□
□●○□□●○□
□○●□□○●□
●□□○●□□○
○□□●○□□●
□●○□□●○□
□○●□□○●□
□□□□□□□□
な形になると思うので、26マス分が最小値ということになるでしょうね。
(ぱっと見,オセロのルール的にこの配置パターンって有り得るのだろうか?という疑問も)
思考ルーチンを学習で鍛えるとしたら,その過程には「まともな対戦相手」が必要そうですね.
(自分に対してだけ強い過学習AIとかいうのもそれはそれで魅力的?)