201804061216[接洽] ?A?B猜數字遊戲的AI

蘇格蘭語翻譯翻譯社前陣子在python版看到有人評論辯論到這個昔時煞到天成翻譯公司的遊戲, 一會兒熱血舊夢又被重燃... 我還算有能力把我手上的設法用C弄出來, 幾個程式設計相幹的板這裡也算是人氣較旺, 來這裡搞搞看有沒有人願意一起來玩玩瘋瘋 ------------------以上前情撮要,只是申明這絕對不是功課文----------------- 幾A幾B猜數字遊戲,略述以下: 兩小我玩,一方出數字,一方猜翻譯出數字的人要先想好一個沒有重複數字的4位數,不克不及 讓猜的人知道。猜的人就能夠開始猜翻譯每猜一個數,出數者就要根據這個數字給出幾A幾 B,此中A前面的數字透露表現位置准確的數的個數,而B前的數字默示數字准確而位置過失的 數的個數。 如准確謎底為5234,而猜的人猜5346,則是1A2B,其中有一個5的位置對了,記為1A,而 3和4這兩個數字對了,而位置沒對,是以記為2B,合起來就是1A2B。 如果不清楚規則的可以看wiki: http://goo.gl/FvfLq,或google 這個遊戲在網路上找到已有人對其解法的幾個最好化標的目的做過研究,一些事實: 1. worst case能包管幾回內猜到: 已證實為7次 (弗成能6次) 2. 在所有合法的5040種可能性中worst case呈現次數起碼: <=50次 (疑似open) 3. 最短能保證平均幾次猜到: 已證實為約5.2131次 4. 還沒有有人用暴力窮舉的體例跑完所有可能性過 (最少我沒查到) 5. 上述1、3有最少三種不同(非對稱等價)的演算法能同時到達 6. "刪除不可能,從剩餘中隨機猜"這個算法平均約5.47次,worst case極可能是10 那麼,我還想從這個被研究爛了的問題中搞什麼? 當然是個很直覺、很該問,而又沒有在所有被找到的研究中看到過的問題 起首我們來觀測上面第五點提到的這三種演算法 (詳見 http://goo.gl/rbXc4 第15頁) Strategy Name 1 2 3 4 5 6 7 8 Total ------------------------------------------------------------------------ Fast Strategy 1 7 62 718 2403 1757 92 26274 Slow Strategy 1 7 61 692 2445 1755 79 26274 Tanaka‘s Result 1 7 63 697 2424 1774 74 26274 ----------------------------------------------------------------------- 如上表,對於正當的5040種謎底,第一種演算法能把此中718種在第四次猜出來 而這三種演算法都能拿到平均26274 / 5040 = 5.2131的平均次數 並且從次數分配表可以看出他們是明明是分歧的,不具有對稱等價關係 他們三者之間有什麼重要的不同嗎? 有!!! 三小我拿著這三種"最好化"演算法彼此對戰,誰會占優? 推行出去一概而論的話,這個問題夠直覺、夠該問吧 以下注釋若何比較兩種演算法對戰的好壞關係 (以下假定演算法非隨機) 假設一個演算法能包管N次內猜出,且剛好在第k次料中的機率為f(k), (則: sum = 0.0; for (i=1;i<=N;i++) sum += f(i); 明顯有sum == 100%的關係) 對於兩種演算法各自的分配f1翻譯社 f2而言,在面臨面的對戰中, 第一種演算法勝出的機率是下面算出的sum sum = 0.0; for (i=1;i<=N1;i++) for (j=i+1;j<=N2;j++) sum += f1(i) * f2(j) 而兩種演算法平手的機率是 sum = 0.0; for (i=1;i<=min(N1, N2);i++) sum += f1(i) * f2(i) 由如許的闡發,套入這三種演算法的次數分配表可知第二種是最彼此對戰勝率最高的 (假如我此刻腦袋中對之前的計較結果印象准確的話) 由此可知,一樣worst case步數、甚至同時有一樣的平均步數的兩個演算法 互相對戰仍有高下,就更不要說平均步數不同的演算法之間了。 乃至我還可以舉出一個設想中的極端例子, 平均步數較差的演算法可能在對克服率上贏過勝過平均較好的 設想演算法: 有一種worst case需要999999999999999步才算出來,其他都一步秒殺 這個精力就是"贏一步是贏一把,輸一百步也是輸一把" 所以一會兒很(ㄗˋ)顯(ㄧˇ)然(ㄨㄟˊ)前面提到的直覺又主要的問題 "什麼演算法實克服率最高?" 仿佛變得有玩弄的空間了不是嗎? -------------------------以上是念頭、後臺說明-------------------------------- 所以天成翻譯公司想幹嗎? 天成翻譯公司想在這裡糾大師有閒的時刻來實做本身的弄法 看看誰能提出實克服率對照利害的算法來 現實比力由於有上面所述的評議方式,所以不需要把各人的code放在同個平台上跑 只要各自提出自己算法的次數分派表(極可能是7個數字罷了) 並附上演算法說明或程式碼給其他有樂趣的人磨練不是豪笅就能夠了 考慮到上面提到的闡明方式實務上只適用於"有肯定流程"的演算法間的比較 對於具有隨機性的算法可能會很難測出真實的機率分派表 我建議大師盡可能的設計有肯定流程的算法以便交流, 假如真的非隨機不成,建議附上至少跑1000圈(每圈5040種各一次)的累計次數分派結果 為了拋磚引玉, (我這兩天會弄出最少一個C code放在這個版以合適版旨,但新手需要點時間...) 今後有空的時候會陸續更新更好的算法 今朝手上有三個用python實作的簡單隨機算法 平均是5.36~5.48次,此中最好的阿誰有worst case極可能是7次, 他的10圈成就是6, 15翻譯社 433, 4909, 22617, 20591翻譯社 1829 最爛的阿誰是無邪的"每次從剩下可能中隨機選", 100圈成就是94翻譯社 1301翻譯社 10871, 61687, 177337, 185799, 61590, 5253, 67, 1 視人人對搞這個勾當回響反映若何啦, 若是反映強烈熱鬧的話我願意供應p幣(等下看我有幾何XD)給最優者 總之鼓動勉勵人人一路來動腦PK殺時候,陪天成翻譯公司瘋一瘋 再附上一個不錯的參考資料: http://bulls-cows.sourceforge.net/index.html -- 我不是學生,不是要交功課弄講述,也不是教員或帶人做科展 我乃至不是資訊科學相幹本科系身世,只是對數學、益智遊戲有點樂趣 並且有點根蒂根基的寫程式能力,所以本身玩玩 想要查詢拜訪天成翻譯公司念頭的不消太麻煩,台北附近可以約出來打棒球趁便聊聊

本文出自: https://www.ptt.cc/bbs/C_and_CPP/M.1348247639.A.C78.html有關各國語文翻譯公證的問題歡迎諮詢天成翻譯公司02-77260931
沒有上一則|日誌首頁|沒有下一則
回應
關鍵字
    沒有新回應!





Powered by Xuite