1. HOME
  2. 刊行物
  3. 金融ITフォーカス
  4. カテゴリから探す
  5. 数理の窓
  6. 面白いゲームのパターンをみつける

面白いゲームのパターンをみつける

2014年8月号

外園康智

数独、一筆書き、ルービックキューブ、チェスを“難しい”順に並べよ。

 難しさを、解くまでの“計算量”とすると、チェス>数独>ルービックキューブ>一筆書きの順となる。各々の計算量と面白さを考えてみよう。

 一筆書きは、図形の中のすべての辺を一回ずつ通る道順を探す問題だが、もし辺が30もあると“総当たり”に辺の行き来を試す必要があり、計算に三十京年もかかる。早く解くには数学の定理が必要だ。実は次の二条件を満たす時、一筆書きは可能になる。

 「条件① グラフ全体で、奇数個の辺が伸びる頂点の数が、0個か2個となる。(2個の場合は、一方が出発点で、もう片方が終点となる)条件② どの二つの頂点も辺を通って行き来可」

 これなら秒単位の時間で確認できる。

 3×3×3のルービックキューブの場合は、総パターン数が4,325京2,003兆2,744億8,985万6,000通りと膨大で、でたらめにまわして完成する確率は極めて小さい。しかし、どんなバラバラな形からも完成形にたどり着く手順の存在が、数学の“群論”により証明されており、最短の手順が20手であるなど、完全に解明がされている。

 一方、数独は、どんな配置に対しても解ける手順は見つかっていない。今のところ、“試行錯誤”が必要だ。数独に対する“決定的な解法の有無”は、実は、有名な未解決問題の「P≠NP問題」に依存している。この問題の正確な説明は難しいが、総あたりでは膨大な時間がかかる組合せ問題に対して、一筆書きと同じように十分早い時間で解ける解法が存在するかを問うている。もし、そのような画期的な方法があると、数独やマインスイパー、100桁の数字の因数分解(※1)や他の多くのパズルにも“効率的な”解法が示され、面白くなくなってしまう。しかし、大方の予想は否定的で、数独の難しさは保たれる。

 最後に、チェスは総パターン数が決まっているが、数学的定式化がしづらく、難しい問題とされる。勝率をあげる試行錯誤の余地がまだまだある。ちなみに、経済は不完全情報ゲームに分類され、手に入らない情報が多すぎて、やはり難しい。

 面白いゲームとは、定式化が可能で、総当たりでなく規則性や定理の発見により、必勝法や戦略の工夫ができるものだ。世界には法則が隠されており、適度に理解できつつもすべての問題を解く決定的なアルゴリズムはない“P≠NP”の方が面白い。

1) 100桁の数字の因数分解は、因数の発見が“十分時間がかかる”こと、因数を知っていれば正しい答えか簡単に確かめられること、を根拠に暗号に利用されている。

※組織名、職名は掲載当時のものです。

印刷用PDF

Writer’s Profile

外園康智Yasunori Hokazono

金融デジタル企画一部
上級研究員

この執筆者の他の記事

外園康智の他の記事一覧

このページを見た人はこんなページも見ています