Re: [討論] ?A?B猜數字遊戲的AI
A、B兩人自己選的答案應該是互相無關的
並沒有人規定A、B兩人要同時用同一個答案
這是你所謂"勝負次數相同、勝率相等"敘述有誤的原因
其實如果你多想幾秒數學關於機率的部分的話
應該是可以理解那個公式的，就是乘法原理在加總而已
不過為了讓你信服，以下使用窮舉法把所有可能性走完
A、B任一選定自己的答案(令其分別為w,x,y,z)，這個組合數共有 4 * 4 = 16種
在實際的對戰中這16種每一種出現的機率均相等，這點應不証自明
各種情形的勝者:
w x y z <- (這是A選定的答案，垂直那行是B選定的答案)
w A A A -
x - - B B
y A A - B
z A A - B
由此可知A、B間的勝敗比例的確是7:5:4
你所謂"勝、負次數相同，勝率相等"的只是上面表格中左上到右下的對角線
========================================================================
btw，前兩天用力的試著把程式碼改成C，
由於程度太差實在相當痛苦...
改完了三個版本才發現我在做無用功，
因為我很快就在python上試出更好的，而且比原本更複雜更難改...
(偷偷問，如果我這個板放上py檔適合嗎?)
直接曬曬目前自己弄出最好的一組非隨機性算法
平均: 5.28273809524 <----------------------終於壓進5.3次以內，嘔業!!!!!
各組分布: [1, 9, 67, 581, 2338, 1918, 125, 1]
雖然我還有弄出其他幾個保證在七次內猜到的算法
但上面這個算法的平均值和實際對戰贏面都比保證我的那幾個保證七次的好
這個我目前最好的算法要點如下:
1. 每輪取能將下一層分最多個分支的來問
2. 若分支數相同則取讓最大分支盡量短的
3. 最大分支也一樣短就盡量選個自己可能是答案的
上述方法的結果去和我查到的四種"保證最短平均步數且最多七次猜到"的算法比較，
很無奈(毫不意外)的完敗被慘電
不過目前腦袋裡還有幾個新的為最佳化對戰勝率的想法，
有一些還有用數學邏輯方式(自以為)證明，接下來會繼續試試看
自以為很有理由相信implement進去還可以再改進
其中我覺得最重要但卻沒有證明出來，就我所知也沒有反例的的一個命題:
若A、B算法間作面對面勝率計算結果為A贏B，
且B、C算法間作面對面勝率計算結果為B贏C，
那麼是否保證A、C算法間作面對面勝率計算結果為A贏C?
如果這為真，那勝率最佳化之路就變成單行道，且保證有終點
另兩個也會很好用但我也沒法處理的命題是:
是否存在一種兩算法間前者所佔優勢的度量f(A,B)，可以有以下性質
給定f(A,B)、f(A,C)，則可算出f(B,C)
若f(A,B) > f(A,C)，則保證A、C間的面對面較量A會佔優勢?
會想到上面的問題主要來自於一個實驗，說明如下
算法: (注意到對固定起始條件而言這個算法是非隨機的)
一開始將0123~9876的5040種所有可能排成特定一種順序的一列
不斷重複"問第一個，淘汰所有不可能的"這個過程
這個算法可以保證得到答案，而且還計算時間非常快，平均猜到次數也不差
我隨機設定那一個起始的順序，100次平均給我:
平均5.4708次，總共[ 94,1301,10871,61687,177377,185799,61590,5253,67,1 ]
接下來我開始大海撈針，每跑一圈統計結果就換一個起始條件
不斷重複上面的算法，並把每次的統計拿去和目前最佳結果面對面PK
結果發現跑100圈以後就很難再有能把當時衛冕者拉下馬的
事實上，下一個成功翻盤的在第2479個，然後再下一個是第67023個
到目前為止約十萬圈了，還沒看到下一個
第67023號挑戰者: [ 1, 13, 108, 621, 1844, 1889, 532, 32 ], 平均: 5.430
這個實驗好像在告訴我"面對面PK"是有A>B, B>C => A>C的
(我承認這很不直接，不過從衛冕者被拉下馬的難度上升好像在暗示)
同時也告訴了我大海撈針法要從沙礫中找到珍珠的機會很渺茫
撈了十萬個，其中最好的一個也才比這類方法的平均少用0.04次......
PS: 最佳化"平均解出步數"的演算法可以達到平均5.213次，還差好遠
我也因為這個結果打斷了我幻想靠單純的大海撈針賽出寶來的機會
畢竟其他算法遠比這個慢太多，一輩子也跑不了多少次
建議大家如果要用"演化"的方式讓電腦自己"優化"，
方法上要動點腦筋，不要太靠暴力，那比Alt+F4還沒用
最後再分享關於優化的經驗
1. 假設第一次猜0123，在所有可能性考慮等價姓，第二次只有其他19類猜法而已
所以建議第二輪可以海巡這19種，不損失任何可能性，又沒有很暴力
我正在研究第三層共有多少種等價的猜法，看看能不能比照辦理
2. end-game階段(最後兩輪左右)可以適當的使用暴力解硬算出最快的
這時如果巡太多找太慢，可以"只從可能的中挑"，經證實常常很有利
先這樣，今天大概會繼續搞到去睡覺吧...
※ 引述《changyuheng (張昱珩)》之銘言：
: 假設母體中只有四個答案，
: A: 3 3 4 5
: B: 5 3 4 4
: 此二者對戰，勝、負次數相同，勝率相等。
: 依照您的公式：
: A: f(3) = 1/2, f(4) = 1/4, f(5) = 1/4; A total: 15
: B: f(3) = 1/4, f(4) = 1/2, f(5) = 1/4; B total: 16
: B 在數字上劣勢，
: 演算法的結果為：
: A 勝率：7/16
: B 勝率：4/16
: 平手率：5/16
: ※ 引述《SocketAM2 (AM2)》之銘言：
: : follow你的假設"母體只有三種答案"，
: : 並進一步假設A和B的猜法都不具隨機性
: : 則A猜法的次數分配為1:0, 2:0, 3:1, 4:1, 5:1 <= 這是前文所述的f1(k)成正比
: : B猜法的次數分配為1:0, 2:0, 3:1, 4:1, 5:1 <= 這是前文所述的f2(k)成正比
: : 可以從這個次數分配算出A、B猜法的機率分配:
: : A: f1(3)=1/3, f1(4)=1/3, f1(5)=1/3, f1(else)=0
: : B: f2(3)=1/3, f2(4)=1/3, f2(5)=1/3, f2(else)=0
: : 由我前文所述的比較方法，在任意一次A、B之間的較量中，A獲勝的機率為:
: : sum = 0.0;
: : for (i=1;i<=5;i++)
: : for (j=i+1;j<=5;j++)
: : sum += f1(i) * f2(j);
: : 用數字算出來是(1/3) * (1/3) * (2+1+0) = 1/3
: : 同理可算出A、B平手、B獲勝的機率也各是1/3
: : 事實上這個結果一點也不意外，
: : 因為兩者的次數分配一樣 => 兩者之間的對戰彼此獲勝的機率相等，就看平手機率多高
: : 而且因為兩者的次數分配在3、4、5次是平均的1，所以輸贏平手各佔1/3很正常
: : 關於勝敗評判的問題，再來個例題確保你有理解我的意思
: : 假設母體還是只有三種答案，但A、B猜法(都不具隨機性)表現如下:
: : A: 1:0, 2:0, 3:1, 4:2, 5:3
: : B: 1:0, 2:0, 3:2, 4:3, 5:1
: : 可以算出A獲勝、平手、落敗的機率分別為1/6, 11/36, 19/36 (如果我心算沒錯的話...)
: : 利用上述的比較猜法之間優劣的方法，可以容易的排名多種算法
: : 只要比照一般運動比賽常看到的二維表格紀錄整體比賽結果:
: : A B C ......
: : A X 1/6,11/36,19/36 .........
: : B 19/36,11/36,1/6 X
: : C .
: : . .
: : . .
: : . .
: : 並可以累積出各種算法的勝敗次數，以此排名
: : 勝敗次數相同的情況下，可以依序比較敗率、勝率等
: : 如果再相同的話可以去追原始碼比較原始碼的計算效率或是誰的code寫得較好XD
: : 重點是，隨著整體參賽者數量N越來越多，
: : 雖然打完一個完整循環所需要的總次數為CN取2=N(N-1)/2 => O(N^2)不是太理想
: : 但因為比較任兩者優劣的方法只需要跑兩個小小的for迴圈作加法、乘法
: : 而且N其實也不可能大到哪裡去 (超過1000我覺得不太可能吧...)
: : 參賽者只需在一參賽的時候就提出自己的分配了，後續擴充很簡單
: : 我在想可能可以用google doc開一個大家共同編輯的文件
: : 讓每個人自己寫上自己的次數分配並貼上source code連結
: : 假設大家都照一個固定的格式來填，那應該寫出一個工具來生成統計結果不困難
: : 感謝你的疑問，希望這樣有回答到你的問題:)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.16.26
※ 編輯: SocketAM2 來自: 118.160.16.26 (09/24 23:03)
※ 編輯: SocketAM2 來自: 118.160.16.26 (09/24 23:04)
推
09/24 23:31, , 1F
09/24 23:31, 1F
→
09/24 23:34, , 2F
09/24 23:34, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 11 之 11 篇)：