「オセロが解決されたとする論文」記事へのコメント

ということは

[Anonymous Coward]

完璧に打つAI相手の勝負では、人間は絶対に勝てないってことか。

Re:

[Anonymous Coward]

どんなに頑張っても引き分けにしかならないですね

映画ウォー・ゲームでは最後三目並べに勝者がいないことを悟ったコンピューターがチェスをやろうと持ち掛けるが、チェス、将棋、囲碁だとどうなるのだろうか?
一応ルール上は全部引き分けのパターンがあるみたいですが

Re:

[Anonymous Coward]

人間が最善ではない手も含めて打った時にそれでも勝てない証明はされてないのでは？

Re:ということは

[Anonymous Crow (45505)]

>人間が最善ではない手も含めて打った時にそれでも勝てない証明はされてないのでは？

両者最善手を打つ場合（弱解決）、片方だけが最善手を打つ場合、共に考慮しているようです
（両者が最善手を打たない場合は考慮されていない（強解決））

（今回の論文の概略）
https://gigazine.net/news/20231106-othello-is-solved/ [gigazine.net]
https://yaneuraou.yaneu.com/2023/11/06/the-surefire-winning-strategy-f... [yaneu.com]

（今回の論文の解説）
https://qiita.com/Nyanyan_Cube/items/a373da3157cdd117afcc [qiita.com]

（弱解決について）
https://www.jstage.jst.go.jp/article/sugaku/65/1/65_0651093/_pdf/-char/ja [jst.go.jp]

>最初の10手の進行について既存のプレイヤーの知識を元にあらかじめ評価値を与えたりすることで計算量を減らし

最初の10手(実質11手?)は人力評価という事でしょうかね？

フリーのAIオセロソフトでも32手目以降は完全読み切りするそうなので
半分打ったところで勝敗が分かってしまうようです
https://www.egaroucid.nyanyan.dev/ja/usage/ [nyanyan.dev]

＃
個人的に凄いと思ったのは、会社の20%ルール（20%の時間は好きな研究していいよ）の中で出した成果、だという事でしょうか

Re:ということは

[Anonymous Coward]

1. 最初の10手をまず既存のオセロソフト(を改造したもの)の評価関数で見積もる。
2. 残り50手を完全読みする(実際にはさらに14手-36手に分割してこの手順を再帰的に適用するようなことをしてるけど省略)
3. 完全読みした評価値と1.の評価値が一致していたので(弱)解決
4. もし一致していなかったら、完全読みした評価値をメモ化して改善された評価関数で1.からの手順を繰り返す

最初から完全読みするのと何が違うのかと言うと、1.で評価しなかった局面(99.9%)については2.の完全読みをしなくて済むので計算量が大幅に節約できる。評価しなかった局面の評価値が違っていても結果に影響がないことはα-β法の原理により保証されている。

Re:

[Anonymous Coward]

トータルの計算量は単純に初手からnull window searchとかpn searchとかした方が少ないんじゃないかな
メモリが大量に必要になるとか並列処理がやりにくいとかで、なんかゴチャゴチャ工夫して現実的な時間で結論まで到達できるようになったと

Re:

[Anonymous Coward]

論文の手法は50マス空きの局面や36マス空きの局面を並列で探索できるのが強みって書いてた

Re:

[Anonymous Coward]

両者最善手を打つ場合（弱解決）

違う。初手以降、先手or後手が常に最善手を打ち続けた場合に結果が定まるのが弱解決。相手が最善手かどうかは関係ない。
両者が最善手のときだけ結果が分かっている場合は超弱解決という。

（両者が最善手を打たない場合は考慮されていない（強解決））

これも違う。ゲーム上に現れうる全ての局面をスタート地点として、その後の先手後手どちらかが最善手を打ち続けた場合の結果がわかることを強解決という。

Re:

[Anonymous Coward]

> （両者が最善手を打たない場合は考慮されていない（強解決））

これが普通の人間同士のゲームです。