「サルかも将棋」 その2 有限でも無限

http://en.wikipedia.org/wiki/Game_complexity
↑ 日本語版が無いので...

将棋を含む「有限ゲーム」は理論上は「しらみつぶし」で回折すれば回答が出ることになっています。

(例)三目並べ(いわゆる「まるばつ」)の場合(対称・有り得ない局面を除いて)765通りの局面しかないので序の口ですね。そして、数分あれば「両者が最善を尽くせば引き分け」...と、結論が出せます。

将棋の場合は...

盤上の組み合わせ = 10^71 (10 の 71乗)
対局の組み合わせ = 10^226 (10 の 226乗) ← これは推定数です

...と桁違いに多いので「しらみつぶし」戦略での攻略は無理です。これが「有限でも無限」...と言うことです。

碁は問題のサイズがもっと大きくて

盤上の組み合わせ = 10^171 (10 の 171乗)
対局の組み合わせ = 10^360 (10 の 360乗)

...となり、最大級の難易度を誇ります。そのため人工知能の業界では「碁が人知の最後の砦」と言われています。

投稿者: webMaster 投稿日時: 木, 08/11/2011 - 13:28 categories [ ]