読者です 読者をやめる 読者になる 読者になる

謎のesper情報

esper総合ブログ(爆)

大貧民のアルゴリズム

大貧民のアルゴリズムを考える。

まず、局面を限定した「詰め大貧民」というゲームを想定すると分かりやすい。

カードカウンティングによって、自分に見えていない残りのカード全てを持った対戦相手1人を想定するだけで、完全情報ゲームになるのがポイント。

つまりMIN-MAXで局面の木を探索することができるという寸法だ。

そうすると、大貧民の任意のある局面での、詰む/詰まない、を判定することが出来る。

おそらく通常カードは最強のものを出すなどの前向き枝狩りによって探索空間はかなり小さくできるので、将棋なんかよりは遥かに簡単だろう。

木を探索しなくても出来そうだが、そこは枝葉末節であるので置いておく。

「詰め大貧民」のアルゴリズムが分かったら、これを通常の大貧民に応用する。

まず第一に、今の局面が詰み、であるならば、詰める。これは当然である。

問題は詰みがない局面で何を出すかということである。

局面を評価をする関数を定義し、現状出来るパスを含む全ての手を指した結果の局面における評価関数の出力を比較して手を選択する、というのが基本的な手法となるだろう。

つまり、評価関数をどう作るかが大貧民アルゴリズムのキモになってくる。

ここで、フィニッシングポイント(以下FP)という概念を提唱したい。

  • 自分の手番で詰む手札である→FPは0
  • 任意のn枚の手札を捨てると、FPが0になる手札→FPはn
  • 何枚捨てても自分の手番で詰むことがない→FPは無限

これがFPの定義である。

たとえば5822とカードを持っているとすると、自分に手番が回れば2のペアと8は確実に切れるので、最後に5を出して詰む形。FPは0だ。

ここにKが加わり、58K22となっていると、Aと2とJokerが全て場に出尽くしいない限り、5かKのどちらか1枚を捨てないと詰み形にならないため、FPは1となる。ちなみに出てれば詰みなのでFPは0だ。

そして、最初の形から5がなくなると、822となり、世間の大貧民では2あがり、8あがりはナシなのでFPは無限、となる。

まぁそんな感じ。

そうすると、このFPの小ささを比較することで大貧民の基本的なアルゴリズムが完成するのではないか。

FPが同じなら単純に枚数の小さくなる手を選択すれば良く、それも同じならより強い*1手札の組みを選択するようにする。

また、先手をとれるカードを切った場合は、その先の局面での最良FPで比較するというわけ。

なかなかエレガント。

*1:この定義も厳密なものが必要だろうが、とりあえずはカードの数が大きいものほど強いとしておく