カスパロフ対DEEP JUNIORの最終結果は引き分け 101
ストーリー by Oliver
脳-vs-CPU 部門より
脳-vs-CPU 部門より
happyhacking 曰く、 "
ロイター通信の記事によると、毎度お馴染みの国際チェス連盟が主催する人間対計算機(プログラム)のチェス世界一決定戦ですが、今回は引き分けに終わった様です。対戦したのは、人類代表がガルリ・カスパロフ氏で、計算機代表がDEEP JUNIORという最強のプログラムでした。
現在の計算機の様に、CPUで演算を行なっている限り結局は引き分けになりそうな気がしますが、人間の脳の働きの解明が進む昨今、脳を完璧にシミュレート出来れば、計算機の方が勝ちそうな気がするのは私だけではないはずです。人間には直感という素晴らしい感覚がありますが、それまでシミュレート出来るようになれば、本当の人工知能の完成ってことでしょうか？"
脳のシミュレートができなくても (スコア:2, 参考になる)
計算機でもDPマッチング [google.co.jp]により「直観」を実現することは可能です。
Re:脳のシミュレートができなくても (スコア:2, 興味深い)
既に最強です。
脳のシミュレートなどできなくても、人間が「知性」だと
思っちゃっている事の多くは計算機で実現できる、というのが
チェスで改めて証明されている、と見るべきかもしれません。
その代わり知性以前と思われていた、単純な認識のような
赤ん坊から持っているような基本能力が、計算機的には
なかなか難しいこともわかってきたのが面白いところです。
まあ、チェスは飛行機的に最終結果だけ同じことができれば
よいという力技戦術でクリアされてしまいましたが、将棋や
囲碁では当面それは通用しないので、また人間の思考プロセスを
模したアプローチに注目が集まるでしょうね。というかチェスは
ターゲットとしては終わり、という認識がされているので、今は
囲碁に行きつつあったはず。ただ、もし人間の思考メカニズムが
解明されたとしても、それは仕組みであって本質ではない、と
いうことになりそうですが :-)
生命が一種類だけではないように、知性も一種類だけではない、と
いうのは誰が言ったんでしたっけ？
Re:脳のシミュレートができなくても (スコア:1)
Re:脳のシミュレートができなくても (スコア:1)
というような話を聞いたことがあります。
実現されてしまうとただのアルゴリズムになると。
昔は"漢字仮名変換"が人工知能と呼ばれていたそうで。
Re:脳のシミュレートができなくても (スコア:1)
脳の一機能が計算機によって安価に提供されるようになったとき、その時点でもまだ「知能」であるとされている仕事を人間の脳はやればいいのです。
それによって人間は知能に関して常に計算機に対して優位に立てることになります。
Re:脳のシミュレートができなくても (スコア:2, 興味深い)
あきらかにチェスや将棋にはそういった構造がありませんし、おそらく P で解ける問題でもないでしょう。したがって DP のテーブルを用意しても、それに基づく 「DP マッチング」の結果はあくまで局所解であり、全域で最適である保証は得られません。そして単に局所最適を求めるならば、DP に限らず様々な手法があります。
そのような局所最適な解を「直観」と言うのならば、わざわざ「DP マッチングを使えば実現できる」と言わずとも、同様な手法が他にも数多くあるわけです。
Re:脳のシミュレートができなくても (スコア:2, 興味深い)
チェスとかにDPを適用する場合の難点は、
・相手がいる。(マルチエージェント)
・状態空間が膨大で計算量が大きい。
という事だと思います。
仮に、相手がある局面において決まったの手を打つと仮定すれば
計算量は別にして、その仮定の元で最適解が得られます。
MDP(Markov Decision Problem)だから、 Bellman 方程式を解けばよいだけです。
本当は、相手によって最適な戦略は変わってしまいますが。
"決まった手"と言うのは、Aを0.5、Bを0.3、Cを0.2の割合で
選択するといった確率的なものでも構いません。
ただし、その確率が変わる(これを相手が学習する言う)場合には、
MDPではなくなってしまいます。
実際には相手が居るので、例えば MIN-MAX法 [kyoto-u.ac.jp]とか
を使ったりして、ゴリゴリすることになるのでしょう。
# 解けるかどうか分かりませんが、できたとしても。
ところで、254490さんの
>> チェスや将棋のように、「過去の経験」が配列として格納できる場合、
は、 Profit sharing [google.com] とか言われます。強化学習でも良いか。
配列を覚えておく必要はありませんが。
ベルマン方程式を状態遷移確率で解くか(DP:DynamicPrograming)、
サンプル系列から解くか(Profit Sharing、Reinforcement Learning)
見たいな違いですが。
Re:脳のシミュレートができなくても (スコア:1)
> 現状では求めることさえできない訳ですよね。
そうですね。これでは状態遷移確率が求められませんので、
>> MDP(Markov Decision Problem)だから、 Bellman 方程式を解けばよいだけです。
は明らかに間違いです。m(_ _)m
状態遷移確率が固定であっても、不明だとDPは解けませんね。
#強化学習なら可能ですが。
Re:脳のシミュレートができなくても (スコア:1)
脳のシミュレートは不要，という所は同意です。
DPマッチングで最適なパスを探索する際に参照するスコアをどう決定するか，言い換えると「次の１手」が勝つためにどのくらい寄与するか否かを評価するところで，人間の「直観」がより強く働いているのではないか，と思います。
チェスや将棋の各局面における『勝つ確率』が，全て厳密に定式化できるなら，上記の限りでは無いとは思います。
計算機が人間より有利なのは，より多くの手を厳密に"先読み"できること。計算機が不利なのは，定式化できない状況で，一瞬で「どちらが有利か」を評価する部分(パターン認識?)だと思っています。
Re:脳のシミュレートができなくても (スコア:2, 興味深い)
> できること。計算機が不利なのは，定式化できない状況で，
> 一瞬で「どちらが有利か」を評価する部分(パターン認識?)だと
> 思っています。
囲碁ではそれが問題になっているそうです。人間にも？？？という
局面が多く、当然ルール化できず、その結果プログラムもうまく
評価できない。チェスや将棋なら駒固有の価値も使えるのですが、
それがなく純粋に他の石との位置関係だけなので非常に難しいとか。
ちなみに、人間の最大のアドバンテージは、読まない能力です。
評価に入る前に筋のほとんどを読まずに切って捨てることが
できているので、組み合わせ爆発が起きる前の段階で問題を
処理できています。計算機は真面目に評価しなきゃいけないし
無駄読みが多すぎるので、これで五分五分になっています。
Re:脳のシミュレートができなくても (スコア:1)
結局のところ、問題に適合させたニューラルネットでパターンとして 評価した結果読むべき筋を絞りこんでいる、ってことじゃないかと 思うのです。
で、これって意識レベルに上がらない無駄な計算を膨大に 実行することに相当するんじゃないかなぁと。コンピュータの計算は こういうレベルの計算も同じように逐次実行するので膨大に見えるけど、人間が巧くサボってる理由でもないのかも。
の
最近の将棋プログラムで言えば (スコア:3, 参考になる)
ある手が明らかに悪いことが分かればその先は読まなくて済みます．このようにして計算を「巧くサボる」手法は forward pruning(前向き枝刈り) と呼ばれる手法で，将棋プログラムでは一般的に用いられている手法です．
また，「この手は重要そうだなぁ」と判断できた場合にはその先よより丁寧に読むと良いことが知られています．この手法は seach extention(探索延長)と呼ばれています．
前向き枝刈りも探索延長もパラメータの調整が難しいのですが，これをプロの棋譜から学習させる(計算する)手法として実現確率に基づく探索 [u-tokyo.ac.jp]bというのが最近提案されて，非常に注目を浴びています．
#業界関係者に...
Re:脳のシミュレートができなくても (スコア:1)
＞チェスや将棋の各局面における『勝つ確率』が，全て厳密に定式化できるなら，上記の限りでは無いとは思います。
上記コメントでこの1文は文脈不明なので無視して下さい。すいません。
ところで、 (スコア:2, 興味深い)
人間が強くなってきたのか、完璧と思われたプログラムが前より弱かったのか。
それとも、こういうゲームに「完璧な答え」なんて存在しないのか。（それを証明するのも大変そうだけど）
結局、同じところをグルグル回ってるだけなのかも知れませんね。（３目並べみたいに）
# 「神の一手」は存在するのか？
---Over, hri.---
Re:ところで、 (スコア:1, 興味深い)
対局が進むにつれて盤上がどんどんさびしくなっていき、
両者とも兵力が不足して詰めることができず引き分け、
というのはよくあるパターンです(強い人同士だと特に)。
これはチェスというゲームの限界であり、
コンピュータも強くなりすぎてもうチェス程度のゲーム性では
飽和してしまったということでしょう。
というわけでこれからのターゲットは将棋・囲碁ということになり、
東洋、とくに日本の出番だといえるでしょう。
チェス・将棋・囲碁の引き分け事情 (スコア:1)
＞両者とも兵力が不足して詰めることができず引き分け、
ただ、さびしくなっても延々と駒を動かし続けることは可能なので、
「いいかげん引き分けにしようよ」という話を対局者同士つけないとキリが
ないわけですよね。その事情を知ってないと、引き分け提案→拒否→再提案→合意、
というプロセスは胡散臭く聞こえるかも。
将棋はさびしくならないので、このケースは少ないのですが、皆無ではありません。
この場合、しばらく指しているとその前の局面に戻ってしまう無限ループにハマります。
これを「千日手」といい、現行ルールでは一部の例外を除いて引き分け（再戦）です。
これに例えば「先手の負け」などと勝敗を定義すれば、将棋は原理的には
引き分けのないゲームになります。ただし現実的には、持将棋などの問題が
あるので難しいところです。
囲碁では、さらに稀ですが、千日手と同様のパターンが存在します。
ただし囲碁には世界中にいろいろなルールが存在し、この場合の結論は
ルールの違いに依存します。
＞というわけでこれからのターゲットは将棋・囲碁ということになり、
＞東洋、とくに日本の出番だといえるでしょう。
引き分けが少ないからいいかどうかは…？
将棋・囲碁が現行技術でまだまだの分野だから、これからは日本の出番、
とは言えると思います。また、そうあってほしいものです。
Re:チェス・将棋・囲碁の引き分け事情 (スコア:2, 参考になる)
チェスの終盤はポーンの前進と成りを巡る駆け引きが展開されます。
チェスにおけるコマの交換は計画的な戦術です。互いの戦力が
豊富な状況では問題にならない９７：１００程度の僅かな効率の差が
コマの交換を進めると１：４と決定的な差になります。
有利な側は常に単純化による差の拡大を狙い筋にします。
また、将棋では同一手順の無限王手は禁止手ですが、チェスでは
引き分けです。これで比較的簡単に引き分けに持ち込めます。
有利な側は連続王手で引き分けに逃げられることを防ぐためにも
コマの交換を促進します。
Re:チェス・将棋・囲碁の引き分け事情 (スコア:1, 参考になる)
このあたり、コンピュータによる研究で、勝つのに50手より長い手数を要する終盤のパターンが発見されて、国際ルールは改正されているはずです。
人間の素人と名人の違い (スコア:2, 興味深い)
上記のテストを含めた複数のテスト（一般的な知能テスト、記憶テストも含む）を行ってみた結果、素人と名人で顕著な差が出たのは「実戦に現れうる形の盤面の記憶能力」だけだったという話でして。
その論文の結論としては、ここでは端折った書き方をしますけれども、結局は経験積んで実戦に現れうるパターンをたくさん知っている人が強いらしい……ということでした。
当たり前といえば当たり前の結論なのですが、重要なのは、思っているほど他の点では素人と名人の違いが無かった、という点でして。
だからどーしたと言われると困るのですが、何かの参考の足しにはなるかなと思い、書き込んでみました。
勝つて言はず、敗れて語らず、
謙譲を崇ぶ者は君子也、怨怒を起す者は小人也。
脳のシミュレート性能が本当に試される問題 (スコア:2, おもしろおかしい)
もし本気で問題に取り組むならばの問題ですが、もはやチェスや囲碁、将棋は制約がきつすぎて、幅広く脳の挙動をとらえるには無理がないでしょうか? なおかつ、実用になる(ビジネスになる)問題実例になかなか行き当たらない。
もうちょっと制約が緩く、かつ実用性もありそうな問題として、次は市場予測問題に取り組んでほしいなぁ... 制約は手持ちの資金と、値幅制限(株式の場合、いわゆるストップ高とストップ安)ぐらいしかないし。かつ、市場に参加しているのは少なくとも現状では人間が多勢だから、脳がシミュレートできると言い張るならこれぐらいできないと。
これで大当たりすれば、「金融工学で儲けました」という人が本当に現れて面白いことになりそうなのだが(とけしかけておこう)。
もちろん、今までにもエリオット波動分析のように、短中期の変動予測をかなり精度良く行う方法はあります。ただ、それでも動きが詰まってきた時に上と下のどちらに抜けるか、あるいはトレンドラインがいつ破れるかというのはなかなか...
Re:脳のシミュレート性能が本当に試される問題 (スコア:1)
脳を完全にシミュレートすることによって得られた人工知能は、
・教育に１０数年かかる
・しかも、どう教育すれば何が得手になるか制御できない
・その日の気分で性能が変わる
・１６時間働かせると８時間止まる（睡眠）
・働かせすぎると鬱病にかかるかも
という特性も、人間そっくりになってしまうような。
チェス脳 (スコア:2, おもしろおかしい)
Re:チェス脳 (スコア:1)
しかし初代のチェスマシン [wizforest.com]はまじで中に人が入ってて大変そうです。
しかし、人間も相手をコンピュータと意識してる限り、
面白い結果がでないと思うのですが。（または逆）
その人用またはプロ向けに作られてる対策ソフトかもしれないし、
人間側もコンピュータと言う事を意識して打つ。
逆に人間的な要素を取り入れた思考系ソフトが
出たら面白いような気がしますが。
相手の表情や視線をカメラで読みとって相手の手を考えるとか。
または計算に戸惑ってる（藁）ときは相手（?)の表情が変わるとか。
ゲームソフトに良く有りますよね。表情は。
人対人のゲームは、その要素がでかいと思いますが。
確か将棋とか囲碁の視線の研究とか心理学とかはやってましたね。
ストーリー1997～2003 (スコア:2, 参考になる)
ハイエンドPCレベルでの興行が成立したことです。今後、このテのイベントの
再活発化も期待できます。
そのストーリー自体非常に興味深いものですが、脳のシミュレートとは
あんまり関係ないような。
ここ数年の経緯を私なりに要約してみました。それでも長くなってスマソ。
1)1997年、人類史上最強グランドマスター、カスパロフが、チェス用
スーパーコンピュータ、DeepBlueによもやの敗北を喫し、世界を驚かせた。
2)プライドを傷つけられたカスパロフは、DeepBlueをインチキ呼ばわりし、
再戦を要求した。多くの関係者にとっても、1勝3分1敗で迎えた最終局、
カスパロフが定跡書にも「悪手」と書かれた手を指して敗れる、という
不可解な展開であったこともあり、リベンジの機会が待たれた。
3)ところが、人類史上初の栄誉に浴して興行的なモティベーションを十二分に
満たしてしまったIBMが降りてしまい、「チェスしか能がないスパコン」に
大枚をはたくスポンサーも他に現れなかった。
4)その一方、コンピュータチェスの研究はIBMに関係なく継続され、ハードも
進歩し続けた。結果、チェスPCソフトが充分に強くなった。
5)今回のニューヨーク対決実現。ただし計画の度重なる延期・変更は、
実現までの紆余曲折を連想させる。
6)引き分けはまずまず妥当な結果か。
完全読み (スコア:1)
たぶん先手でも後手でも、人間は、自滅して、まける。
I am grateful to everyone and you.
Re:完全読み (スコア:1)
# ぐらいなイメージ？＜練習問題レベル？
Copyright (c) 2001-2014 Parsley, All rights reserved.
Re:完全読み (スコア:2, 参考になる)
「先手、後手ともに最善手を打ち続けた場合、何目の差が出るか」
が科学的に証明されたら「コミは何目がいいのか」という
囲碁界の大問題が解決してありがたいことになるかと。
コミ変更 (スコア:1)
# 思いつきだけで発言
Copyright (c) 2001-2014 Parsley, All rights reserved.
正しいコミは？ (スコア:1)
そのコミはルールに採用されるべきではないと思います。
少なくとも、人間が囲碁を打つときのルールには。
その数値は、6目半からかなりかけ離れた数値であることもあり得ます。
その場合、かえって黒番勝率が5割から大きく乖離してしまい、不公平になるでしょう。
現実のプレイヤーがすべてを読み切れない以上、統計的に勝率5割に
もっとも近いコミを採用し続けるのが、結果的にもっとも「公平」だと思います。
日本では6目半への移行が決まったばかりですが、これが公平かどうかは、
やってみなきゃわからない、というところでしょう。
不完全性定理 (スコア:1)
「先手・後手の、どちらがかが必ず勝つのかを証明できないゲームが存在する」
は、既に証明されています。
#これが、チェス・将棋・囲碁に適用されるかは、また別命題ですが（^^；。
「勝てない手順が存在する」は、直感的には理解出来ます。証明は難しいでしょうが…。
閑話休題
Re:不完全性定理 (スコア:1)
チェスに必勝法が存在することは証明されていたような...
...芸というものは一生勉強だと思っています...
Re:不完全性定理 (スコア:1)
五目並べ（連珠）は先手必勝が証明されてますね。
参考リンク
http://www.cs.vu.nl/~victor/thesis.html
ツェルメロの定理 (スコア:1)
すみません。1912年にツェルメロによって証明されているのは、こうでした。
...芸というものは一生勉強だと思っています...
計算機代表がDEEP JUNIORという最強のプログラム (スコア:1)
Re:計算機代表がDEEP JUNIORという最強のプログラム (スコア:1)
Re:計算機代表がDEEP JUNIORという最強のプログラム (スコア:1)
さらに原文を探ると。。。$50の商用版はPCで動作とのこと。
今回はマルチプロセッサー対応版だそうな。詳細が気になるなあ。。
Re:計算機代表がDEEP JUNIORという最強のプログラム (スコア:1, 参考になる)
脳のシミュレートと云っても。 (スコア:1)
--rena
Re:脳のシミュレートと云っても。 (スコア:1)
非互換性は当然あると思われます。
それに加え、中身もほとんどの部分が非互換であるはずです。
もし脳内での知識の表現に互換性があると仮定すると、この世の
あらゆる事象に対応する表現パターンがあらゆる人の脳内で事前に
規定されていなければなりません。
たとえば私以外誰も絶対に知らない知識であっても、他の人がそれを
（無意識のうちに）知識として持っているということになります。
そうでないと、私がその知識を他人に伝えても、私とその人との間で
脳内での表現に非互換が生じるはずです。
さらに、その知識に対する理解度や、その人が使う言語によっても
表現は変わると考える方が自然ですよね。
したがって、脳の互換性は非常に低いものと思われます。
チェスなんて (スコア:1)
おおよそ0が120個くらいの数しか指手のパターンがないのです。
人間の思考パターンの数に比べれば、
0がいくら少ないかまだまだ想像もつきません。
超頭が固くて保守的なウチの両親の思考パターンくらいなら、
もしかするとワタシが生きている間に、
完全シミュレーションが可能になるかもしれませんが。
（でも、あまりに頭が固すぎて、こっちが考えも付かないことを
言い出すことあるからなあ）
おれいっつも思うんだけど、 (スコア:1, おもしろおかしい)
そういう戦法って反則だと思わない？
Re:おれいっつも思うんだけど、 (スコア:1)
コンピュータ相手に心理戦を展開する人類代表のほうが反則かもしれません。
#引き分けを受け入れたのは、コンピュータだろうか、コンピュータ使いの方だろうか
Re:おれいっつも思うんだけど、 (スコア:1)
/* いちゃもん
Re:おれいっつも思うんだけど、 (スコア:1)
読めない局面で迷った時は、
俺に分からんのだから相手に分かるはずがない。ならば、
そこに持ち込めば俺が先に読み切るので勝ち
と思ってその手にする
とか（出典は記憶になし…誰か補完してくれるとうれしい）。
計算機は定石データベースにない手、以上の認識はしそうにないので
張り合いがなさそうです。
対計算機の手として、人間には結果は明白なのに、計算機的には
非常に広く深く読み進めないと切り捨てが困難な手順とかが
そのうち考案されたりするのかな？でも考え付く方が大変か…
Re:おれいっつも思うんだけど、 (スコア:1)
勝ったはずです。全体としては負けましたけど。
Re:コンピュータの中の人も大変だろうな (スコア:1)
やっぱり、大きさと言えば天童市 [tendocci.com]だと。＜物理的大きさで比べてどーするっ
Copyright (c) 2001-2014 Parsley, All rights reserved.
Re:実は激しく計算してるのは (スコア:1)
ちょっぴし茶々モードです．
潜在意識って観測不可能なものですよね? 観測不可能なもの(または観測限界ギリギリのもの)を 論拠に持ってくるのは技術屋や科学屋さんのやることでは ないと思います．
Koichi
Re:実は激しく計算してるのは (スコア:1, 参考になる)
１０を知って１へ (スコア:1)
資料持ち込みOKの試験みたいになってきましたね。
# 出題者のセンスが問われてきそうな風味
Copyright (c) 2001-2014 Parsley, All rights reserved.
Re:カスパロフがプログラムを (スコア:1)
どっちが勝つか？