LoginSignup
103
88

More than 3 years have passed since last update.

@TanigUhey(Yuhei Taniguchi)inNE株式会社

大富豪から学ぶアルゴリズム

Last updated at Posted at 2019-11-22

はじめに

この記事ではトランプゲームのひとつである「大富豪」(「大貧民」とも呼ばれます)を例にアルゴリズムの設計パラダイムについて紹介しようと思います。石油王から最新のアルゴリズムについて学んできたレポートではありません。

「バブルソートとか二分探索くらいは知ってるけど、アルゴリズムってどんな種類があるんだろう？」「そもそも●●●っていうアルゴリズムって普段使わないじゃん」みたいな人に向けた記事なります。

一つの問題を色々な角度からみることで別の手法が生まれるということが、この記事で伝われば良いと思います。

記事に載せているコードはPHPをベースにしていますが擬似コードなので、動作に必要な処理が抜けています。イメージのための補足にしてください。

また、この記事は社内勉強会で発表するにあたり急ぎで作ったものなので誤字・脱字・間違いや言い回しによって誤解を生む表現などがあります。

あったほうがいい知識

  • 一般的な大富豪のルール
  • PHPのコードがなんとなく読めるレベルの理解度
  • 計算時間O(N)の意味

扱う大富豪

解説のため一般的な大富豪のルールを簡単にします。

  • 対戦人数： 2人(1 vs 1)
  • カードは1~10, J, Q, K, Jokerの14種類・全て1枚ずつ
  • 説明を簡単にするため、数字の大きさがそのまま強さ(1が最弱とします)
  • 手札は7枚ずつおおよその強さが同じくらいの状態(強さが偏っていないとします)
  • 8切りなどの役は一切なし

このような大富豪を行うにあたって「配られた手札で勝つことができるのか」、「自分の手札をどう出せば勝てるか」などを考えることにします。
（説明の都合上求めたいことは都度変わることがあります）

全探索

まず最も簡単な方法から試してみましょう。
全てのパターンを調べて、勝てるパターンを常に選ぶ「全探索」という手法です。

全探索
/**
 * @param   array $hands 両プレイヤーの手札
 * @param   int   $prev_card 直前に出たカード
 * @param   int   $turn 0:自分のターン 1:相手のターン
 */
function search(array $hands, int $prev_card, int $turn){
    /* どちらかの手札が空なら勝ったプレイヤーをreturn */

    foreach ($hands[$turn] as $number) {
        // カードが出せる場合、探索を続ける
        if($prev_card < $number || /* 直前がパス */){

            /* handsから出したカード$numberを取り除く */

            $result = search($hands, $number, (($turn + 1) % 2));
        }
    }

    // 直前のカードがパス以外ならパスした場合も探索
    if($prev_card !== self::PASS){
        $result = search($hands, self::PASS, (($turn + 1) % 2));
    }
}

上記は再帰による全探索をしています。(厳密には深さ優先探索)

全てのパターンを調べるので、大富豪中に頭の中で全探索なんかしていると対戦相手から「早く出せ」と急かされることは間違いないでしょう。

計算時間はO(N!)です。

貪欲法

では次に、対戦相手に思いやりのある方法、計算に時間をかけない方法を考えましょう。

貪欲法はGreedy Algorithmとも呼ばれ、その場その場で最も良いと思った選択をする手法です。最も良い選択とは大富豪において例えば、

  • 手札の数が減れば減るほど良い
  • 出せるカードの中で最も弱いカードを出す（強いカードを手札に残す）

などが考えられます。

貪欲法
/**
 * @param   array $hands 両プレイヤーの手札
 * @param   int   $prev_card 直前に出たカード
 * @param   int   $turn 0:自分のターン 1:相手のターン
 */
function search(array $hands, int $prev_card, int $turn){
    /* どちらかの手札が空なら勝ったプレイヤーをreturn */

    $select = 0;
    $hand_max = 0; // 最も良い選択をした時の手札の強さ

    foreach ($hands[$turn] as $number) {
        if($prev_card < $number || /* 直前がパス */){
            /* カードが出せる場合、残りの手札の強さを調べる */

            if(/* array_sum($hands[$turn]) - $select */ > $hand_max) $select = $number;
        }
    }

    // 出せるカードがない場合パス
    if($select === 0){
        $result = search($hands, self::PASS, (($turn + 1) % 2));
    }
    else {
        /* handsから出したカード$selectを取り除く */

        $result = search($hands, $select, (($turn + 1) % 2));
    }
}

計算時間はO(N^2)です。

しかし貪欲法を用いても必ず勝てるパターンにたどり着けるとは限りません。
20191122-144453.png

上記のような状況で、青のプレイヤーが「1」を出したとします。この時赤いプレイヤーが貪欲的に最も弱い「2」を出してしまうと、相手が「3」を出して上がりになってしまいます。よってこの場面では「4」を出す最も良くない選択をしなければならない状況があります。

20191122-144807.png

動的計画法

この項目は大幅追記予定です。　時間が足りず完成に間に合わなかったので、解説がかなり読みづらくなっています。

では、確実に勝てるパターンを探すことにしましょう。
全探索の悪いところはただ無駄な計算が多く時間がかかってしまうことだけで、勝てるパターンが存在するなら確実に見つけることができます。
なので、動的計画法を用いて「勝てるパターンはどういう手順なのか」だけ調べることにします。

(広義的な)動的計画法とは分割統治法を元にメモ化を用いて効率よく探索する手法です。

分割統治法とメモ化

分割統治法は大きな問題を小さい問題に分割し、その小問題を解きつなげ合わせることで元の問題を解く手法です。

例えば、ゲーム開始時にどれだけ手札があろうと、ゲーム終盤では互いの手札は少なくなります。
その終盤のある瞬間の手札(と場のカード)の状況というのは、最初からその手札・枚数だけでゲームを開始した状況と同じと言えるでしょう。
手札2枚 VS 手札2枚の大富豪であれば、相手のカードを予測しどの手なら勝てるか全探索したとしても人間の脳で考えてもそれほど莫大な時間はかからないはずです。

全てのパターンを調べて、勝てるパターンを探している最中というのは、さきほど分割したような小さな問題はたくさん現れると思います。

例えば、ゲームを終盤に8を出したあと3を出して上がるようなパターンというのは、それまでゲーム序盤・中盤にカードを出す手順がたくさん存在しているので全体で見ると8→3で上がるパターンは多いように思えます。しかしその手順のどれを選んで終盤に差し掛かったにしろ、残り手札が8と3なのであれば、8を出して3を出せば上がりなのは変わりません。よって3を先に出すパターンというのは最初に1回だけ考えればよく、「3と8が残っていれば8を出せば上がれる」という計算済みの情報は残りの手順パターン全てで使えるということです。
このような計算結果をプログラム中にメモしておく手法をメモ化といいます。

ここからは実際の実装方法の話です。

メモ化に必要なのは同じ状況であれば結果は使い回せるということなので、「どの値が分かれば状況を一意に決められるか」を考えます。
大富豪の場合「自分が出したカード」「相手が出したカード」「直近で出たカード(場のカード)」が同じであれば同じ状況だと言えます。
これを配列にメモしながら探索を進めます。

以下のコードはメモの設計例です

メモ化
$hand_i = [1, 3, 5, /* 省略... */ 13];
$hand_j = [2, 4, 6, /* 省略... */ 14];
$DP[i][j][k]; // 1~:勝てる -1:勝てない 0:未計算
/* i, j = 手札のビット列(昇順に並べて使ったカードは1)
   例 hand_iが1,5を使っていたら i = 0b0000101 = 5

   k = 直近で出たカード 1 ~ 13, 14(Joker), 15(自分のパス), 16(相手のパス) */

大富豪で勝ちと判定されるのは自分の手札を使い切ったときなので、dp[0b1111111][j][k] = 勝ちと言えます。jとkの条件は以下の通りです。

j < 2^7 \\
k = 自分の手札のいずれか

初手から繰り下がっていく

自分が先攻だとすると、相手がパスしたところから始まると定義 → DP[0][0][16]
後攻ならDP[0][0][15]
そこからk_1を出したとすると次の遷移先はDP[k_1][0][k_1]
次に相手がk_2を出したとするとDP[k_1][k_2][k_2]
もちろん大富豪のルールに則ってk_1 < k_2でなくてはならない

出すことのできないパターンは計算しない(枝刈り)

勝てるパターンから繰り上がっていく

最後に出した手が自分のものなら勝ちなので、終盤に勝ちが確定したときどんな序盤・中盤の手順があるかを調べることにしましょう。
最後にk_1というカードを出して上がったとするとdp[127][j][k_1] = 勝ちです。k_1を出す直前にはk_2が場に出ていたとすると、DP[127][j][k_1] = DP[127 - k_1][j][k_2]となります。もちろんk_2にはゲーム開始時の相手の全ての手札のうち、k_1を次に出せるカード(k_1 > k_2もしくはパス)に限られます。
その次は、DP[127 - k_1][j][k_2] = DP[127 - k_1][j - k_2][k_3]のように手番を巻き戻していき、カードを何も出していない状況DP[0][0][パス(15or16)]まで辿ることができたら、そのk_n ~ k_1が勝てる手順ということになります。
途中でk_1 > k_2という制約によって手番を戻せなくなったら、そのDPの値は-1(計算済みで出せない)とメモ化しておけば、出せるカードがないかを探す計算はなくなります。

別視点から考える

そもそもこの記事で伝えたいことは、一つの問題を色々な角度からみることで別の手法が生まれるということです。

上で紹介したDP[i][j][k]なんかは大富豪でしか使えないような設計ですし、無理やり大富豪に動的計画法を適用したようなやり方です。しかし、大富豪のようなルールでも視点はたくさんあります。
これまでは相手と自分の手札を出す組み合わせを探索する、樹形図を書き出すようなものでしたが少し視点を変えてみます。

例1

役の強さを軸に考えます。1のあとに出せるカードは2以上、かつ自分の持っているカードです。また、2を出した後に1は出せないことはルールからわかる通りです。

以下の画像は出せるカードに有向辺を追加し、グラフの構造でカードを表現したものです。

20191122-151856.png

この画像の状況で赤が勝つ方法を求めるというのは、「赤いカードを全て通るルートを調べる。ただし、先に青いカードを全て通ってはいけない。」という経路探索問題に変わります。

例2

今度は先に自分の出すカードの順番を確定させたとしましょう。カードを出したりパスを選ぶのは交互に行われるので、次のような問題として考えることもできます。(0はパスを意味しています)

20191122-153022.png

まとめ

「別視点から考える」で挙げたような考え方で勝ちの手順を求めるにはどのようなアルゴリズムを学べば良いでしょうか。もしかしたら、あなたがすでに知っているアルゴリズムで解ける視点に問題を置き換えることができるかもしれません。

アルゴリズムを学ぶことは、その視点の見つけ方やその解き方の幅を増やすことであり、効率的にロジックがかけるようになるかもしれません。

あなたが明日書かなければならないコードは、どんな処理をしたいどの視点から見たどんなロジックのコードなのでしょうか。

103
88
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
103
88