AtCoder社のchokudai(高橋 直大) さんが、競技プログラミングで上位に上がるためにどのようにすれば良いかということについて興味深いツイートをされている。言うまでもなくchokudaiさんは、AtCoderという競技プログラミングの国内最大級のサイトを運営されているだけではなく、ICFPC優勝4回等など競技プログラミングの世界ランカーでもある。
https://twitter.com/chokudai/status/1101139927629086720
https://twitter.com/chokudai/status/1101145431961100288
上記のツイートのなかには「全知」と「全能」という言葉が出てくる。
将棋で言うと「全知」とはすべての局面の正解手を知っているということである。これには無限に近い記憶容量が必要となる。将棋の場合、考えられうる局面数は、10の220乗通りとも言われている。初期局面から現実的に到達しうるのは、そのうち10の60乗ぐらいかも知れないが、それにしても、宇宙の原子の数が10の80乗程度なので原子1個1個をフル活用して記憶させたところで足りるのかどうかすら怪しい。
そんなわけで我々生身の人間が「全知」を目指すと言っても、実際には記憶容量はごく限られているので、現実的には、何らか類似性や冗長性、反復性などを利用して圧縮しながら記憶していくこととなる。
もう一方の「全能」のほうは何であろうか？将棋で言うとこれは、無限の計算力を持っているということである。すなわち瞬時に終局までのすべての指し手の組み合わせを計算できるということである。こうなっていれば、何の知識も必要はない。愚直にすべての指し手を調べていけば良いのであるから。
しかし、全知がストレージ的に不可能であるように、全能も計算資源的に不可能である。そこで現実的には、αβ探索など探索の特性を活かして計算量を削減していかなければならない。また、計算資源が有限である以上、なるべく効率的に探索できなければならない。
将棋で言うと「3歩持ったら継ぎ歩に垂れ歩」という格言があるが、これは「もし、3歩持っているなら継ぎ歩に垂れ歩を検討せよ(それが高い確率で正解手である)」というルールベースの知識である。これらは「手筋」とも呼ばれる。
一定の計算資源しか持たない我々が、「全能」を目指そうとするとき、(実際に「全能」ではない我々がなるべく「全能」に近づくように振る舞うためには)その計算量を減らさなければならないので、このような「手筋」と呼ばれる知識を総動員してその計算量を減らしにかかるわけであるな。
こうして考えてみると、我々が「全知」を目指すと言っても、ごく限られたストレージであるから、なるべくストレージの節約が求められ、逆に我々が「全能」を目指すと言っても、無限の計算資源を持たない生身の身体では、なるべく計算量を減らすアプローチが求められるわけであるな。そこが逆説的で面白いと思う。
将棋AIのケースについて考えてみると、将棋AIは、探索(読み)と局面の評価(大局観)と２つの車輪で駆動している。探索には、計算力を用いる。しかし序中盤ではゲーム木の詰みの局面まで読めることは稀なので、詰みではない探索の末尾の局面の形勢を評価しなければならない。この時に評価関数を用いる。これは現在の局面の形勢を大雑把に判断する(期待勝率を事前知識に基づき算出する)ような関数である。人間の大局観に相当する。評価関数の計算にも計算力は必要ではあるが、そこはあまり本質的ではなく、この時に用いる知識の質がどうであるのかという問題のほうが棋力への影響は大きい。評価関数は(あらゆる局面に対応できるように)構造化された知識だと考えられる。
つまり、将棋AIでは「全知」(知識)と「全能」(計算力)のどちらか一方を目指しているのではなく、知識も計算力も限られているPCを用いる以上、その両者を最適に近いバランスに保ちながら(棋力が最大になるように調整しながら)実装されているわけであるな。
これは、競技プログラミングの世界に挑む生身の人間についても同様のことが言えて…などと考えていくと非常に味わい深いのではなかろうか。残念ながら私は競技プログラミングの世界のことはよく知らないのでここで筆を置きたいと思う。
「全知vs全能」とってもキャッチーですね！
どうぶつしょうぎの必勝手順は全知のひとつでしょうか(不要な局面までは知らないでしょうが)。相手の自由な応手による枝葉も含めるとどのくらいの容量になるんでしょうね？
(調べりゃわかるかもしれないけど調べてない)
> 不要な局面までは知らないでしょうが
どうぶつしょうぎは後退解析(すべての詰みの局面からの逆算)なので、初期陣形から到達しうるすべての局面について最善手を持っていたような。2億5千万局面だとか何とか。盤面が小さいわりには、わりとあるなーという感じですが、いまどきのXeonなPCであの盤面サイズなら100Mnpsぐらいは出るでしょうから、だとしたら全幅探索でも3秒で読み切れちゃうじゃん!とか思ったりも。(←計算合ってる？)
わーじゃあどうぶつしょうぎにおいては全知and全能でもあるのか。
どうぶつしょうぎから本将棋までの間を埋める、複雑さが単調に増加する仮想将棋ルールを想定することができれば、本将棋の全知と全能にそれぞれどれだけの資源が必要なのか、計算で求めることができ・・・(笑)
なるほど，私がやってる大きく二つのアプローチがそれぞれ全知と全能を目指していると説明可能な気がしてきました。定跡とクラスタリングに注力するってのは両極と言えますね。全知全能には程遠いですが
全知と全能は対極にあり、本来は片側だけで十分なはずなのに、現実的には、その両方をバランス良く目指すのがベストであるというところがこの問題の興味深いところですね。(｀･ω･´)ｂ
大学生のころ、石取りゲーム（三山崩しの山5つバージョン）の必勝法を考えていました。（当時は三山崩しという名も必勝法についても無知でした）
いろいろと思考を巡らし、
「現在の石の総数がNなら、次の状態の石の総数はNより小さい。つまり石の総数が1からN-1までの
全ての状態において勝ち負けが分かっていれば、石の総数がNのときの勝ち負けがわかる」
「負けの状態から逆行する（どこか1山、石を1個以上増やす）と、それは勝ちの状態である」
と思い以下のアルゴリズムを考えた。
1.全ての状態を「負け」と定義する
2.石の総数が1個であるすべての状態に対して、「負け」であるならば、
その状態からどこか1山、石を増やした状態は「勝ち」と再定義する
3.石の総数を2個、3個と増やしていき、2.と同じように「勝ち」を再定義する。
この方法はうまくいき、必勝法を使うプログラムが作れました。（当時、自分はこのプログラムに勝てませんでしたｗ）
知っての通り、「ニム和」を使った必勝法が存在します。なので、「ニム和」という知識があればこんなことせずとも必勝法が作れます。
私のこのケースは「知識」がなくても「考察力？」で問題を解いた1例でしょう。
最近気になるのが、小学生のプログラミングが必修となり「n個の数の中から最も大きい数を見つけるプログラム」を学んだ小学生が
「n個の数の中から2番目に大きい数を見つけるプログラム」を作れるかどうかですね。
誰でもいいのでやってみてほしいです。
> 私のこのケースは「知識」がなくても「考察力？」で問題を解いた1例でしょう。
典型的なDP(動的計画法)の問題なので、数学的帰納法などを学んだあとなら、思いつくような気も…。
化学だか物理だかで博士号を取ると昔仰ってましたねー
不思議なもんすね、バランス度外視で一点豪華主義な方かと思ってましたが進んでゆくとそこには社会性がほら何と豊かにあります事か。
将棋盤を挟んで人と人が向かい合う「将棋」を人と向き合わないで極めんとするところが如何にもやねさんらしいというか、お変わりなくて何よりです。
全知か全能か、僕たちは限られた時間と能力を何に振り分けて幸福に辿り着くか、みたいなメルヘンチックな事を僕は連想して拝読してました。
ご活躍をいつも励みにしてますよー
やねうらおさんはコンピュータ将棋選手権出場しますが、それの時間配分バランスどんな感じですか？
Stockfishとか機械学習とかの書籍を読む時間と
ソフトの設計コーディング試行錯誤の時間。
前者５０％後者５０％くらいですか？
改良のアイデア考える = 10%
コードを書く = 5%
Stockfishのソースコードを読む、書籍を読む = 5%
学習の実験の設定、実験結果の集計など = 80%
いまのところこんな感じでございます(´ω｀)