Re: [問題] 關於 xa xb 的猜數字遊戲AI

[RyanGun (雷恩)]

這個題目我之前有玩過一次

提供我的方法給大家

當然也歡迎批評


Step 1:建立所有可能性的資料庫 (e.x. 10x9x8x7 種可能)

Step 2:電腦亂數找到某組index

Step 3:使用者回答 ?A?B, 電腦刪除不可能的index

Step 4:goto Step 2


如果不考慮peformance的問題

基本上我想不到有更快的方式

有人有其他的想法嗎？



※ 引述《yauhh (喲)》之銘言：
: ※ 引述《cses (5858)》之銘言：
: : 其實是最近老師開了這個題目給我們
: : 要我們寫出一個簡單的AI來讓電腦跟我們玩 幾A幾B的猜數字遊戲
: : 就是...我們自訂一組數字，而電腦就是隨機產生一組亂數來問我們幾A幾B
: : 我們回答他幾A幾B ， 一直到猜出數字 4A 0B 這樣
: : 之前爬文有看到隨機產生1~9亂數這部分有看到一種方法是"增加某數字出現的權重"
: : 想問問這種語法要怎麼寫呢 ?
: : 由於本人是C的無敵新手，只看著課本找到srand()這個亂數函式
: : 想問  那種可以控制亂數出現比例的方法 要怎麼寫...
: : 又或著有更好的方法 可以把幾A幾B的AI寫出來呢 :)?
: 基本是用集合過濾法.
: 已知之前猜過一些數字,整理成一些對應集合,如:
:     ABCD 0A0B
:     AXBY 0A2B
:     .... ....
: 當你祭出一則 XYZW 的時候,假如它命中,意思就是和之前所猜過但不命中的
: 每個數字比對,就會是相關的AB情況. XYZW 和 ABCD 比對為 0A0B, XYZW 和
: AXBY 比對為 0A2B 等等.
: 於是,相對的,要出祭出每一則猜測,先把所有數字中,符合已經猜過的數字界定範圍
: 中的四位數字做為挑選對象. 例如,要祭出 YWXZ, 為什麼要祭出這個數?
: 因為 YWXZ 和 ABCD 比對是 0A0B, 和 AXBY比對是 0A2B ... 等等,過去猜過的
: 數字及AB情況完全符合,所以 YWXZ 是一個可以放出去猜的四位數字.
: 以上是AI部份. 至於你說你是C超新手,那就要多練習了. 這一題可以練很多程式技巧.

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 59.104.138.25
→ softwind:想不出來? 怎麼你會覺得這題目簡單勒???
→ softwind:這可是連Knuth 都愛的題目哩~ XXD
→ RyanGun:我沒有覺得簡單呀  所以我還蠻想知道其他的方式
→ bleed1979:原po的step2就是這個問題需要思考的地方。
推 timTan:接下來的最佳化就幸苦了。
→ yoco315:關鍵字Mastermind,如bleed所說step2是關鍵,很多論文做這個
→ yoco315:如果是只是亂數隨便選那當然是簡單,但是要猜比較多次
→ yoco315:step2選的好的話,可以盡可能縮小需要的的平均次數
→ yoco315:這個就很難了,我記得這目前還是 open problem