- ヨセ 総合スレ
219 ：名無し名人[]：2018/08/27(月) 15:11:39.01 ID:bf//Iake - > 216
ご教授ありがとうございます。当該書籍はまだ見ていませんが、Berlekampでを検索して
いろいろたどったところ、興味深い論文をたくさん見つけることができました。
というか、最初からGoogle Scholarで「go endgame」で検索してれば
よかったのだと後悔してます、「囲碁 ヨセ」じゃ全然だめでしたねww。
いくつかの論文のAbstractを読んだところですが、結構（個人的には）
驚くべきことが数学的に証明されているようでした。
囲碁のヨセのように、ゲームの分岐を、それぞれの部分の
小さなゲーム木に分解することができるゲーム（Sum of games）の性質ですが、
囲碁で言うと
(1) それぞれのヨセの打ち方と、そのときの出入りの目数が完全にわかっている
(2) それぞれのヨセは完全に独立して他に影響を及ぼさない
(3) 各ヨセの打ち方は一通りしかない
（打ち方によって後手8目、または先手6目の寄せ方を選べる、といったことはない）
(4) 各ヨセは高々２手で終わる
（高々、黒黒、黒白、白黒、白白の４通りが最大分岐数）
(5) もちろんコウとかはない
という、現実の囲碁のヨセより相当簡単と思われる制限を置いたときでさえ、
最善手探索問題の複雑さは、PSPACE完全かつNP困難ということでした。
要するに厳密な最善を探すためには、すべてを読み尽くす以外の方法はなさそう、
ということになります。
(4)の2手の制限を、1手にすると、要するに後手ヨセしかない局面で、
大きい順に打つのが最善であることは自明になります。
2手だと原始的な先手・後手がうまれます。3手ぐらいにすれば、
もしかしたらNP困難性とか証明できるかも、くらいに思っていたのですが、
2手で十分だった、ということで驚きました。
まあ、とはいえ実践的に言えることは「２倍法とか、手番の価値とか、絶対計算とか
いろいろ持ち出しても、所詮近似に過ぎず、本当の最善は読み尽くしてみないと
一般的にはわからない」という、至極常識的なものになるのですが・・・
|