K.Maebashi's BBS

javaでオセロを作っているものですがよろしくお願いします。 javaでオセロゲームを作っているのですが、リバーシゲームの思考ルーチンについて ソースをダウンロードして見ているんですけど、よくわかりませんでした。 どうやっているのかを詳しく教えていただけないでしょうか？

はじめまして。 >javaでオセロゲームを作っているのですが、リバーシゲームの思考ルーチンについて >ソースをダウンロードして見ているんですけど、よくわかりませんでした。 >どうやっているのかを詳しく教えていただけないでしょうか？ 「学生」さんがどの程度のスキルをお持ちかわかりませんが、 http://kmaebashi.com/javaworld/index.html このページで簡単に説明しているように、このリバーシゲームのアルゴリズムは ミニマックス法とαβ枝刈りです。 それぞれどんなものかについても上記ページにごく簡単に説明していますが、 もちろんこの説明ではわからないからこそここで質問されたのかと思います。 ミニマックス法とαβ枝刈りはこの手のゲームの思考ルーチンとしては ごく一般的なものなので、検索すれば解説ページは出てきます。 Wikipediaの解説もそんなに悪くないかも。 http://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95 αβ枝刈りも検索すれば出ますが、高速化の手段なので(しかもそんな 劇的に早くなるわけでもないので)、最初はなくてもよいかも。 あとは評価関数ですが、少々手抜きの評価関数でも、ある程度先読みすれば、 並の人間の相手は可能なぐらいの強さにはなります。 たとえば盤面の各マスに評価値を付けておいて(当然四隅が最大)、 自分の石があったらその値を加算、敵の意思があったら減算、ぐらいの 評価関数でもそこそこ遊べるようなものになった記憶があります。 私のリバーシゲームでは結構凝った評価関数を実装していますが、 実のところこれがよい評価関数なのか、私には判定できません。 私自身がこの手のゲームが得意でないため、自分の作ったプログラムに まるっきり勝てないので、評価関数を直しても、強くなったのか弱くなったのか 判定できないためです。 実は、私のプログラムの評価関数は、以前別件で作った「6×6オセロ」の 評価関数の焼き直しです。「6×6オセロ」のときは、評価関数同士を 戦わせたりしてまじめに検討したのですが、それを8×8に焼き直すときには、 まったく検証していません。手抜きです……

ご返信ありがとうございました。 >「学生」さんがどの程度のスキルをお持ちかわかりませんが、 > javaは本を一冊読んだ程度の実力です。 オセロゲームを現在、作成しています。 コンピュータの作成では、ランダムでしか対戦ができないため、 コンピュータが強くないので強くしたいと思っている所です。 リバーシゲームのアルゴリズムは検索して調べてみたのですが、 ソースを見ても詳しくわからないので 評価、着手数、要素の計算などはどこでやっているのか教えてもらえないでしょうか？

>評価、着手数、要素の計算などはどこでやっているのか教えてもらえないでしょうか？ 評価関数がどこにあるかといえば、Eval02.javaにあります。 これはEvaluateBoardインタフェースを実装しており、Eval00.javaとかEval01.javaと 差し替えられるようになっています。Eval02を実際にnewしてくっつけているのは ReversiApplet.javaです。 着手数や要石の計算は、このEval02.javaの中のscanLineで盤面を4方向にスキャンし、 フラグを立てています。以下のページに図があります。 http://kmaebashi.com/javaworld/index.html ただ、「学生」さんの現状のプログラムが、 >コンピュータの作成では、ランダムでしか対戦ができないため、 >コンピュータが強くないので強くしたいと思っている所です。 ランダムで(打てるところに?)打つ、というレベルなら、なにもこんな複雑な 評価関数をいきなり導入しなくてもよいのではないでしょうか。 …と、いうことを前回の返信で言いたかったのですが。

今見てみたのですが、 >評価関数がどこにあるかといえば、Eval02.javaにあります。 >これはEvaluateBoardインタフェースを実装しており、Eval00.javaとかEval01.javaと >差し替えられるようになっています。Eval02を実際にnewしてくっつけているのは >ReversiApplet.javaです。 Eval00.javaやEval01.javaの方が、Eval02.javaよりはずっと簡単なので、 読むならそちらの方がよいでしょう。

返信ありがとうございます。 >Eval00.javaやEval01.javaの方が、Eval02.javaよりはずっと簡単なので、 >読むならそちらの方がよいでしょう。 その通りで、自分にはEval02.javaは難しいので、 Eval00.javaを参考に作成したいと思います。 Eval00.javaでは、 cellPriority[][]で評価をしていて、 自分の石だったら足して、コンピュータの石だったら引いているのは わかるのですか最後のcellsValue + canPutNum * 100では なぜ100をかけているんでしょうか？ 後、Eval00.javaは上の説明であっているでしょうか？ 違っていたら、流れを教えてもらえないでしょうか？ たびたび質問すいません。よろしくお願いします。

>Eval00.javaでは、 cellPriority[][]で評価をしていて、 >自分の石だったら足して、コンピュータの石だったら引いているのは >わかるのですか最後のcellsValue + canPutNum * 100では >なぜ100をかけているんでしょうか？ canPutNumは石が置ける場所の数(着手数)です。 オセロは石が置ける限りたとえ不利になるとしてもパスはできないので、 着手数は重要です。手詰まりが最大の敵です。 そのため、canPutNumが評価値に対して大きなウエイトを占めるように するために、100をかけています。 もちろん、cellPriorityの各要素の値を小さくしても同じ効果が あるでしょうけど。

基本値の計算が作成できました。 次にミニマック法を作成してみたいと思うのですが ComputerPlayer.javaでは何手先まで読んでいて、どこでやっているんでしょうか？ 後、ab法はどこでやっているのですか？

>次にミニマック法を作成してみたいと思うのですが >ComputerPlayer.javaでは何手先まで読んでいて、どこでやっているんでしょうか？ ComputerPlayer.javaはほぼ全域がミニマックス法とαβ枝刈りなので 「どこで」というのはないのですが、先読みの深さについては以下のように なっています。 ・通常は4手先までです(DEFAULT_SEARCH_DEPTH)。 ・残りのマスの数を数えます。これが残りの手数の概算(パスを考慮しない)と 　なるのですが、これが5(WIN_SEARCH_DEPTH)以下になったら、 　完全読み切りモードに入ります。 >後、ab法はどこでやっているのですか？ 変数alphaBetaValueで処理を分けているあたりです。 今ソースを見ると、残手数がPERFECT_SEARCH_DEPTH以下のときと WIN_SEARCH_DEPTH以下のときとでなにやら分岐していますが、 ここで設定した変数は使っていないので、無視してください。すみません。

アドバイスのおかげでコンピュータが作成できました。 ありがとうございます。 こちらのサンプルアプレットでのオセロゲームで 石がひっくり返るときに たとえば、黒を置いた時に白から黒にひっくり返るのですが 最後のほうになると黒を置いた時に石が黒に代わってから白から黒に回って変化して いるんですけどそれはなんで最後のほうだけなるんでしょうか？

>こちらのサンプルアプレットでのオセロゲームで >石がひっくり返るときに > >たとえば、黒を置いた時に白から黒にひっくり返るのですが >最後のほうになると黒を置いた時に石が黒に代わってから白から黒に回って変化して >いるんですけどそれはなんで最後のほうだけなるんでしょうか？ 前の質問ですけど コンピュータの時だけなってしまいます。

>たとえば、黒を置いた時に白から黒にひっくり返るのですが >最後のほうになると黒を置いた時に石が黒に代わってから白から黒に回って変化して >いるんですけどそれはなんで最後のほうだけなるんでしょうか？ この説明ではなんだかよくわかりませんが、たぶん自動でパスしてるんじゃ ないでしょうか? このプログラムでは、打つところがないときは勝手にパスします。

>この説明ではなんだかよくわかりませんが、たぶん自動でパスしてるんじゃ >ないでしょうか? このプログラムでは、打つところがないときは勝手にパスします。 > いや、確かに表示がおかしくなってますね。 実際にコンピュータ同士対戦させてみて、最後のほうの石の表示を観察してみてください。 結果的な盤面変化は問題ないのですが、ひっくり返る過程の表示だけ変です。

>いや、確かに表示がおかしくなってますね。 >実際にコンピュータ同士対戦させてみて、最後のほうの石の表示を観察してみてください。 >結果的な盤面変化は問題ないのですが、ひっくり返る過程の表示だけ変です。 再確認しました。思い込みとは恐ろしいもので、たくさんの石を一気に ひっくり返すとき、ひっくり返す前から色が変わっているにもかかわらず 気付いていませんでした。失礼しました > 学生さん このプログラムは、ゲームのメインループ(先手後手を切り替えながら ゲームオーバーまでぐるぐる処理)を普通のループで書きたかったため、 イベントドリブンであるGUIとは別のスレッドで動かしています。 その待ち合わせがうまくいっていなくて、アニメーション前に盤面が 再描画されているように思います。 何年も前に公開したプログラムなのでいまさらなのですが、ちょっと確認してみます。

>このプログラムは、ゲームのメインループ(先手後手を切り替えながら >ゲームオーバーまでぐるぐる処理)を普通のループで書きたかったため、 >イベントドリブンであるGUIとは別のスレッドで動かしています。 >その待ち合わせがうまくいっていなくて、アニメーション前に盤面が >再描画されているように思います。 この処理は、どこでやっているんですか？

>>このプログラムは、ゲームのメインループ(先手後手を切り替えながら >>ゲームオーバーまでぐるぐる処理)を普通のループで書きたかったため、 >>イベントドリブンであるGUIとは別のスレッドで動かしています。 >>その待ち合わせがうまくいっていなくて、アニメーション前に盤面が >>再描画されているように思います。 > >この処理は、どこでやっているんですか？ ゲームオーバーまでぐるぐる回る処理のことであれば、 Judge.javaでやっています。

>>いや、確かに表示がおかしくなってますね。 >>実際にコンピュータ同士対戦させてみて、最後のほうの石の表示を観察してみてください。 >>結果的な盤面変化は問題ないのですが、ひっくり返る過程の表示だけ変です。 > >再確認しました。思い込みとは恐ろしいもので、たくさんの石を一気に >ひっくり返すとき、ひっくり返す前から色が変わっているにもかかわらず >気付いていませんでした。失礼しました > 学生さん > >このプログラムは、ゲームのメインループ(先手後手を切り替えながら >ゲームオーバーまでぐるぐる処理)を普通のループで書きたかったため、 >イベントドリブンであるGUIとは別のスレッドで動かしています。 >その待ち合わせがうまくいっていなくて、アニメーション前に盤面が >再描画されているように思います。 > >何年も前に公開したプログラムなのでいまさらなのですが、ちょっと確認してみます。 > これは、どこを直せばよろしいのですか？

>これは、どこを直せばよろしいのですか？ 前回書いたとおりJudge.javaがGUIのイベントドリブンなスレッドとは 別スレッドで動いていて、石をひっくり返すところは、Judge.javaの方の スレッドで、Board.javaのput()から呼び出されています (window.animationPut()メソッド)。 石がひっくり返るアニメーションの前に、既にBoard内のデータは 書き換えられているので、もしその前に画面の再描画が動いてしまえば 現状のような現象になると思うのですが、すみませんが最近どたばたしていて 私のほうでは原因が追えていません。

> >石がひっくり返るアニメーションの前に、既にBoard内のデータは >書き換えられているので、もしその前に画面の再描画が動いてしまえば >現状のような現象になると思うのですが、すみませんが最近どたばたしていて >私のほうでは原因が追えていません。 自分の方で調べて直してみたのですができませんでした。 今、お忙しそうですが原因がわかったらでいいので教えてもらえるとありがたいです。

>今、お忙しそうですが原因がわかったらでいいので教えてもらえるとありがたいです。 すみません、ちょっと手間取ってます…

大変遅くなってしまいましてすみません。学生さんがまだここを見ているかどうかも わかりませんが… >>石がひっくり返るアニメーションの前に、既にBoard内のデータは >>書き換えられているので、もしその前に画面の再描画が動いてしまえば >>現状のような現象になると思うのですが、すみませんが最近どたばたしていて >>私のほうでは原因が追えていません。 > >自分の方で調べて直してみたのですができませんでした。 > >今、お忙しそうですが原因がわかったらでいいので教えてもらえるとありがたいです。 Board.javaのput()メソッドの中のwindow.redraw()を抜けばよいようです。 このメソッドは、最終的にはCanvasのrepaint()を呼び出すことで、オセロの 盤面の再描画を行います。石を置いた後、アニメーションとともに画面の更新は 終わっているのですが、「念のために」全体の再描画をかけているわけです。 しかし、AWTにおけるrepaint()は非同期なので、即座に実行されるとは限りません。 この再描画要求が、「次に石を置き、盤面の状態は変わったが、アニメーションの前」 という状況で実行されると、アニメーション前に盤面の絵が更新されてしまいます。 ソースは近日中に差し替えます。ご指摘ありがとうございました。

> >Board.javaのput()メソッドの中のwindow.redraw()を抜けばよいようです。 > >このメソッドは、最終的にはCanvasのrepaint()を呼び出すことで、オセロの >盤面の再描画を行います。石を置いた後、アニメーションとともに画面の更新は >終わっているのですが、「念のために」全体の再描画をかけているわけです。 > >しかし、AWTにおけるrepaint()は非同期なので、即座に実行されるとは限りません。 >この再描画要求が、「次に石を置き、盤面の状態は変わったが、アニメーションの前」 >という状況で実行されると、アニメーション前に盤面の絵が更新されてしまいます。 > >ソースは近日中に差し替えます。ご指摘ありがとうございました。 お忙しい中、ありがとうございました。