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

**すらいむ ★** · 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
これで解決と言えるのかね
弱解決とは言っていいみたいだけど

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

ユークリッド盤面から非ユークリッド盤面に変更しよう

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

シェイクスピアやろ、そこは…

**名無しのひみつ** · 2023/11/08(水) 04:42:18.88

初期盤面の真ん中4マスやめて、碁みたいに自由な場所に一枚ずつ置いていけるようにするのはどうか
で白と黒が隣り合ってしまったらそこから普通のオセロがスタート

**名無しのひみつ** · 2023/11/08(水) 05:04:00.82

複雑にするため、一回だけパスできるようにする。これは大変だよ!

**名無しのひみつ** · 2023/11/08(水) 05:06:19.93

理論的には将棋　囲碁も必勝法あるんだよな。

**名無しのひみつ** · 2023/11/08(水) 05:09:53.31

あたり

**名無しのひみつ** · 2023/11/08(水) 09:56:37.33

>>55
負けないような最善手を指し続けた場合、引き分け的な結果にしかならんかもしれん

**名無しのひみつ** · 2023/11/08(水) 13:27:04.86

>>55
> 理論的には将棋　囲碁も必勝法あるんだよな。

敗勢濃厚なときには…

将棋の場合
　盤を180度回転させる

囲碁の場合
　相手と自分の碁笥を入れ替える

**名無しのひみつ** · 2023/11/08(水) 15:01:58.27

相手殴りつけるのはダメか

**名無しのひみつ** · 2023/11/08(水) 21:23:58.37

８ｘ８ではなくて６ｘ１０ではどうかな。

**名無しのひみつ** · 2023/11/08(水) 21:28:31.39

>>29
俺も思った

**名無しのひみつ** · 2023/11/08(水) 21:29:00.64

盤面をn * nに拡張しても同じだろ？

**名無しのひみつ** · 2023/11/09(木) 02:49:51.13

着手のパターンは広いけど、終わるまでの手数は必ず60手で終わる。
定石16手と積みエンジン32手ぐらい読んだら、かなり狭くなってくるよね。

**名無しのひみつ** · 2023/11/09(木) 23:38:33.37

まだ論文の査読も検証もされてないがな

まあ俺もこの分野の研究をしてる人間の一人だが
俺が読んだ限り今のところ誤りは見つけられてない

**名無しのひみつ** · 2023/11/09(木) 23:46:00.67

>>64
弱解決ってどの程度の評価なの?
片側は常に最善の手という制約みたいだけど
最善の手というのは評価関数で決めるだけだから
本当のところは分かってないのが弱解決なんだよね?
評価関数がある程度正しいことが分かってるから
ほぼ間違いないのではないかという話と理解して良い?

**名無しのひみつ** · 2023/11/10(金) 08:21:14.39

盤面の最初を、黒も白も対角にもっとも外の角の位置に石を置いてからと思ったが、それだとどうなるのだろうか。
今は初期状態を中央に黒も白も対角に置いて始めるけれども。

**名無しのひみつ** · 2023/11/10(金) 18:24:09.36

>>30
言葉の使い方を知らないんだろうね

**名無しのひみつ** · 2023/11/11(土) 09:40:49.68

TikTok LiteでPayPayやAmazonギフトなどに交換可能な4000円分のポイントをプレゼント中！
※既存TikTokユーザーの方はTikTokアプリからログアウトしてアンインストールすれば参加できる可能性があります。

1.SIMの入ったスマホ・タブレットを用意する
2.以下のTikTok Litのサイトからアプリをダウンロード（ダウンロードだけでまだ起動しない）
https://lite.tiktok.com/t/ZSNfeYxHq/
3.ダウンロード完了後、もう一度上記アドレスのリンクからアプリを起動
4.アプリ内でTikTok未使用の電話番号かメールアドレスを使用して登録
5.10日間連続チェックインで合計で4000円分のポイントゲット

ポイントはPayPayやAmazonギフト券に交換可能！
家族・友人に紹介したり通常タスクをこなせば更にポイントを追加で獲得できます。

**名無しのひみつ** · 2023/11/11(土) 10:33:02.18

>>68
ポイント大杉じゃね？

**名無しのひみつ** · 2023/11/11(土) 15:55:33.84

>>37
囲碁はハンデのコミが無ければだろ。
コミ6.5目なら白必勝かもな。それか、黒が負けを避けて３コウの引き分けという結論か。

**名無しのひみつ** · 2023/11/12(日) 10:47:03.29

>>67
そもそも理解してないのでは?

**名無しのひみつ** · 2023/11/12(日) 22:12:34.89

量子コンピュータだと一瞬で解けたりしないの？
アルゴリズム開発できない？

**名無しのひみつ** · 2023/11/12(日) 22:47:46.87

>>68
簡単で良いな

**名無しのひみつ** · 2023/11/26(日) 00:59:20.65

8x8で勝負がついたら負けた方が勝負を続けるか選択できる。
掛け金を2倍にして周囲に2列増やした12x12に盤面を広げてゲームを続行できる。
負け分を払って続行しない選択もできる。
12x12で勝負がついたら．．（以下繰り返し。青天井？）

「圧倒的勝利をしてしまってはダメなんだ。
　適度に手を抜いて相手に「勝てるかも」と思わせてゲームを続行させるのが肝。」
みたいな。

あ、最終局面全部黒とか続行不可のケースもあるな。

**名無しのひみつ** · 2023/11/26(日) 01:01:41.36

あ、勝負師がわざと負けて掛け金を莫大にしてから勝つでいいのか。

**名無しのひみつ** · 2023/11/26(日) 08:57:37.90

チクタクトーと同じで両者が最善手を打つと引き分けだとすれば、
やってもしょうが無いゲームだということになる。

**名無しのひみつ** · 2023/11/26(日) 12:57:47.55

永久機関とかフリーエネルギーと
https://www.google.com/search?q=%E7%89%B9%E8%A8%B1+%E6%B0%B8%E4%B9%85%E6%A9%9F%E9%96%A2+%E5%87%BA%E9%A1%98%E4%BB%B6%E6%95%B0

人口が増えると無駄にエネルギーを消費するので
地球で採掘する原子の枯渇を早めますね!

リサイクルを使用とも数%は・・・

引いていえば宇宙を維持するエネルギーも最後は枯渇する!

**名無しのひみつ** · 2023/11/26(日) 13:33:34.16

>>23
早期終局じゃなきゃあ最後に打つ手には選択の余地ないし、黒にも早期終局勝ちは可能

**名無しのひみつ** · 2023/11/29(水) 20:00:51.68

なんでも解明されてしまう、つまらない世の中になったもんだ。

**名無しのひみつ** · 2023/11/30(木) 12:53:02.33

一箇所、そこには打ってはいけない場所を設けると、それでもってゲームが代わる。
あるいは白でもない黒でもない、たとえば赤いコマを置いて置くのでも同じ。

**名無しのひみつ** · 2023/12/07(木) 08:57:09.79

>>65
強解決の意味は
・その段階では最善手を選ばなくても後で取り返して勝つ方法を見つける
あるいは
・最善手を選ばないと負けることが証明できる
なんじゃないかな

**名無しのひみつ** · 2023/12/09(土) 19:19:22.09

双方最善を指してたらいつか将棋も振り駒で勝敗が決まっちまうのか

**名無しのひみつ** · 2024/01/10(水) 18:45:18.96

引き分けが存在するゲームはほぼほぼ引き分けやろ

**名無しのひみつ** · 2024/01/10(水) 19:09:53.28

引き分けが存在しても囲碁やオセロのように数で勝ち負けが決まるものは
解かれてしまった後は引き分けラインを動かすことで先後の公平を期す事ができる
あるいは勝ち負けを必ずつけたい場合は囲碁の0.5目のように勝敗ラインを設定することもできる
但しこれはゲームの本質に影響を与えるものではなく大会や統括組織下で設定するもの

**名無しのひみつ** · 2024/01/12(金) 00:16:28.28

オセロのゲームの根本を変えて、
最後に残った自分の色のコマが少ない
側が勝ち、とルールを変更したらどうなる
だろうか？

**名無しのひみつ** · 2024/01/12(金) 00:40:29.31

黒有利なはず

**名無しのひみつ** · 2024/01/14(日) 15:34:19.88

弱解決
初期局面の勝敗が解明されていて
それを証明するために必要な各局面の最善手も分かってる

この定義を読んでも意味が分からなかったが
「ゲームの解決　田中哲朗」の縦横だけの五目並べの弱解決の証明をｙ院でやっと意味が分かった

拙い言葉で言い換えると
各局面でどうやればいいかの戦略があり
その戦略によってどちらかが勝つ
あるいは引き分けに持ち込める事が分かっており
それを避けることは出来ない
ということか

定義を読んでも理解できなかったのは
オセロには縦横五目並べみたいな単純な戦略がないと思っていたから
実際に単純ではなくて暗記出来ないほど複雑な戦略なんだろうけど

**名無しのひみつ** · 2024/01/14(日) 15:35:15.16

>>87
ｙ院で→読んで

**名無しのひみつ** · 2024/01/14(日) 15:38:10.64

けどそういう事が分かるのであれば
強解決ではないのだからブルートフォース的解決でないのは当然だけど
比較的単純な計算パワーの解決でもはなくて
オセロの特徴に特化した証明になってるはず

**名無しのひみつ** · 2024/01/14(日) 15:58:49.98

奇数にしておけば、引き分けなんて起こらなかったのに。
とは言え、先攻・後攻で平等にするには偶数にするしかないのだが。
後は、囲碁のようにコミあり（0.5とか）にすれば必ず勝負が着いたかな。

**名無しのひみつ** · 2024/01/14(日) 17:44:08.44

>>85
それって後手が最後にひっくり返して同数になるのが最善手（そうでないとパスになる）だから必ず後手勝利だろ

**名無しのひみつ** · 2024/01/14(日) 18:40:28.04

>>87
うまく日本語に出来なかったが
こう書けば正確かな

各局面でどうやればいいかの戦略があり
その戦略によって
　先手後手のどちらかが勝つ
　どちらにも勝つ方法がない場合でも引き分けに持ち込め
避けることは出来ない

**名無しのひみつ** · 2024/01/15(月) 10:13:01.06

https://i.imgur.com/zUnRAXH.jpg

**名無しのひみつ** · 2024/01/15(月) 18:46:59.72

>>93
壺注意

**名無しのひみつ** · 2024/01/16(火) 13:59:16.81

まるばつが引き分けるのと同じだｒ

**名無しのひみつ** · 2024/01/16(火) 23:35:17.61

5木並べ（連珠と違って、先手3－3、長連禁止とかが無い単純な場合）に
先手に必勝法があるということは江戸時代に既に発見されていたというね。