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

将棋のプロ性が消滅する日=非決定性チューリングマシンが出来ちゃった日

技術ネタ

この記事はほとんどの人が読もうと思わないんじゃないでしょうか
学生時代に研究室で計算量についての記事を書いた事がありましたが
将棋の話を深くする為に勉強ついでに
計算量理論の話を書く事にします。
将棋はNP問題かという事を議論している方々がいました
羽生善治氏は将棋はNPの問題だと言っていたそうです。

http://beboshogi.seesaa.net/article/318751721.html

計算機が計算をする際に対象とする問題の複雑さによって
いくつかの分類があるんです。
有名なのがPとNPです。※

複雑さの図はこんな感じ
下の方が一般的には短時間で解きやすい問題のクラス
(そんな単純に言えないですけどイメージしやすく言うとそんな感じ)


wikipedia より

P≠NP 問題は証明出来れば100万$もらえる未解決問題ですが
専門誌への投稿と共に何人かの査読を経ないと
証明したと周囲の人々にそうだと認識されないんです。
世の中の認識を変化させるべくイノベーションを夢見て
製品開発競争を繰り広げるシリコンバレーの面々も驚愕する事でしょう。
専門家の数人が「この問題の証明は正しい」と判断すれば残る
世界中の人間の認識が変化するんですから、
数学の未解決問題の証明は一瞬で世の中の認識を変化させる
イノベーションの一種です。
話が逸れましたが
NP問題の定義はwikipediaから拝借すると

NP の定義は次の2つである、ただしこれらはお互い同値であることが証明されている。
1非決定性チューリングマシンによって多項式時間で解くことができる問題。
2yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題。

との事です。
自分なりに整理してみると多項式時間というのは
コンピューターに入力するデータをn個必要として
そのデータを何かの処理に通す時
その処理にかかる時間が多項式で表される場合は多項式時間ですね。
(nと数字が+,-,×,÷でくっついてるだけなら多項式時間ですね。※)
バブルソートという効率の悪いデータの整理方法がありますが
n個のデータを配列に入れてソートさせた場合
最悪でも以下の数式より処理の手数は少なくて済みます。


つまり多項式時間は入力するデータの個数と処理にかかる手数の関係を
表したものです。その手数が指数関数的に発散せずに、1億年とかでなく
数日くらいの現実的な時間で解けるものという事です。

NP問題は非決定性チューリングマシン
(無限に並列化可能なマシン ヘッドの話は略※)
なら現実的な時間内に解けて、検証出来る問題なので
もし将棋(を一般化した問題)がNPに属する問題だとすると
非決定性チューリングマシンがあれば
将棋の探索木の底まで読める可能性があり
開始した時点で先手が勝利の宣言をし後手が敗北の投了を示すような事態が起こりえます。
それを見ている人間にはいったい何が起こったかきっとわからないでしょう。
当たり前と言えば当たり前のような話です。

将棋のゲームの一般化をしてみると
n×nの有限な盤
盤面のn×n以下の個数の駒
それらの駒が盤面上動きうる任意の移動ルールのパターン
(王が取られれば負けというルールは固定)
の有限な組み合わせから生み出されるゲームの一種という事になるので
このゲームがNPに属すと証明出来れば
少なくともそのゲームの特殊な場合である将棋は
NP以下の計算複雑性クラスに属する問題という事になりますね。
直感的にはnの多項式時間で表せそうな問題だけど
どうも違うみたいです。
詳しくは上記のリンク先で伺って下さい
ともかく非決定性チューリングマシンが存在すれば
将棋のゲームとしての価値がなくなるかもしれません
全て計算機が出した答えに従えば、
ゲーム開始前に先手が勝つか後手が勝つか
決定しているので、流石にこれだと観戦者が答えをしっている
事になるので興行性がなくなるのは避けられないでしょう。
非決定性チューリングマシンどうやって作るねん
という突っ込みはごもっともなんでまぁ、
この話事態は現在存在しないマシンがあった場合のお話ですね。
量子コンピューターとか実用化された将来の話ならどうなるんだろう)
なんで初期状態の盤面から終局の状態の盤面が決定されるかという
お話についてはまた今度

※ちゃんと定義から説明してとか割り算はいらないとかいう数理専門の方ごめんなさい
プログラミングとシミュレーションに必要な部分を学んで修了したので
抽象的な理論お話は要勉強なのです。