BOFと最中限のアルゴリズム
昨日、 a2c さんが主催している BOF に参加させていただいた。それぞれ思い通りに開発しつつ、わからないところはみんなで解決的なのり。是非また参加させていただきたい。 BOFの中で、 西尾 さんが、 最中限 という3人でやるゲームを教えてくれた。ルールは 本家サイト を参照していただくとして、これをコンピュータ大戦するためのアルゴリズムを考えたい。 ゲーム理論 で考えた場合、 ミニマックス法 でやる場合はすべての条件を網羅しないといけない。この場合の計算コストは以下のようになる。 カードは全部で52枚ある 自分は17枚のカードを持っている 単純に計算すると、最初のターンで(17×3)×(16×3)×(15×3)× ・・・ (1×3)通りの条件を網羅しないといけない。500垓(該=10の20乗)回の計算。うーん無理だろ。 実際のゲームもこんなに計算しているわけじゃない。っていうかできない。再帰的なスレッドを入れ子して作るんだけど、これはアーランは得意そう。でも現実的には全パターンを網羅する必要なんてまったくない。ということで、 アルファ・ベータ法 等で、ゲーム木の深さを制限したい。それには条件が色々と必要になる。昨日初めて遊んだだけなので不確かだけど、以下のような条件では探索は不必要となる(と思うｗ)。 1回目のラウンドは、0か一番少ない得点を狙いたい 2回目のラウンド以降、自分が一番高得点の場合、相手に自分以上の得点を取らせたい 2回目のラウンド以降、自分が最中限の場合、この状態をキープしたい 2回目のラウンド以降、自分が一番低得点の場合、最中限の人を超えて最大得点以下の点を取りたい ラウンド内の各ターンでは、ラウンドで最大の成果を出せるように得点を取りたい 1番強いカードと1番弱いカードは絶対に取りたい時、取りたくない時に有効 点数を取りたくない場合、ターンで最大を目指すか、最少を目指す 点数を取りたい場合、最中を目指す うーん。どれぐらい減るのかは書いてみないと分からないな。。。まだまだです。各自が作ったアルゴリズムを実装したら対戦して、誰のアルゴリズムが強いかを競い合ったりしたいｗ