【計算機科学】オセロが解決される、双方が最善手を打った場合最終局面は引き分けになることが明らかに [すらいむ★]

**すらいむ ★** · 2023/11/06(月) 21:56:12.79

オセロが解決される、双方が最善手を打った場合最終局面は引き分けになることが明らかに

　2023年10月30日に「オセロが解決された」というタイトルの論文が世界最大のプレプリント(査読前論文)サーバーarXivに投稿されました。
　論文によると、双方が最善手を打った場合の最終局面は引き分けになると述べられています。

　[2310.19387] Othello is Solved
　https://arxiv.org/abs/2310.19387

（以下略、続きはソースでご確認ください）

Gigazine 2023年11月06日 15時10分
https://gigazine.net/news/20231106-othello-is-solved/

**名無しのひみつ** · 2023/11/06(月) 22:00:56.39

何年も前に「先手の必勝パターンが見つかった」みたいなニュースを見たような？

**名無しのひみつ** · 2023/11/06(月) 22:04:11.72

将棋の結論は持将棋だよな
ほぼ確実に

**名無しのひみつ** · 2023/11/06(月) 22:04:39.38

俺は後手が優勢って聞いたがな
まあ引き分けってのはあり得るかな

**名無しのひみつ** · 2023/11/06(月) 22:09:08.30

This document talks about:

- **オセロの弱解決**: この文書は、オセロ（8×8盤）が弱解決されたことを発表する。初期局面の理論値は引き分けであることが証明された。弱解決とは、初期局面から完全な戦略を知ることを意味する。
- **Edaxの改良**: オセロソフトウェアEdaxを改良し、36空きの局面を解くために使用した。Edaxはアルファベータ探索に基づいており、探索効率を向上させるために多くの技術を採用している。特に、探索窓の設定や手順の並べ替えに工夫を凝らした。
- **50空きの局面の選択**: 50空きの局面の中から、2,587局面を選んで仮説を立てた。これらの局面の理論値が仮説通りであれば、初期局面の理論値も仮説通りであることが導かれる。局面の選択には、アルファベータ探索に似たアルゴリズムを用いた。
- **36空きの局面の解決**: 50空きの局面の仮説を検証するために、約1.5億個の36空きの局面を解決した。これらの局面の探索には、約1.5×10^18個の局面を探索する必要があった。探索には、Preferred Networks社のスーパーコンピュータMN-Jを使用した。

**名無しのひみつ** · 2023/11/06(月) 22:10:54.87

こうしたゲームの解析において、解決には「弱解決」と「強解決」という2つの解決の種類があります。「弱解決」は初手から双方が最善手を打った場合にゲームの最終局面がどうなるのかが解明されることで、一方「強解決」はゲームの全ての局面においてその局面から双方が最善手を打つとどうなるのかが解明される事を意味しています。

今回の論文は「弱解決」を扱っており、自分は常に最善手を打つという前提で計算が進められています。相手の手については悪手も計算対象に入っており、先手・後手それぞれで計算を進めたところどちらの手番で始めても「勝つか引き分けになる」という計算結果になりました。従って、双方が最善手を打つと最終局面は引き分けになることが明らかになったというわけです。

**名無しのひみつ** · 2023/11/06(月) 22:16:04.12

局面数ってどうやって計算するの？

>3^(8*8)
= 3433683820292512484657849089281.

>(3^(8*8))/4
= 858420955073128121164462272320.25

小数が出てしまうんだが。

**名無しのひみつ** · 2023/11/06(月) 22:26:40.26

お互い勝つか引き分ける手しか打てないなら、引き分けにしかならなくねぇ？
先攻、後攻の優位差が無いってこといいたいのか？

**名無しのひみつ** · 2023/11/06(月) 22:30:27.04

>>7
4で割ったのは回転したら同じ局面になるのを同じ局面としてカウントするため？

点対称な局面や線対称な局面があるから一律に4で割っちゃいけないんだと思う

**名無しのひみつ** · 2023/11/06(月) 22:30:41.72

>>7
なんでわる

**名無しのひみつ** · 2023/11/06(月) 22:51:54.61

4で割ったのは点対称の分を減らしただけ。台を回転させると同一局面になるから。
線対称は別物として扱う。
しかし存在しない局面を省くと局面数は10^28程度になるというが、どうやって計算したのかが気になる。

**名無しのひみつ** · 2023/11/06(月) 22:54:40.27

勘違いした。点対称ではなく90度ずつ回転させたらと訂正させていただく。

**名無しのひみつ** · 2023/11/06(月) 23:03:36.44

後手で最低でも引き分けになる打ち手があるってことか

**名無しのひみつ** · 2023/11/06(月) 23:54:20.58

>>7
3の累乗は石なし・白・黒を意図したんだろうけど、囲碁と違ってオセロは相手の石を挟む形でしか打てないので必ず一つの大きな島になる
つまり、3のベキでは見積もりが大き過ぎる

÷4は回転対称を意図したんだろうけど、90°でなく180°もあり得るし、回転対称でなく鏡像もあり得るし、対象性がないかもしれない
つまり、÷4では見積もりが小さすぎる

数え上げの方針としては4×4盤面で90°回転対称を数え上げ、4×8盤面で180°回転対称と鏡像を数え上げ、8×8盤面で対称性のないものを数え上げる

**名無しのひみつ** · 2023/11/07(火) 00:08:32.58

白い方が勝つわ

**名無しのひみつ** · 2023/11/07(火) 00:10:44.53

最近どっちも見かけないな

**名無しのひみつ** · 2023/11/07(火) 01:01:16.99

白黒つかなかったか

**名無しのひみつ** · 2023/11/07(火) 03:19:44.16

てことは>>1の棋譜を覚えておけば絶対に負けはないってことか
昔からつまらなそうとは思ってたけどマジでつまらｎゲームだなｗ

**名無しのひみつ** · 2023/11/07(火) 03:28:33.60

4x4と6x6のオセロはいずれも後手（白）の必勝だから面白い

**名無しのひみつ** · 2023/11/07(火) 03:30:56.06

実際の局面では後手が勝つ場面が多いと言われているから、
先手が巧みに打ちこなすと引き分けに持っていけると言った感じだろうな

**名無しのひみつ** · 2023/11/07(火) 03:51:23.16

Othelloっていう単語は海外で通用しないはずだが論文のタイトルに使っていいんだろうか？

**名無しのひみつ** · 2023/11/07(火) 06:02:03.60

オセロ(リバーシ)の解決かあ
計算の歴史がまたひとつ進んだ

**名無しのひみつ** · 2023/11/07(火) 06:06:01.66

>>2
黒の1手目は対称性からどこ打っても同じだよね。
で白の方が有利って言われてたよね。
順に打てたら最後に打てるからかな。

**名無しのひみつ** · 2023/11/07(火) 06:12:34.90

>>8
その部分の情報だけなら「最後に打てる方が勝つ」じゃね？　

**名無しのひみつ** · 2023/11/07(火) 06:30:23.96

>>18
相手がその棋譜通りに打つとは限らん。　

**名無しのひみつ** · 2023/11/07(火) 07:49:29.16

次はチェスだ

**名無しのひみつ** · 2023/11/07(火) 08:22:40.89

>>21
日本人が作ったゲームなのに欧米に寄せた名前を付けて
しかもそれが海外で通用しないとは情けないな

**名無しのひみつ** · 2023/11/07(火) 08:32:17.52

>>27
×日本人が作った
◯日本人が名付けた

オセロは昔からあるリバーシ（日本に伝来した当時の名前は源平碁）のサブセット

**名無しのひみつ** · 2023/11/07(火) 08:35:17.49

○×ゲームと同じようなもんか

**名無しのひみつ** · 2023/11/07(火) 11:08:52.88

やねうらおがこのネタで必勝法見つかるみたいな見出しにしててゲンナリした

**名無しのひみつ** · 2023/11/07(火) 14:20:25.54

オセロ以前から欧米でリバーシという同じゲームがあったよ
>>27

**名無しのひみつ** · 2023/11/07(火) 16:18:35.19

先攻め後攻めの勝率が5割のゲームってあるの？
ある場合はこのような最善手を踏み続けると引き分けになるもんなん？

**名無しのひみつ** · 2023/11/07(火) 16:37:08.09

fjtちゃうんか

**名無しのひみつ** · 2023/11/07(火) 17:17:52.35

とうとう8x8オセロが完全解析されたのか…
盤面を拡張して10x10にしよう

**名無しのひみつ** · 2023/11/07(火) 17:23:50.18

将棋とか囲碁に比べたら単純だからそうだろうな

**名無しのひみつ** · 2023/11/07(火) 17:24:04.42

>>34
ほんと研究者は鬼畜だぜ

**名無しのひみつ** · 2023/11/07(火) 17:44:41.78

マジかよ。また一つのゲームが終わっちまったな
チェスも多分引き分けだと思う
将棋と碁と連珠は先手必勝だろうな　多分

**名無しのひみつ** · 2023/11/07(火) 18:06:10.87

4×4や6×6は後手必勝だったな。
昔は達人やコンピュータの対戦成績から
後手必勝かも？と言われた時代もあったが

遂に全局面の探索が終わったんだな。
引き分けとは驚いた。

**名無しのひみつ** · 2023/11/07(火) 18:06:24.77

4×4や6×6は後手必勝だったな。
昔は達人やコンピュータの対戦成績から
後手必勝かも？と言われた時代もあったが

遂に全局面の探索が終わったんだな。
引き分けとは驚いた。

**名無しのひみつ** · 2023/11/07(火) 18:13:37.54

>>34
100×100とかどうかな

**名無しのひみつ** · 2023/11/07(火) 18:13:41.03

あれ？　全局面ではないのか。

**名無しのひみつ** · 2023/11/07(火) 19:02:54.56

１０ｘ１０の盤面にすればまだ楽しめるじゃん
それがだめなら１２ｘ１２、１４ｘ１４と増やせばいい

**名無しのひみつ** · 2023/11/07(火) 20:49:36.28

>>21
オセロットぐらいしか
思い浮かばんな

**名無しのひみつ** · 2023/11/07(火) 21:05:06.41

オセロ合意

**名無しのひみつ** · 2023/11/07(火) 21:05:22.54

オセロ合意

**名無しのひみつ** · 2023/11/07(火) 21:05:31.65

オセロ合意

**名無しのひみつ** · 2023/11/07(火) 21:31:25.48

まだ2nx2nやn次元オセロの一般解が未解決だから、数十年は楽しめるよ。

**名無しのひみつ** · 2023/11/07(火) 21:33:14.07

球面オセロとかトーラス型オセロとか、数学は鬼畜だ。

**名無しのひみつ** · 2023/11/07(火) 21:40:10.50

ルール外だけど初期位置によってどうなるかも知りたいな

**名無しのひみつ** · 2023/11/07(火) 21:46:47.43

>>41
これで解決と言えるのかね
弱解決とは言っていいみたいだけど