23/11/06 21:56:12.79 ZP9wTHrI.net
オセロが解決される、双方が最善手を打った場合最終局面は引き分けになることが明らかに
2023年10月30日に「オセロが解決された」というタイトルの論文が世界最大のプレプリント(査読前論文)サーバーarXivに投稿されました。
論文によると、双方が最善手を打った場合の最終局面は引き分けになると述べられています。
[2310.19387] Othello is Solved
URLﾘﾝｸ(arxiv.org)
（以下略、続きはソースでご確認ください）
Gigazine 2023年11月06日 15時10分
URLﾘﾝｸ(gigazine.net)
2:名無しのひみつ
23/11/06 22:00:56.39 CLIeic8x.net
何年も前に「先手の必勝パターンが見つかった」みたいなニュースを見たような？
3:名無しのひみつ
23/11/06 22:04:11.72 9udymhAp.net
将棋の結論は持将棋だよな
ほぼ確実に
4:名無しのひみつ
23/11/06 22:04:39.38 o2cCAv7W.net
俺は後手が優勢って聞いたがな
まあ引き分けってのはあり得るかな
5:名無しのひみつ
23/11/06 22:09:08.30 oIrg942I.net
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を使用した。
6:名無しのひみつ
23/11/06 22:10:54.87 oIrg942I.net
こうしたゲームの解析において、解決には「弱解決」と「強解決」という2つの解決の種類があります。「弱解決」は初手から双方が最善手を打った場合にゲームの最終局面がどうなるのかが解明されることで、一方「強解決」はゲームの全ての局面においてその局面から双方が最善手を打つとどうなるのかが解明される事を意味しています。
今回の論文は「弱解決」を扱っており、自分は常に最善手を打つという前提で計算が進められています。相手の手については悪手も計算対象に入っており、先手・後手それぞれで計算を進めたところどちらの手番で始めても「勝つか引き分けになる」という計算結果になりました。従って、双方が最善手を打つと最終局面は引き分けになることが明らかになったというわけです。
7:名無しのひみつ
23/11/06 22:16:04.12 oIrg942I.net
局面数ってどうやって計算するの？
>3^(8*8)
= 3433683820292512484657849089281.
>(3^(8*8))/4
= 858420955073128121164462272320.25
小数が出てしまうんだが。
8:名無しのひみつ
23/11/06 22:26:40.26 IvfKhl7P.net
お互い勝つか引き分ける手しか打てないなら、引き分けにしかならなくねぇ？
先攻、後攻の優位差が無いってこといいたいのか？
9:名無しのひみつ
23/11/06 22:30:27.04 CDqYohsX.net
>>7
4で割ったのは回転したら同じ局面になるのを同じ局面としてカウントするため？
点対称な局面や線対称な局面があるから一律に4で割っちゃいけないんだと思う
10:名無しのひみつ
23/11/06 22:30:41.72 MwGb715t.net
>>7
なんでわる
11:名無しのひみつ
23/11/06 22:51:54.61 oIrg942I.net
4で割ったのは点対称の分を減らしただけ。台を回転させると同一局面になるから。
線対称は別物として扱う。
しかし存在しない局面を省くと局面数は10^28程度になるというが、どうやって計算したのかが気になる。
12:名無しのひみつ
23/11/06 22:54:40.27 oIrg942I.net
勘違いした。点対称ではなく90度ずつ回転させたらと訂正させていただく。
13:名無しのひみつ
23/11/06 23:03:36.44 xq/rrIqu.net
後手で最低でも引き分けになる打ち手があるってことか
14:名無しのひみつ
23/11/06 23:54:20.58 DnYqqLh5.net
>>7
3の累乗は石なし・白・黒を意図したんだろうけど、囲碁と違ってオセロは相手の石を挟む形でしか打てないので必ず一つの大きな島になる
つまり、3のベキでは見積もりが大き過ぎる
÷4は回転対称を意図したんだろうけど、90°でなく180°もあり得るし、回転対称でなく鏡像もあり得るし、対象性がないかもしれない
つまり、÷4では見積もりが小さすぎる
数え上げの方針としては4×4盤面で90°回転対称を数え上げ、4×8盤面で180°回転対称と鏡像を数え上げ、8×8盤面で対称性のないものを数え上げる
15:名無しのひみつ
23/11/07 00:08:32.58 j/mUV19n.net
白い方が勝つわ
16:名無しのひみつ
23/11/07 00:10:44.53 MN1j+dRH.net
最近どっちも見かけないな
17:名無しのひみつ
23/11/07 01:01:16.99 6aIQeLp/.net
白黒つかなかったか
18:名無しのひみつ
23/11/07 03:19:44.16 6QL1hg+q.net
てことは>>1の棋譜を覚えておけば絶対に負けはないってことか
昔からつまらなそうとは思ってたけどマジでつまらｎゲームだなｗ
19:名無しのひみつ
23/11/07 03:28:33.60 vbayjP+t.net
4x4と6x6のオセロはいずれも後手（白）の必勝だから面白い
20:名無しのひみつ
23/11/07 03:30:56.06 vbayjP+t.net
実際の局面では後手が勝つ場面が多いと言われているから、
先手が巧みに打ちこなすと引き分けに持っていけると言った感じだろうな
21:名無しのひみつ
23/11/07 03:51:23.16 u+/0aJrE.net
Othelloっていう単語は海外で通用しないはずだが論文のタイトルに使っていいんだろうか？
22:名無しのひみつ
23/11/07 06:02:03.60 UdsvuFDw.net
オセロ(リバーシ)の解決かあ
計算の歴史がまたひとつ進んだ
23:名無しのひみつ
23/11/07 06:06:01.66 BLN9FfUy.net
>>2
黒の1手目は対称性からどこ打っても同じだよね。
で白の方が有利って言われてたよね。
順に打てたら最後に打てるからかな。
24:名無しのひみつ
23/11/07 06:12:34.90 BLN9FfUy.net
>>8
その部分の情報だけなら「最後に打てる方が勝つ」じゃね？
25:名無しのひみつ
23/11/07 06:30:23.96 BLN9FfUy.net
>>18
相手がその棋譜通りに打つとは限らん。
26:名無しのひみつ
23/11/07 07:49:29.16 j72sEzKG.net
次はチェスだ
27:名無しのひみつ
23/11/07 08:22:40.89 zqfgmPvO.net
>>21
日本人が作ったゲームなのに欧米に寄せた名前を付けて
しかもそれが海外で通用しないとは情けないな
28:名無しのひみつ
23/11/07 08:32:17.52 ik42to4f.net
>>27
×日本人が作った
◯日本人が名付けた
オセロは昔からあるリバーシ（日本に伝来した当時の名前は源平碁）のサブセット
29:名無しのひみつ
23/11/07 08:35:17.49 r4wnI99c.net
○×ゲームと同じようなもんか
30:名無しのひみつ
23/11/07 11:08:52.88 0c80TQCv.net
やねうらおがこのネタで必勝法見つかるみたいな見出しにしててゲンナリした
31:名無しのひみつ
23/11/07 14:20:25.54 bfJGngaR.net
オセロ以前から欧米でリバーシという同じゲームがあったよ
>>27
32:名無しのひみつ
23/11/07 16:18:35.19 eNGQlIRQ.net
先攻め後攻めの勝率が5割のゲームってあるの？
ある場合はこのような最善手を踏み続けると引き分けになるもんなん？
33:名無しのひみつ
23/11/07 16:37:08.09 6LNihabj.net
fjtちゃうんか
34:名無しのひみつ
23/11/07 17:17:52.35 GuYtM2Ha.net
とうとう8x8オセロが完全解析されたのか…
盤面を拡張して10x10にしよう
35:名無しのひみつ
23/11/07 17:23:50.18 T1Un15/I.net
将棋とか囲碁に比べたら単純だからそうだろうな
36:名無しのひみつ
23/11/07 17:24:04.42 CfCnYElj.net
>>34
ほんと研究者は鬼畜だぜ
37:名無しのひみつ
23/11/07 17:44:41.78 4Gg5WPI4.net
マジかよ。また一つのゲームが終わっちまったな
チェスも多分引き分けだと思う
将棋と碁と連珠は先手必勝だろうな 多分
38:名無しのひみつ
23/11/07 18:06:10.87 bMSoc/+m.net
4×4や6×6は後手必勝だったな。
昔は達人やコンピュータの対戦成績から
後手必勝かも？と言われた時代もあったが
遂に全局面の探索が終わったんだな。
引き分けとは驚いた。
39:名無しのひみつ
23/11/07 18:06:24.77 bMSoc/+m.net
4×4や6×6は後手必勝だったな。
昔は達人やコンピュータの対戦成績から
後手必勝かも？と言われた時代もあったが
遂に全局面の探索が終わったんだな。
引き分けとは驚いた。
40:名無しのひみつ
23/11/07 18:13:37.54 1Xdm+BUu.net
>>34
100×100とかどうかな
41:名無しのひみつ
23/11/07 18:13:41.03 bMSoc/+m.net
あれ？ 全局面ではないのか。
42:名無しのひみつ
23/11/07 19:02:54.56 YUkXV8SQ.net
１０ｘ１０の盤面にすればまだ楽しめるじゃん
それがだめなら１２ｘ１２、１４ｘ１４と増やせばいい
43:名無しのひみつ
23/11/07 20:49:36.28 L3n9Ub0T.net
>>21
オセロットぐらいしか
思い浮かばんな
44:名無しのひみつ
23/11/07 21:05:06.41 ffA+f6fB.net
オセロ合意
45:名無しのひみつ
23/11/07 21:05:22.54 ffA+f6fB.net
オセロ合意
46:名無しのひみつ
23/11/07 21:05:31.65 ffA+f6fB.net
オセロ合意
47:名無しのひみつ
23/11/07 21:31:25.48 2acfMjXL.net
まだ2nx2nやn次元オセロの一般解が未解決だから、数十年は楽しめるよ。
48:名無しのひみつ
23/11/07 21:33:14.07 2acfMjXL.net
球面オセロとかトーラス型オセロとか、数学は鬼畜だ。
49:名無しのひみつ
23/11/07 21:40:10.50 zD6ifLdX.net
ルール外だけど初期位置によってどうなるかも知りたいな
50:名無しのひみつ
23/11/07 21:46:47.43 uxB+f5p0.net
>>41
これで解決と言えるのかね
弱解決とは言っていいみたいだけど
51:名無しのひみつ
23/11/07 22:53:08.93 tpJsEttw.net
ユークリッド盤面から非ユークリッド盤面に変更しよう
52:名無しのひみつ
23/11/07 23:36:00.65 0c80TQCv.net
シェイクスピアやろ、そこは…
53:名無しのひみつ
23/11/08 04:42:18.88 Gt/c447z.net
初期盤面の真ん中4マスやめて、碁みたいに自由な場所に一枚ずつ置いていけるようにするのはどうか
で白と黒が隣り合ってしまったらそこから普通のオセロがスタート
54:名無しのひみつ
23/11/08 05:04:00.82 Y4CNuQwY.net
複雑にするため、一回だけパスできるようにする。これは大変だよ!
55:名無しのひみつ
23/11/08 05:06:19.93 Y4CNuQwY.net
理論的には将棋 囲碁も必勝法あるんだよな。
56:名無しのひみつ
23/11/08 05:09:53.31 dIJSWkMA.net
あたり
57:名無しのひみつ
23/11/08 09:56:37.33 GdPlUin3.net
>>55
負けないような最善手を指し続けた場合、引き分け的な結果にしかならんかもしれん
58:名無しのひみつ
23/11/08 13:27:04.86 ucAXmg/H.net
>>55
> 理論的には将棋 囲碁も必勝法あるんだよな。
敗勢濃厚なときには…
将棋の場合
盤を180度回転させる
囲碁の場合
相手と自分の碁笥を入れ替える
59:名無しのひみつ
23/11/08 15:01:58.27 ues6dyNE.net
相手殴りつけるのはダメか
60:名無しのひみつ
23/11/08 21:23:58.37 37M8yImc.net
８ｘ８ではなくて６ｘ１０ではどうかな。
61:名無しのひみつ
23/11/08 21:28:31.39 5KYMk2J2.net
>>29
俺も思った
62:名無しのひみつ
23/11/08 21:29:00.64 5KYMk2J2.net
盤面をn * nに拡張しても同じだろ？
63:名無しのひみつ
23/11/09 02:49:51.13 d62HEbNH.net
着手のパターンは広いけど、終わるまでの手数は必ず60手で終わる。
定石16手と積みエンジン32手ぐらい読んだら、かなり狭くなってくるよね。
64:名無しのひみつ
23/11/09 23:38:33.37 qxEOoCA6.net
まだ論文の査読も検証もされてないがな
まあ俺もこの分野の研究をしてる人間の一人だが
俺が読んだ限り今のところ誤りは見つけられてない
65:名無しのひみつ
23/11/09 23:46:00.67 fqLvu0zb.net
>>64
弱解決ってどの程度の評価なの?
片側は常に最善の手という制約みたいだけど
最善の手というのは評価関数で決めるだけだから
本当のところは分かってないのが弱解決なんだよね?
評価関数がある程度正しいことが分かってるから
ほぼ間違いないのではないかという話と理解して良い?
66:名無しのひみつ
23/11/10 08:21:14.39 KPoFguCu.net
盤面の最初を、黒も白も対角にもっとも外の角の位置に石を置いてからと思ったが、それだとどうなるのだろうか。
今は初期状態を中央に黒も白も対角に置いて始めるけれども。
67:名無しのひみつ
23/11/10 18:24:09.36 1d+DmX4W.net
>>30
言葉の使い方を知らないんだろうね
68:名無しのひみつ
23/11/11 09:40:49.68 FF8xQTpE.net
TikTok LiteでPayPayやAmazonギフトなどに交換可能な4000円分のポイントをプレゼント中！
※既存TikTokユーザーの方はTikTokアプリからログアウトしてアンインストールすれば参加できる可能性があります。
1.SIMの入ったスマホ・タブレットを用意する
2.以下のTikTok Litのサイトからアプリをダウンロード（ダウンロードだけでまだ起動しない）
URLﾘﾝｸ(lite.tiktok.com)
3.ダウンロード完了後、もう一度上記アドレスのリンクからアプリを起動
4.アプリ内でTikTok未使用の電話番号かメールアドレスを使用して登録
5.10日間連続チェックインで合計で4000円分のポイントゲット
ポイントはPayPayやAmazonギフト券に交換可能！
家族・友人に紹介したり通常タスクをこなせば更にポイントを追加で獲得できます。
69:名無しのひみつ
23/11/11 10:33:02.18 srAOksEs.net
>>68
ポイント大杉じゃね？
70:名無しのひみつ
23/11/11 15:55:33.84 QZKsI70O.net
>>37
囲碁はハンデのコミが無ければだろ。
コミ6.5目なら白必勝かもな。それか、黒が負けを避けて３コウの引き分けという結論か。
71:名無しのひみつ
23/11/12 10:47:03.29 +/qPdl/k.net
>>67
そもそも理解してないのでは?
72:名無しのひみつ
23/11/12 22:12:34.89 8Sv5ArMe.net
量子コンピュータだと一瞬で解けたりしないの？
アルゴリズム開発できない？
73:名無しのひみつ
23/11/12 22:47:46.87 PFbl62eR.net
>>68
簡単で良いな
74:名無しのひみつ
23/11/26 00:59:20.65 JUbseymF.net
8x8で勝負がついたら負けた方が勝負を続けるか選択できる。
掛け金を2倍にして周囲に2列増やした12x12に盤面を広げてゲームを続行できる。
負け分を払って続行しない選択もできる。
12x12で勝負がついたら．．（以下繰り返し。青天井？）
「圧倒的勝利をしてしまってはダメなんだ。
適度に手を抜いて相手に「勝てるかも」と思わせてゲームを続行させるのが肝。」
みたいな。
あ、最終局面全部黒とか続行不可のケースもあるな。
75:名無しのひみつ
23/11/26 01:01:41.36 JUbseymF.net
あ、勝負師がわざと負けて掛け金を莫大にしてから勝つでいいのか。
76:名無しのひみつ
23/11/26 08:57:37.90 ux6mhKgm.net
チクタクトーと同じで両者が最善手を打つと引き分けだとすれば、
やってもしょうが無いゲームだということになる。
77:名無しのひみつ
23/11/26 12:57:47.55 hKM0Caas.net
永久機関とかフリーエネルギーと
URLﾘﾝｸ(www.google.com)
人口が増えると無駄にエネルギーを消費するので
地球で採掘する原子の枯渇を早めますね!
リサイクルを使用とも数%は・・・
引いていえば宇宙を維持するエネルギーも最後は枯渇する!
78:名無しのひみつ
23/11/26 13:33:34.16 FazEat50.net
>>23
早期終局じゃなきゃあ最後に打つ手には選択の余地ないし、黒にも早期終局勝ちは可能
79:名無しのひみつ
23/11/29 20:00:51.68 w8nHt+Vl.net
なんでも解明されてしまう、つまらない世の中になったもんだ。
80:名無しのひみつ
23/11/30 12:53:02.33 5gv5z66p.net
一箇所、そこには打ってはいけない場所を設けると、それでもってゲームが代わる。
あるいは白でもない黒でもない、たとえば赤いコマを置いて置くのでも同じ。
81:名無しのひみつ
23/12/07 08:57:09.79 KMkkpQUi.net
>>65
強解決の意味は
・その段階では最善手を選ばなくても後で取り返して勝つ方法を見つける
あるいは
・最善手を選ばないと負けることが証明できる
なんじゃないかな
82:名無しのひみつ
23/12/09 19:19:22.09 D1+m+XDL.net
双方最善を指してたらいつか将棋も振り駒で勝敗が決まっちまうのか
83:名無しのひみつ
24/01/10 18:45:18.96 AWCWCsEa.net
引き分けが存在するゲームはほぼほぼ引き分けやろ
84:名無しのひみつ
24/01/10 19:09:53.28 0AeZ8nrz.net
引き分けが存在しても囲碁やオセロのように数で勝ち負けが決まるものは
解かれてしまった後は引き分けラインを動かすことで先後の公平を期す事ができる
あるいは勝ち負けを必ずつけたい場合は囲碁の0.5目のように勝敗ラインを設定することもできる
但しこれはゲームの本質に影響を与えるものではなく大会や統括組織下で設定するもの
85:名無しのひみつ
24/01/12 00:16:28.28 uJjXLZ1e.net
オセロのゲームの根本を変えて、
最後に残った自分の色のコマが少ない
側が勝ち、とルールを変更したらどうなる
だろうか？
86:名無しのひみつ
24/01/12 00:40:29.31 6ZKTkK0M.net
黒有利なはず
87:名無しのひみつ
24/01/14 15:34:19.88 FepjsRnC.net
弱解決
初期局面の勝敗が解明されていて
それを証明するために必要な各局面の最善手も分かってる
この定義を読んでも意味が分からなかったが
「ゲームの解決 田中哲朗」の縦横だけの五目並べの弱解決の証明をｙ院でやっと意味が分かった
拙い言葉で言い換えると
各局面でどうやればいいかの戦略があり
その戦略によってどちらかが勝つ
あるいは引き分けに持ち込める事が分かっており
それを避けることは出来ない
ということか
定義を読んでも理解できなかったのは
オセロには縦横五目並べみたいな単純な戦略がないと思っていたから
実際に単純ではなくて暗記出来ないほど複雑な戦略なんだろうけど
88:名無しのひみつ
24/01/14 15:35:15.16 FepjsRnC.net
>>87
ｙ院で→読んで
89:名無しのひみつ
24/01/14 15:38:10.64 FepjsRnC.net
けどそういう事が分かるのであれば
強解決ではないのだからブルートフォース的解決でないのは当然だけど
比較的単純な計算パワーの解決でもはなくて
オセロの特徴に特化した証明になってるはず
90:名無しのひみつ
24/01/14 15:58:49.98 2XfbUS6F.net
奇数にしておけば、引き分けなんて起こらなかったのに。
とは言え、先攻・後攻で平等にするには偶数にするしかないのだが。
後は、囲碁のようにコミあり（0.5とか）にすれば必ず勝負が着いたかな。
91:名無しのひみつ
24/01/14 17:44:08.44 9odmynG1.net
>>85
それって後手が最後にひっくり返して同数になるのが最善手（そうでないとパスになる）だから必ず後手勝利だろ
92:名無しのひみつ
24/01/14 18:40:28.04 FepjsRnC.net
>>87
うまく日本語に出来なかったが
こう書けば正確かな
各局面でどうやればいいかの戦略があり
その戦略によって
先手後手のどちらかが勝つ
どちらにも勝つ方法がない場合でも引き分けに持ち込め
避けることは出来ない
93:名無しのひみつ
24/01/15 10:13:01.06 gA47CojZ.net
URLﾘﾝｸ(i.imgur.com)
94:名無しのひみつ
24/01/15 18:46:59.72 pKl2z/JX.net
>>93
壺注意
95:名無しのひみつ
24/01/16 13:59:16.81 UQcJtWRP.net
まるばつが引き分けるのと同じだｒ
96:名無しのひみつ
24/01/16 23:35:17.61 w3Q2JkKH.net
5木並べ（連珠と違って、先手3－3、長連禁止とかが無い単純な場合）に
先手に必勝法があるということは江戸時代に既に発見されていたというね。
97:名無しのひみつ
24/03/17 08:13:30.83 X6ECE10gi
人の話をよく聞く岸田異次元増税憲法ガン無視地球破壞覇権主義経済音痴文雄にとって人とはお前らではなくクソ官僚のことた゛からな
官僚の給料爆上け゛しないと優秀な人材か゛集まらないとかデタラメ．マイナンバ─その他のポンコツっぷりからも分かるように頭は昭和の
無能ぞろいなのは給料か゛高すぎて金の亡者しか集まらないからというのが実態、知的能力者は金より完璧なシステ厶を完成させることによる
達成感を選ぶものた゛が公務員という人類に湧いた害虫に好き放題奪われ航空騒音による威カ業務妨害までされて人々が欲する価値生産なんて
やってられるかとみんな離脱、半導体価格大幅下落にリスキリングカ゛一の無能天國曰本て゛半導体だのAIだの天下り賄賂癒着大企業に10兆円
弾道ミサヰル作って空中で爆破するのか゛利権の次に大好きなシ゛ャクソに8兆圓，利権のためには氣候変動，災害連發，国土破壞，隣國挑發して
戦爭惹起して軍事利権倍増と俺も俺もと費用対効果もクソもない税金泥棒まみれのクソ公務員に支配された腐敗無能集団自民公明禍
お前らの賃金か゛物価上昇を上回るとか100%あり得ない
(ref.) URLﾘﾝｸ(www.call4.jp)
URLﾘﾝｸ(haneda-project.jimdofree.com) , URLﾘﾝｸ(flight-route.com)
URLﾘﾝｸ(n-souonhigaisosyoudan.amebaownd.com)