JWorld@TW the best professional Java site in Taiwan
      註冊 | 登入 | 全文檢索 | 排行榜  

» JWorld@TW » Java 程式分享區 » 數獨、猜數字  

按列印兼容模式列印這個話題 列印話題    把這個話題寄給朋友 寄給朋友    訂閱主題
reply to topicthreaded modego to previous topicgo to next topic
己加入精華區
by caterpillar at 2006-01-10 18:36
本主題所含的標籤
無標籤
作者 [猜數字系列] 和大家分享我最近寫的猜數字…… ( 最佳解求出來了 5.2131 ) [精華]
owenlin_twn





發文: 21
積分: 3
於 2005-12-24 01:24 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
從以前就陸陸續續地對猜數字作了一些研究,
最近發現這個網站上有許多網友,似乎對這個遊戲也蠻有興趣的,
所以最近寫了一個猜數字的遊戲,和大家分享。

可是這些主要的目的在於研究猜數字,而非遊戲本身,所以介面作的不是很好,
以下是遊戲的畫面(文字模式啦……Big Smile)

1
2
3
4
5
6
7
8
9
create BasicChooser with seed as 1135328405375
start game with random seed as 1135328405375
using chooser: BasicChooser
guess: 1059 ?A?B: 10
guess: 2839 ?A?B: 11
guess: 6489 ?A?B: 01
guess: 2354 ?A?B: 12
guess: 2043 ?A?B: 03
guess: 1234 ?A?B: 40


執行的方式如下:
java -jar guess.jar

預設的 AI 不是最強的,最強的又太慢,建議可以打
java -jar guess.jar InfoGain
用 InfoGain 這個 Guess Chooser ,又快效果也不錯……

因為程式很大,我也就不 post 出來程式碼了,附檔裡有 source code,
一個 jar 檔,和 javadoc 的文件。

guess.zip (260.21k)


owenlin_twn edited on 2006-01-08 07:13
reply to postreply to post
作者 Re:和大家分享我最近寫的猜數字…… [Re:owenlin_twn]
owenlin_twn





發文: 21
積分: 3
於 2005-12-24 02:04 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
這個程式,有個我覺得蠻好的 framework,
有興趣的人可以用來開發自己的演算法,相信可以省下不少的時間。

程式的說明,javadoc中都有寫,可是我的英文不是很好,
但是 javadoc 寫中文的又很怪。如果有看不懂,不明白的地方,再問我就可以了。

大至上來說,我把猜數字的過程看作是一顆樹,而遊戲過程中的狀態是樹中的一個節點,比如說,根節點就代表遊戲的一開始,該節點總共有 5040 個數字,代表一開始有 5040 種可能。每一次的猜測會分裂一個節點(split),分裂出一個或多個的子節點,比如說根節點一定會分裂出 13 個子節點,分別代表 0A0B, 0A1B, ..... , 3A0B 的情況,(因為 4A 就是猜中了,算是在這個節點結束,所以不列入子節點中)。

一次完整的遊戲在樹裡面就是一條從root到leaves的路徑。這裡說的節點,在程式裡就是 GuessTreeNode 。

在程式裡所有的數字都是以 16 進位來表示的,比如說,猜的是 "1234" 的話,所代表的數值就是 0x1234 = 4660 。而 1A2B 這種關係,在程式碼中稱之為「標籤」(Label) ,也是用 16 進位來表示的,比如說 0x12 就是 1A2B 。

而程式的 AI 主要是在 GuessChooser 這個介面的實作者中來實現,拿最簡單的 BasicChooser 來看好了,以下是 BasicChooser 的程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class BasicChooser implements GuessChooser {
  // 省略……  
  private Random random;
  
  public BasicChooser( Random random ) {
    if ( random == null ) throw new NullPointerException();
    this.random = random;
  }
  
  public int nextGuess(GuessTreeNode node) {
    int index = random.nextInt( node.size() );
    return node.getNumber( index );
  }
  // 省略……
}


程式會將目前的狀態傳給 nextGuess 這個 function ,而 BasicChooser 就從目前還符合的數字中,任選一個傳回。

除了BasicChooser 以外,我還寫了許多其它的 chooser ,其中許多的 chooser 都是以評分的方式來選出最佳的數字來猜。我把它們共同的部份再抽取出來,成為 ScoredChooser ,它的子類別,只要專心於 評分函式 的實作就可以了。舉例來說,以 fanout 來評分的 FanoutChooser,程式碼如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class FanoutChooser extends ScoredChooser {
  // 略……
  private int category[] = new int[ 0x100 ];
  
  public FanoutChooser( Random random ) {
    super( random );
  }
 
  public double score( int guess ) {
    node.doLabelStatistics( guess, category );    
    int fanout = 0;
    int n = node.getDigitCount();
    for( int i=0; i <= n; ++i ) {
      for( int j=0, jn = n - i; j <= jn; ++j ) {
        int x = category[ ( i << 4 ) | j ];
        if ( x > 0 ) ++ fanout;
      }
    }
    return fanout;
  }
 
  // 略……  
}


reply to postreply to post
作者 Re:和大家分享我最近寫的猜數字…… [Re:owenlin_twn]
owenlin_twn





發文: 21
積分: 3
於 2005-12-24 02:37 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
這個 project 中,除了 Game 以外,還有另外一個好用的工具 BuildTree。在前一篇文章說到了一次的遊戲只是「樹」中的一條路徑,所以在一次的遊戲中,我們只需如果我們將該路徑上的節點分割(split)即可。

而 BuildTree 會將整顆樹完整的建出,並且會 output 每一個數字所在的深度統計。(也就是要猜幾次的統計啦 Cool) 。以下是用 InfoGain 所得到的結果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
c:\> java -cp guess.jar org.fattybobo.guess.BuildTree InfoGain
build InfoGainChooser(1.8) with random seed as 1135333903093
build guess tree using chooser: InfoGainChooser(1.8)
1: 1( 0.0198% )
2: 7( 0.1389% )
3: 74( 1.4683% )
4: 712( 14.1270% )
5: 2309( 45.8135% )
6: 1787( 35.4563% )
7: 148( 2.9365% )
8: 2( 0.0397% )
average guess number: 5.238888888888889
complete in 3515 ms
save the built tree into "guesstree.bin"


更好的是,它會把這整顆數「序列化」Serialize 到 guesstree.bin 這個檔案之中。
output 到檔案作什麼呢?因為它是一顆完整的樹,所有的清況都在其中了,我們可以用它來作之後的猜測。程式中有一個 GuessTreeChooser 就是用來作這件事的。附檔中有一個 besttree.zip 請把它解開後有一個 besttree.bin。接著執行以下的動作就可以用這顆樹囉。
1
C:\>java -jar guess.jar GuessTree besttree.bin

分享的這顆樹,它的平均次數可以到 5.2183 次喔!

besttree.zip (62.95k)


reply to postreply to post
作者 平均五次的迷思 - Part I [Re:owenlin_twn]
owenlin_twn





發文: 21
積分: 3
於 2005-12-25 05:55 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
介紹了一些程式上的架構與設計之後,再來點理論的東西吧!Cool

我最終的結論是要證明,沒有任何一種演算法可以達到 平均 5 次內猜到。 Shock

所以,這也就是說……

那筆猜數字獎金是送不出去的…… Big Smile
http://www.javaworld.com.tw/jute/post/view?bid=35&id=36001&sty=3&tpg=1&age=0

猜數字在一開始的時候,有5040種可能的數字,
第一次不管你猜那一個數字,所得到的結果會有下列幾種:

1
2
3
4
5
0A0B:  360, 0A1B: 1440, 0A2B: 1260, 0A3B:  264, 0A4B:    9
1A0B:  480, 1A1B:  720, 1A2B:  216, 1A3B:    8,
2A0B:  180, 2A1B:   72, 2A2B:    6,
3A0B:   24,
4A0B:    1


總共有 14 種情況,每種情況後面則是符合的個數。

不難理解:

如果一次之內要保證猜到,可能的數字不能超過 1 個。
如果二次之內要保證猜到,可能的數字不能超過 14 個。

那麼三次呢??

假設 f( n ) 表示 n 次要要猜到,可能的數字的上限的話,
1
2
1. f( 1 ) <= 1
2. f( n ) <= sum( min( f(n-1), size[i] ), i = 1 to 14 


其中 size 是如下上面所述每種情況的個數 { 1, 6, 8, 9, 24, 72, ....., 1440 };

上式並不難理解,在猜了第一次之後,我們只剩下 n-1 次可用,
並且會有 14 種可能的情況,為了確保每一種情況 在剩下的 n-1 次內可以猜到,
每一種情況的個數最多只能有 f(n-1) 個。

上述是一個遞迴式,我們不難求出:
f(1) <= 1, f(2) <= 14, f(3) <= 164, f(4) <= 1432,
f(5) <= 5032, f(6+) <= 5040 ( 6 以上都是 5040 )

這一個簡單的公式已經告訴我們,猜數字遊戲要保證在 5 次內猜完是不可能的。
那麼平均呢??

假設我們今天有一個最佳的猜法,假設它最多要猜 m 次,
而它在第 n 次可猜到的數字個數為 g( n )。

我們會有
1
2
3
4
g(1)                                <= f(1) <= 1            .... (1)
g(1) + g(2)                         <= f(2) <= 14           .... (2)
g(1) + g(2) + ... + g(m-1)          <= f(m-1) <= 5040       .... (3)
g(1) + g(2) + ... + g(m-1) + g(m)   = 5040 ( 全部的數字 )   .... (4)


以 (4) 式分別減去 (1) (2) (3) 式之後相加,我們可以得到
1
1*g(1) + 2*g(2) + .... + m*g(m) >= 5040 * m - 1 - 14 - ... - 5040


將兩邊同除 5040 ,左式即為 平均次數,右式 為 ( 23579 / 5040 ) = 4.678

到目前為止,我們證明了平均次數至少為 4.678 次。

嘿!等等,你不是說可以證明至少是 5 次的嗎?
打累了,容我賣個關子,下次再說吧!

( 如果對證明過程有疑問的話,歡迎提出來。我自己是認為是對的,但難免有思慮不周的情況。)


owenlin_twn edited on 2005-12-28 06:53
reply to postreply to post
作者 Re:和大家分享我最近寫的猜數字…… [Re:owenlin_twn]
worookie

Small Ship

版主

發文: 2092
積分: 21
於 2005-12-25 20:18 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
owenlin_twn wrote:
我自己是認為是對的,但難免有思慮不周的情況。

我很認同這句話.


reply to postreply to post
作者 平均五次的迷思 - Part II [Re:owenlin_twn]
owenlin_twn





發文: 21
積分: 3
於 2005-12-26 07:19 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
其實要證明平均至少 5 次的概念,和上一篇所用到的概念是一樣的,
只不過為了更逼近其下界(lower bound),我們多往下展開幾層。
也就是說,我們先模擬前幾次的猜法,之後才將上面的推論套用在子節點上,

舉個例子來說,在第一次猜完之後,屬於 0A1B 的 1440 個數字,
其分支根本不可能達到和原本 root 一樣那麼多,如果我們可以更精確的估計它的話,
一定能再更進一步的求出它的下界。
這樣的概念可以延申到往下展開第二次的猜法,甚至是第三次,第四次。
但要注意的是,第二次以上的猜法就不是只有一種了。
我們必需模擬出所有可能的猜法,並在其中選出最小值來當作我們的下界。

觀念上來說是這樣,但是還有一個問題要解決。
在根節點時,猜每個數字的分支情況都是一樣的,但是這點對子節點來說就不成立了。
我目前解決的方法就是每個分支法都試一次,最後取其最佳解。
用數學式子來寫:

1
2
    原本的 sum( min( f(n-1), size[ i ] ), i = 1 to 14 )
    將變成 max( sum( min( f(n-1), size[j][ i ],i = 1 to 14 ), j 為所有不同的猜法 )


也就是說,我們摸擬所有的可能分支情況,求其最大值。
值得一提的是在不同的 n 值下,選到的 j 可能是不同的喔!

為了更精確地描述上面的方法,我將這段敘述的程式碼貼在下面:
( 其中的 fanout 就是上述的 size )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    private static int 
    getCost( GuessTreeNode node, int fanout[][] ) {
        int last = 1, sum = 1, level = 1;
        while( last != node.size() ) {
            int maximum = 0;
            for( int j=0; j < fanout.length; ++j ) {
                int vector[] = fanout[j], tmp = 0;
                for( int k=0; k < vector.length; ++k )
                   tmp += Math.min( last, vector[k] );
                if ( maximum < tmp ) maximum = tmp;
            }
            sum += ( last = maximum );
            ++ level;
        }
        return node.size() * ( level + 1 ) - sum;
    }    


這只是程式中的一小片段,完整的程式請看附檔。以下是執行的結果。

展開 0 層: 23597 / 5040 .... 4.6819
展開 1 層: 24824 / 5040 .... 4.9254
展開 2 層: 25542 / 5040 .... 5.0679

到了展開 2 層時,我們需要大約 2 分鐘的時間,
不過也剛好足夠證明了要平均五次是不可能的囉!

目前我只能往下展開了兩層,我有一台電腦正在算展開三層的結果,
結果應該是幾天內就會出來了,如果有消息,再來向各位報告。

我們現在知道了最佳解介於 5.06 ~ 5.2185 之間,到底最佳解會落在哪呢?
(我相信第三層如果算出後,下界可以提升到 5.10 以上。)

我蠻希望將這個最佳解求出來,
不夠以我目前的想法在現在的電腦上,速度上還有很大的難題就是了。
這幾天我會再好好的估計一下所需的時間,看有沒有可能去解它。

LowerBound.java (3.34k)


owenlin_twn edited on 2005-12-28 06:54
reply to postreply to post
作者 Greedy Algorithms [Re:owenlin_twn]
owenlin_twn





發文: 21
積分: 3
於 2005-12-27 16:24 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
到目前為止,還有一件事沒交代清楚,就是平均 5.2185 次的猜法是如何得出的。
在這之前,先來說明一下,在程式中實作了哪些 Greedy 的演算法,
並儘可能解釋它們設計的原理以及它們的效果如何。

==== BasicChooser ====

非常一般和直覺的寫法,它會從還符合到目前為止的條件的數字中任選一個來猜。
說真的,以這麼簡單的演算法來說,它的效果還算蠻不錯的,

以下是其中一次執行 BuildTree 的結果。

1
2
3
4
5
6
7
8
9
1: 1( 0.0198% )
2: 13( 0.2579% )
3: 109( 2.1627% )
4: 616( 12.2222% )
5: 1788( 35.4762% )
6: 1877( 37.2421% )
7: 600( 11.9048% )
8: 36( 0.7143% )
average: 5.4579


在這邊要特別說明的是,因為它的猜法是任選的,
所以它所建立出來的「樹」也不是唯一的,
有可能有些樹的平均會到 5.489 次或更多,也可能比 5.458 次更少,
也有可能最多會猜到 9 次之多。這裡所貼出來的,只是它一次的結果。
目前看起來,它們的平均並不會差太遠。
不只 BasicChooser 是屬於這種 randomized algorithm,
接下來所提的方法,也幾乎都有這樣的特性,不過就不再特別提了。

我想它的弱點,就如 nadiaInochi 提過的,
如果前兩次都是 3A0B 的話,它可能會笨到要猜到第七次才會猜中。

==== FanoutChooser ====

以其分支數作為所猜數字[的評分標準,選出分支最多的猜法。
這也很符合直覺,但事實上它有另一個有趣的意義,它會「最大化」下次猜到的機會。

例如,原本有 n 個數字,猜完之很可能有 m 種情況,每種情況符合的數字分別有 n1, n2, ..., nm 個。
那麼下次要猜到的機會就是

(n1/n)*(1/n1) + (n1/n)*(1/n1) + ... + (nm/n)*(1/nm) = m / n

這是因為出現情況 i 的機會是 ni/n 而 清況 i 一猜就中的機會是 1/ni 。
所以 m 愈大,其值就愈大。

1
2
3
4
5
6
7
8
1: 1( 0.0198% )
2: 8( 0.1587% )
3: 57( 1.1310% )
4: 530( 10.5159% )
5: 2226( 44.1667% )
6: 1999( 39.6627% )
7: 219( 4.3452% )
average: 5.3502


和 BasicChooser 相同,因為滿足 fanout 最多的數不只一個,所以它所建立的樹也不只一種。
我試了一下,它最差的情況有可能會有 8 次,但平均還是不會差多。
它已經比 BasicChooser 快了大約 0.1 次了。

==== GiniIndexChooser ====

所謂的 GiniIndex 是一種在「決策樹」(Decision Tree) 用的演算法,

它的計算方式如下面所述:
假設原本有 n 個數字,以某個數字去猜,將會得到 m 種可能情況,
每種情況符合的數字個數分別為 n1, n2, ..., nm 。

則它的 gini index 為:

Gini Index = ( n1/n )^2 + ( n2/n )^2 + .... + ( nm/n )^2

我們將選 Gini Index 最小的猜法作為下一次的猜法。
它也有另一個比較讓人理解的意義,它最小化 符合的數字個數 之期望值。
因為:
Gini Index = ( ( n1/n ) * n1 + ( n2/n ) * n2 + .... + ( nm/n ) * nm ) / n

以下是其中一次執行的結果:

1
2
3
4
5
6
7
8
1: 1( 0.0198% )
2: 4( 0.0794% )
3: 60( 1.1905% )
4: 593( 11.7659% )
5: 2398( 47.5794% )
6: 1886( 37.4206% )
7: 98( 1.9444% )
average: 5.2685


大致上來說,它又比 FanoutChooser 再快一了 0.1 次左右。

==== MinSetChooser ====

以分割後最大的情況之數字個數,作為評分的方法。
假設原本有 n 個數字,以某數去猜,將會得到 m 種可能的情況,
假設每種情況符合的數字個數分別 n1, n2, ..., nm 。
則這個 chooser 它的評分公式為:

max( n1, n2, ..., nm )

並選擇其值最小的猜法為下一次的猜測。

它的結果如下:

1
2
3
4
5
6
7
8
1: 1( 0.0198% )
2: 2( 0.0397% )
3: 32( 0.6349% )
4: 377( 7.4802% )
5: 1999( 39.6627% )
6: 2287( 45.3770% )
7: 342( 6.7857% )
average: 5.5


可以注意到的是,它是一個考慮「最差」情況的演算法,
雖然不像 BasicChooser 會有 8 次,甚至 9 次的情況出現,
但平均反而比 BasicChooser 還差。

==== InfoGainChooser ====

這也是「決策樹」(Decision Tree) 用的演算法。

基本上,給定一組 symbol 及其每一個 symbol 的機率,
我們可以求出這組 symbol 的「熵」( entropy ),它的算法如下,

entropy = sum( - pi * lg( pi ) )
其中,lg( n ) = ln( n ) / ln( 2 )

它可以想作是用來表示每一個 symbol 平均所需要的 bit 數。

舉例來說,我們有 a, b, c, d 四個 symbol,
它們出現的機率各為 1/8, 1/8, 1/4, 1/2,則它的熵的為

-1/8*lg( 1/8 ) -1/8*lg( 1/8 ) - 1/4*lg( 1/4 ) -1/2*lg( 1/2 ) ,

即為 ( 3+3+4+4 )/8 = 7/4 。

而所謂的 information gain 就是猜之前的「熵」和猜之後「熵」的期望值之差。
可以證明期值必定為正,它可以想像為這次猜測所猜得的資訊,
而我們正是要選能獲的最多資訊的猜法。

就我們的例子來說,

假設原本有 n 個數字,因為每一個數字出現的機會都是相同的,
所以它們的機率都是 1/n ,所以原本的熵就是: lg( 1/n )。

假設猜之後有有 m 種不同的情況,而符合的各個情怳的數字分別有 n1, n2, ..., nm 個。
則猜之後的「熵」的期望值就是

(n1/n)*lg( n1 ) + n2/n*lg( n2 ) + ... + nm/n*lg( nm )

又因為 對於所有不同的猜法,它們的 n 都是相同的,
所以 info gain 可以再減化為

info gain = - n1*lg( n1 ) - n2*lg( n2 ) - ... - nm * lg( nm )

但是如果仔細想想的話,這樣的公式還有一個小缺點,
大小為 1 的情況有兩種,猜中了( 4A0B ),或者沒猜中,
但是無論是哪一種情況,在上式中它們的值都為 0 ,這顯然不是很公平。

所以呢,我們多加了一個參數進去,"next level penalty", 把原本的公式改為

info gain = - n1* ( lg( n1 ) + w ) - ... - nm' * ( lg( nm ) + w ) ........ (1)

其中 4A0B 的情況還是為 0 ,其它的就多加一點 所謂的 penalty,w,它是一個正的常數。

事實上會這樣子改還有另一個原因,因為這樣改的公式還有另一個解釋,
就是以 lg( n ) 作為該一大小為 n 的子節點之平均深度的估計值,
而得到母節點中所有數字的深度加總。

假設 f( ni ) 為大小為 ni 的子節點的平均深度,則母節點的深度和會是

total depth = n1 * f( n1 ) + n2 * f( n2 ) + .... + nm * f( nm )
+ n1 + n2 + ... + nm
= n1 * ( f( n1 ) + 1 ) + .... + nm * ( f( nm ) + 1 )

代入 f ( ni ) 為 lg ( ni ) / lg( w' ) 再經過化簡即可得到 (1) 式了。

經由實驗發現 w 的值取在 1.8 的效果不錯。
說了這麼多,它的效果如何呢?

1
2
3
4
5
6
7
8
9
1: 1( 0.0198% )
2: 7( 0.1389% )
3: 74( 1.4683% )
4: 713( 14.1468% )
5: 2307( 45.7738% )
6: 1789( 35.4960% )
7: 147( 2.9167% )
8: 2( 0.0397% )
average: 5.2387


可以看到它又比 GiniIndex 要再更進一點了。而 next level penalty 真的有用嗎?
以下是未使用所得到的結果:
1
2
3
4
5
6
7
8
1: 1( 0.0198% )
2: 5( 0.0992% )
3: 49( 0.9722% )
4: 523( 10.3770% )
5: 2458( 48.7698% )
6: 1892( 37.5397% )
7: 112( 2.2222% )
average: 5.2929


嗯……看起來是有用的……

==== DeepInfoGainChooser ====

這裡用的演算法基本上和 InfoGain 是相同的,所不同的是它會多思考一層。
所以又會比單層的 InfoGain 再進步一些。它的結果如下:

1
2
3
4
5
6
7
8
1: 1( 0.0198% )
2: 7( 0.1389% )
3: 67( 1.3294% )
4: 691( 13.7103% )
5: 2417( 47.9563% )
6: 1754( 34.8016% )
7: 103( 2.0437% )
average: 5.2202


真的是有再進步一點…… ( 0.019次 ),
但是它所花的時間卻多了1000 倍,唔!真是不小的代價呀!

==== ExpertChooser ====

這個 chooser 基本上在子節點個數小於某一值時,會將子節點以子節點內的數字完全展開,
也就是 nadiaInochi 所說的表內搜尋。
另一方面來說,當子節點個數比較多時,它會將選擇交給另一個 chooser 來作,
我們稱那個 chooser 為 delegate chooser。

它的用法比較特別,參數的格式如下:

java -cp guess.jar org.fattybobo.guess.BuildTree Expert 32 delegate: InfoGain 1.8

其中,32 即為啟動無限展開的節點個數限制,
而 "delegate:" 之後的參數為 delegate chooser 的參數。

下以的結果是以 Expert 512 delegate: DeepInfoGain 3.0 所得到的結果。

1
2
3
4
5
6
7
8
1: 1( 0.0198% )
2: 7( 0.1389% )
3: 57( 1.1310% )
4: 697( 13.8294% )
5: 2435( 48.3135% )
6: 1764( 35.0000% )
7: 79( 1.5675% )
average: 5.2155


唔!又進步到了 5.2155 了耶!咦?是最新找到的 tree 嗎?怎麼程績又進步了呢?
唉…其實是之前我把 tree 的檔案弄錯了,這才是我之前找到最佳的樹。

這顆樹我放在附檔,有興趣的人可以 download 下來試看看。

嗯,它花了我電腦大約兩個小時的時間才算出來。

==== DigitInfoChooser ====

這和 InfoGainChooser 一樣,都是利用 information gain 來作為評分的依據,
所不同的是,這裡是計算每一個數字的 information gain 之後,
再將 0 ~ 9 的 gain 的總和作為評分。

也就是說 如果 數字 i 出現在 位置 j 的 機率為 p(i,j) 又 p(i,0) 代表它沒有出現的機率,
則它的「熵」為

entropy( i ) = sum( - p(i,j) * lg( p(i,j) ), j = 0 ~ 4 )

同樣的,我們對它的公式作和 InfoGain 類以的化簡,並加上 next level penalty 。

它的結果如下:

1
2
3
4
5
6
7
8
9
1: 1( 0.0198% )
2: 6( 0.1190% )
3: 70( 1.3889% )
4: 678( 13.4524% )
5: 2281( 45.2579% )
6: 1854( 36.7857% )
7: 148( 2.9365% )
8: 2( 0.0397% )
average guess number: 5.2611


besttree.zip (62.88k)


owenlin_twn edited on 2005-12-27 17:00
reply to postreply to post
作者 最新的 lower bound 出來了…… 5.1675 [Re:owenlin_twn]
owenlin_twn





發文: 21
積分: 3
於 2005-12-28 06:51 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
往下三層預估 lower bound 的程式在辛苦地跑了3天又20個小時再56分鐘之後,終於有了驚人的結果了。

下界(lower bound) 再度推進至 26044 / 5040 = 5.1675
和目前最佳的結果 5.2155 只有 0.048 次的差距了。

沒想到逼得這麼近了,超乎我原本的預期……Big Smile
這是真的嗎?還是我的推論出了問題,亦或是程式寫錯了呢?!

ps: 找尋 optimal solution 的工作正默默地持續進行著…… Dead


owenlin_twn edited on 2005-12-28 06:54
reply to postreply to post
作者 擴充新的 chooser [Re:owenlin_twn]
owenlin_twn





發文: 21
積分: 3
於 2005-12-29 08:30 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
這個程式當初一個設計的目的就是讓使用者可以在不改程式碼的情況下,
可以簡單地擴充這個程式,加入新的 AI。

我參考了 Yoshi 所設計的 DeepGreen ,設計了一個新的 Chooser ,
用以擴充原本的程式 AI 。

我不知道有沒有誤解了原意,不過只是個 demo 嘛……
這裡只秀出相關的部份,完整的程式請下載附檔。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.Random;
import org.fattybobo.guess.*;
 
public class DeepGreenChooser implements GuessChooser {
    static {
        ChooserFactory factory = ChooserFactory.getInstance();
        factory.registerBuilder( "DeepGreen", new Builder() );
    }
    private Random random = new Random();
    
    public DeepGreenChooser( Random random ) {
        if ( random == null ) throw new NullPointerException();
        this.random = random;
    }
 
    // 略
    
    private static class Builder implements ChooserBuilder {
 
        public GuessChooser buildChooser( String[] argv ) {
            long seed = argv.length == 0 ?
                    System.currentTimeMillis() :
                    Long.parseLong( argv[0] );
            Random random = new Random( seed );
            GuessChooser chooser = new DeepGreenChooser( random ); 
            System.out.println( "create " 
                    + chooser + " with seed = " + seed );
            return chooser;
        }
        
    }
    
}


其中 factory.registerBuilder( "DeepGreen", new Builder() );
就是向 factory 註冊一個名為 DeepGreen 的 ChooserBuilder.

而 Builder.buildChooser( String[] argv )
則是負責從 user 端讀取相關的參數,並依此建立新的 chooser 。

準備的工作如下:

1. 將它存成 DeepGreenChooser.java。

2. 在 user.home 的目錄下 ( Windows 下就是 C:\Document and Settings\[USERNAME] ),
  新增一個名為 "org.fattybobo.guess.ChooserBuilder.list" 的檔案 (嗯,有點長)。
  檔案的內容就是剛剛的 class 名稱(要包含 package 名喔),
  就這個例子來說就是 DeepGreenChooser。
  如果將來還要擴充其它的 chooser,一行一個地加上去就可以了。

3. Compile DeepGreenChooser

  C:> javac -cp guess.jar DeepGreenChooser.java

4. 新的 chooser 可以用囉!

  C:> java -cp .;guess.jar org.fattybobo.guess.Game DeepGreen
  ( 這裡的 classpath 要能夠找到新增加的 chooser 喔! )

你應該可以看到如下的畫面:
1
2
3
4
create DeepGreenChooser@83cc67 with seed = 1135786801375
start game with random seed as 1135786801375
using chooser: DeepGreenChooser@83cc67
guess: 0875 ?A?B:


我認為目前所設計的 chooser 大都沒辦法估計一個 node 的難易程度,
像是 InfoGainChooser 或是 GiniIndexChooser 都是依照 node 的大小所算出來的。
當初設計出 DigitInfoChooser 時,本來認為它很有機會的,不過很可惜,後來也敗陣下來。

期待有新 chooser 被設計出來。

DeepGreenChooser.java (2.01k)


reply to postreply to post
作者 猜數字之最佳解 ( optimal solution ) -- 5.2131 [Re:owenlin_twn]
owenlin_twn





發文: 21
積分: 3
於 2006-01-08 07:12 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
owenlin_twn wrote:
ps: 找尋 optimal solution 的工作正默默地持續進行著…… Dead

最佳解的找尋,在昨天晚上對程式作了修改後,速度上有了相當的改善。
電腦在今天有了最後的結果了,總共只花了 9 個小時又19分再24秒(我的電腦是 P4 3G )。

有必要說明的是這裡指的「最佳解」是指「平均猜的次數」最少猜法。

以下是最佳解的統計資料:

1
2
3
4
5
6
7
8
1: 1( 0.0198% )
2: 7( 0.1389% )
3: 62( 1.2302% )
4: 691( 13.7103% )
5: 2444( 48.4921% )
6: 1756( 34.8413% )
7: 79( 1.5675% )
average: 5.2131


雖然和之前用 heuristic 演算法所得到之最好的結果 ( 5.2155 ) 只進步了 0.0024 ,不過還是另人相當的高興。

在程式的背後,是有些理論在支持地,好讓它跑得更快些(主要是對稱性和下界)。
像之前所說的,這些理論是否有未考慮清楚的情況,撰寫出來的程式是否有問題,
我都不是十分的確定。

所以這幾天我會把 code 再整理一下,並且我程式的概念寫出來,看看有沒有人覺得有問題的地方的。

另外我也想把序列化(serialize)的方式重新改寫一下,讓它用的空間可以更小。


reply to postreply to post
作者 Re:猜數字之最佳解 ( optimal solution ) -- 5.2131 [Re:owenlin_twn]
owenlin_twn





發文: 21
積分: 3
於 2006-01-08 08:55 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
這裡我將描述我用來加速找尋最佳解的方式。

-- 對稱性 -- (我想這是加快速度最大功臣了)

如果不考慮對稱性,以平均猜 5 次來說,
就會有 5040 ^ 4 (第一次不算)種可能的猜法,也就是 645241282560000 。
以電腦 1 秒可以試 1000,000,000 種排法來說,也要算個 7 天才有結果,
更何況現在電腦的速度遠不及這樣的推論。

大家都知道第一次因為對稱性的關係,無論你猜什麼數字,其效果都是一樣的。

更進一步地,第二次的猜測呢?
如果第一次猜的是 0123 ,不難理解第二次猜 0145 和 0167 的效果其實也是一樣的,
( 到目前為止的觀念,在我第一篇裡的程式裡就有運用了! )

那麼再進一步呢?

如果第一次猜的是 0123 ,那第二次猜 0124 和 0143 的效果是一樣的嗎?
( 嗯,直覺說它們是一樣的。 )

那麼,第二次猜 1032 和 3210 的效果是一樣的嗎? 那和 1230 呢?
( 心中的聲音再次說前兩者是一樣的,後者則未必相同。 )

還有,要如何解釋它們的「效果」是一樣的呢?

我到昨天才仔細去想這個問題,但也因為想通了這個問題,
程式所花的時間從我原本預估的 4 天 ( 我沒跑完,看起來要跑 4 天左右 ),
變成了 9 個小時。

解過八皇后問題的人都知道,在解出來的解當中,有許多組解其實是同一組,
它們之所以不同,只是把棋盤作了旋轉或翻轉而已。

其實今天也我們遇到的也是同樣的情況。
只不過棋盤的旋轉與翻轉變成了「數字的對換」及「位置的互換」而已。

假設 X 和 Y 之間的關係是 1A1B ,(比如說 X=1234, Y=1562)
則我們將 X 和 Y 中的任兩個數字作互換的話,它們之間的關係還是 1A1B 。
(比如說 把其中的 1 和 3 互換,則 X 就變成了 3214 ,Y 就變成了 3562 )

同樣的,我們也可以將數字的位置作對調,也會有同樣的結果,
(比如說,把第一個位置和第二個位置作互換的話,
X 就變成了 2134 ,Y 就變成了 5162 ,而它們之間的關係還是 1A1B )

我們也可以把這種轉換前後的關係,看成是一個 MAP ( FUNCTION ),
它將所猜的數字對應成另一個,而且這種對應是 one-to-one 而且 on to 的對應。

比如說讓 T 代表將前面兩個數字位置對調,
則我們可以寫出 T(1234) = 2134, T(5678)=6578 ,
用式子來寫,則上面的關係就是 label( T(X), T(Y) ) = label( X, Y )。
( label 就是指 ?A?B )

而這樣的 T 總共有 10! * 4! ( 數字的對換有 10! 種,而位置的對換有 4! 種 )

這樣的對換和我們的例子有什麼樣的關係呢?

「如果第一次猜的是 0123 ,那第二次猜 0124 和 0143 效果是一樣的嗎?」

如果我們將第三位置,和第四位置作互換,並將數字 2,3 作對換,
那麼在上面的敘述中 0123 還是 0123 ,但是 0124 就變成了 0143 了,
這樣的對換可以套用再之後的所有數字 (猜的,與可能的數字),

這也就表示猜 0143 所能得到結果,
將等同於猜 0124 所得到的結果再經過上面的所描述轉換而已。

換句話說:「第二次猜 0124 和 0143 的效果其實是完全一樣的」。

這樣的想法,其實不僅能套用在第二次,也可以套用在第三次,甚至是第四次的猜測,
舉例來說,如果第一次猜的是 0123 ,第二次猜的是 5678 ,
則第三次猜 0178 和 5623 其實是一樣的。
( 前後兩位數對調,然後 0 1 分別和 2 3 互換,而 5 6 和 7 8 互換 )

不過在程式裡,我只套用到第三次,因為第四次還有這種對稱的情況就很少了。

以第一次猜 0123 為例,第二次的猜法只有下列 20 種。

0123, 0124, 0132, 0134, 0145, 0214, 0231, 0234, 0245, 0456,
1032, 1034, 1045, 1204, 1230, 1234, 1245, 1435, 1456, 4567

-- 下界( lower bound ) --

我想這是加速的第二個原因了。

我想原理沒什麼特別的,它的想法就是:
「如果目前猜法的 lower bound 和已知最佳解一樣或者更大的話,就不用再往下找了。」

而在這個程式中,求 lower bound 的方式,其原理和之前文章中所描述的方式是一樣的。
但是有一點小小的不同的是,當子節點不大時,我就不再浪費時間去算它精確的 lower bound,
而是直接用 父節點 的 fanout 來算。( 子節點的 fanout 一定小於或等於 父節點的 )。

-- 已確定的數字 --

如果剩下的數字是 0125 0126 0127 0128 0129 。
那麼猜 5617 和 5627 甚至是 5637 他們的效果都是一樣的。

因為 1 2 3 都是確定位置,或者是未出現的,它會形成的 A 和 B 是固定的,
( 比如說,猜 5617 的話,1 所得到的一定是 B,猜 5627 的話 2 一定是 A )

不過要注意的一點是 4A 是比較特殊的情況,所以猜 0125 一定會比 猜 0135 來得好。
(因為 0135 一定猜不中, 0125 有 1/4 的機會喔!)

-- 其它 --

根據 infomation gain 來排序所有可能的猜法,
將最有可能找到最佳解的猜法先作。
如此再撘配 lower bound 的使用,就可以避免在不對的猜法上花太多的時間。

小的子樹先作,因為大的子樹所要花的時間通常要多上許多,
先算出小的子樹將更精確的控制大的子樹的「配額」。
( 比如說,目前找到的最佳解 為總共 100 次,小的子樹已經用掉了 30 次的話,
則大的子樹只能用剩下的 70 次了。 )

最後要說明的是,我並沒有分開去測式每一種改善效率的方式的效能,
上面提到的效果,只是我自己的預測吧了。


owenlin_twn edited on 2006-01-09 06:02
reply to postreply to post
作者 Re:[猜數字系列] 和大家分享我最近寫的猜數字…… ( 最佳解求出來了 5.2131 ) [Re:owenlin_twn]
nadiaInochi





發文: 6
積分: 1
於 2006-01-09 04:40 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
來插個花...
看了你的文章,實在受益良多
我目前的最佳總手數和仍然比你的最佳成績多出4手,目前還在使用前2層完全展開+其他用表內展開的方式向最佳解前進中,不過我的程式對於對稱的刪減沒有做得很好,因此對於每個第三手的猜法最多需要高達1000多小時來計算(用P4 2.4CG With HT,開兩個IE threads一次計算兩個猜法)

目前的最佳成績:
總共26278次 平均5.213889次 最多7次猜中
紀 錄 n次猜中% n次以內%
猜1次 1 0.02% 0.02%
猜2次 7 0.139% 0.159%
猜3次 63 1.25% 1.409%
猜4次 683 13.552% 14.96%
猜5次 2448 48.571% 63.532%
猜6次 1764 35% 98.532%
猜7次 74 1.468% 100%

最新暫時結果顯示在維持總手數和26278次的情況下,猜7次的累計次數還可能進一步減少2次


nadiaInochi edited on 2006-01-09 04:43
reply to postreply to post
作者 Re:[猜數字系列] 和大家分享我最近寫的猜數字…… ( 最佳解求出來了 5.2131 ) [Re:nadiaInochi]
owenlin_twn





發文: 21
積分: 3
於 2006-01-09 06:19 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
nadiaInochi wrote:
最新暫時結果顯示在維持總手數和26278次的情況下,猜7次的累計次數還可能進一步減少2次


嗯,我想你說的沒錯。
關於猜 7 次的次數,是有可能再少的。我目前有想到一些可能的原因。

1. 最佳解必須犧牲第7次的次數以換取第5次或更佳的次數。(我不太相信)
2. 當可能的數字只剩三個以內時,我只用表內搜尋,雖然用表外可能可以降低最多所花的次數。(應該是這樣吧!)
3. 可能有不只一組的最佳解。

下面是第一層子樹的最佳解,不知和你找到的是否相同呢?
它們的總手數應該都小於或等於你找到的吧?!
1
2
3
4
5
6
7
8
9
10
11
12
13
0A0B    1446
0A1B    6495
0A2B    5548
0A3B    1004
0A4B      23
1A0B    1913
1A1B    2992
1A2B     804
1A3B      22
2A0B     659
2A1B     240
2A2B      15
3A0B      73


reply to postreply to post
作者 Re:[猜數字系列] 和大家分享我最近寫的猜數字…… ( 最佳解求出來了 5.2131 ) [Re:owenlin_twn]
nadiaInochi





發文: 6
積分: 1
於 2006-01-09 07:17 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
owenlin_twn wrote:
1. 最佳解必須犧牲第7次的次數以換取第5次或更佳的次數。(我不太相信)


這是可能的,大陸的網友yczni專攻減少7步猜中的次數(你應該在點睛工作室看過他的文章),他7步猜中的累計次數只有54次,不過平均步数要5.2385步,也是個強者喔

我剛找到我更新的資料,只在0A2B那裡比你多3手,其他數據都跟你相同,我猜可能是第二手的猜法跟你不同所致(我目前猜1234得2B後是猜3456,也就是說取沒有重疊的2B )


nadiaInochi edited on 2006-01-09 07:28
reply to postreply to post
作者 Re:[猜數字系列] 和大家分享我最近寫的猜數字…… ( 最佳解求出來了 5.2131 ) [Re:nadiaInochi]
owenlin_twn





發文: 21
積分: 3
於 2006-01-10 05:27 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
nadiaInochi wrote:
這是可能的,大陸的網友yczni專攻減少7步猜中的次數(你應該在點睛工作室看過他的文章),他7步猜中的累計次數只有54次,不過平均步数要5.2385步,也是個強者喔

我剛找到我更新的資料,只在0A2B那裡比你多3手,其他數據都跟你相同,我猜可能是第二手的猜法跟你不同所致(我目前猜1234得2B後是猜3456,也就是說取沒有重疊的2B )


你說的那篇我漏看了說,我只注意到他說他證明了 6 次不可能。
不過,真是沒想到第 7 步的次數可以減少到那種程度。

我去檢查了一下找到的最佳解,在 3 個數字的 node 中,
並沒有利用表外搜尋可以減少最多手的情況。

另外,我去看了一下,猜 1234 得2B 之後,我是猜有一個重疊的 2B ,( 比如說 2356 )。
不知道是不是因為這裡不同所造成的差異。

最後,我今天突然想到一個有趣的問題:「兩人對猜,平均次數較低的猜法其「勝率」一定比較高嗎?」

在某些設計過的例子下,上面的說法是不成立的喔……

我也算了一下一些演算法之間對猜的勝率,(括號內的是輸的機率)

最佳解 v.s. 亂數選(Basic) : 41.6835% ( 26.2978% )
最佳解 v.s. 之前找到平均 5.2155 的解: 31.2887% ( 31.1539% )
最佳解 v.s InfoGain: 32.5933% ( 30.8392% )
InfoGain v.s. 亂數選(Basic): 41.0253% ( 27.4537% )

嗯…… 目前看起來平均低的,勝率確實較高。

但說不一定會有例外,或者……它們之間會有像「剪刀、石頭、布」的情況出現。Big Smile


owenlin_twn edited on 2006-01-10 05:30
reply to postreply to post
作者 Re:平均五次的迷思 - Part II [Re:owenlin_twn]
worookie

Small Ship

版主

發文: 2092
積分: 21
於 2006-01-11 01:25 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
owenlin_twn wrote:
其實要證明平均至少 5 次的概念,和上一篇所用到的概念是一樣的,
只不過為了更逼近其下界(lower bound),我們多往下展開幾層。
也就是說,我們先模擬前幾次的猜法,之後才將上面的推論套用在子節點上,
(略)


很棒的一串討論.
請問您可以把 "證明平均至少 5 次" 這部份的內容整理成一份數學上(analytically/computationally)嚴謹的論文嗎?


reply to postreply to post
作者 Re:平均五次的迷思 - Part II [Re:worookie]
owenlin_twn





發文: 21
積分: 3
於 2006-01-11 08:05 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
worookie wrote:
很棒的一串討論.
請問您可以把 "證明平均至少 5 次" 這部份的內容整理成一份數學上(analytically/computationally)嚴謹的論文嗎?

嗯,謝謝你。Smile
到現在我曾經研究過猜數字三次,就算這次最有突破吧。Big Smile
( 剛剛查了一下,上一次是四年前了……Dead
再上一次是我高中的時候…… 哇!!那是十年多前了耶…… DeadDead )

你說的沒錯,"證明平均至少 5 次"那邊,雖然看起來應該是對的,
但有些地方確實沒有仔細去證明它,我會再仔細想想每一個步驟的正確性。

我也想過是不是可以寫篇關於猜數字的論文,不知道可不可行?


reply to postreply to post
作者 Re:[猜數字系列] 和大家分享我最近寫的猜數字…… ( 最佳解求出來了 5.2131 ) [Re:nadiaInochi]
owenlin_twn





發文: 21
積分: 3
於 2006-01-11 08:58 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
nadiaInochi wrote:
我剛找到我更新的資料,只在0A2B那裡比你多3手,其他數據都跟你相同,我猜可能是第二手的猜法跟你不同所致(我目前猜1234得2B後是猜3456,也就是說取沒有重疊的2B )


我寫了一個可以瀏覽 tree 的小工具,執行的畫面如下。
用這個工具的話,可以快速地告訴我們一些相關的資訊,還蠻有趣的。

在附檔中,還有最佳解的 tree 檔,解開後,直接執行批次檔應該就可以了。



ViewTree.zip (86.38k)


reply to postreply to post
作者 Re:[猜數字系列] 和大家分享我最近寫的猜數字…… ( 最佳解求出來了 5.2131 ) [Re:owenlin_twn]
nadiaInochi





發文: 6
積分: 1
於 2006-01-11 15:04 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
謝謝你提供的程式
查閱了一下,我發現在同樣手數和的情形下,還是可以有不同的7步出現率,
我的0A1B這個分支需要猜到7步的有58個數,2~7步的個數分別是:
1 6 97 547 731 58

我的程式有附加最多還要幾步的計算,最佳解篩選原則是若總手數和相同,
如果有最多只要6步的解,會優先選最多只要6步的解,但如果非得要7次才
能算完全部的解的時候,由於程式並沒有去計算會有幾個7步的解,所以無
法篩選7步出現率最少的解--除非為0


reply to postreply to post
作者 Re:猜數字之最佳解 ( optimal solution ) -- 5.2131 [Re:owenlin_twn]
owenlin_twn





發文: 21
積分: 3
於 2006-01-14 07:18 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
前幾天對程式的一些參數作了一些微調後,速度提升到 3 個半小時解完最佳解。

今天又把對稱性的部份再作了一些改進,
( 我本來是看 「猜過的數字」來決定對稱性,
我現在改用看 「可能的數字」來作對稱性。雖然計算上比較復雜,
但可以使要猜的數字再進一步地減少。)

目前時間上的記錄是 2 小時又 5 分鐘再 37 秒 ( P4 3G )。 Big Smile

附檔中有所有的程式碼、作好的 jar 檔、以及一些找到的最佳樹……
我註解寫的不多,所以如果對程式有任何問題或建議(UI不算喔),
都歡迎直接和我連絡。

這裡摘要一下這些樹的最佳平均次數:

4 位數 10 個數字: 5.2131
4 位數 09 個數字: 4.9319
4 位數 08 個數字: 4.6530
4 位數 07 個數字: 4.3330
4 位數 06 個數字: 4.0167

5 位數 07 個數字: 4.8829

我目前只跑了這些情況的最佳化,如果你要跑比較複雜的情況,
說不一定也是可以啦!但要注意程式是很有可能會跑不完的喔!

下面是用來跑 4 位數 10 個數字的參數下法:
java -cp guess.jar org.fattybobo.guess.Optimize 4 10

接下來可以用下面的指令來看產生出來的樹:
java -cp guess.jar org.fattybobo.guess.ViewTree optimized.tree

guess.zip (171.63k)


owenlin_twn edited on 2006-01-14 07:54
reply to postreply to post
作者 Re:[猜數字系列] 和大家分享我最近寫的猜數字…… ( 最佳解求出來了 5.2131 ) [Re:nadiaInochi]
owenlin_twn





發文: 21
積分: 3
於 2006-01-14 07:42 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
nadiaInochi wrote:
我的程式有附加最多還要幾步的計算,最佳解篩選原則是若總手數和相同,
如果有最多只要6步的解,會優先選最多只要6步的解,但如果非得要7次才
能算完全部的解的時候,由於程式並沒有去計算會有幾個7步的解,所以無
法篩選7步出現率最少的解--除非為0


目前我的程式都沒有去計算這些 ( 目前正在拼速度說…… )

但是我發現一件奇怪的事:7步出現率最少的解,其「勝率」通常反而較低。
我試了好幾個例子,都是這樣子。

1, 7, 62, 692, 2439, 1763, 76 ...... ( A )
1, 7, 62, 691, 2444, 1756, 79 ...... ( B )

( A ) 的勝率會是 31.1961% 而 ( B ) 的勝率會是 31.2282% 。

和我們一般認為的剛好相反說。Dead


reply to postreply to post
作者 Re:猜數字之最佳解 ( optimal solution ) -- 5.2131 [Re:owenlin_twn]
owenlin_twn





發文: 21
積分: 3
於 2006-01-23 00:02 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
這幾天,一方面持續地對程式作改進,一方面也在網路上搜尋相關的資料。

在改進的過程中,也發現了上次版本( 2 小時 5 分版 ) 中的 Bug,
( 算是嚴重的 Bug,有可能會影響到結果,不過在 4x10 的情況剛好看不出來。 )
( 附檔中有修正過後的程式。 )

程式目前已經可以跑進兩小時以內了,我想最佳化的工作到此也算告一段落了。

這個遊戲有許多的名字,一般知道的名字是 MasterMind ,
另外也在英國,他們稱作是 Cow and Bull ,

Cow and Bull 和我們的「猜數字」是一樣的,不過 MasterMind 則有一點不同,
大致上來說,在 MasterMind 中每個數字有 6 個字母,一樣是 4 位數,
但是字母是「可以重覆」的。

早在 1976 年, Knuth ( The Art of Computer Programming 的作者 )
就曾經研究過這個問題了,他提出了一個 greedy 的方式,平均可以到 4.478 次。
之後有許多人提出了更好的 greedy 方式,有些可以到 3.364 次。

在 1993 年的時候, Koyama, K. 以及 Lai, T. W 兩位先生
解出平均次數的最佳解,最小的平均次數是 4.340 次,
不過目前我還沒有讀過那篇 paper ,
只知道他們是用什麼 "backtracing" 的方式去解,不知道那是什麼神奇的方法。

我找了一下,知道在清華大學數學系的圖書館有那本書,我會去借來看看。

最近幾年,這個問題還是陸續有被研究過,而且還是台灣人喔……

國立台灣師範大學 資訊工程研究所 的 林順喜 教授 和他的博士生班學生 陳善泰
在 2003~2004 年也研究過這個問題,並且在 2004 年寫了一篇名為
"Optimal algorithms for 2 x N Mastermind games - a graph-partition approach"
並且登在 "Computer Journal, Vol. 47"

唔!那應該是很好的 journal 呢!

它們以圖形的方式解出了當位數為 2 時的最佳解,很神奇……。

由於之前提到的 lower bound 和 對稱性,在 MasterMind 中也有同樣的性質,
只是實作的方式要作些修改,我現在也改了一版依據 MasterMind 規則的程式。

它解 4x6 的情況只需要不到一分鐘的時間,答案也和前人解的一樣。
我也跑了 4x8 的情形 (剛剛才跑完的),平均是 4.9978 次。
需時 3 個小時又 46 分 11 秒 ( Centrino 1.73 G )。

雖然前人已經有許多研究了,但是令人興奮的是在
Optimal algorithms for 2 x N Mastermind games
這篇論文中有提到:

Because the complexity of these games grows at an exponential
rate, no optimal strategy for them when they have higher dimensions
(i.e., when the games have more than 4 pegs and 6 colors, i.e., 4 × 6)
has yet been found.

如果是真的話,可以寫 paper 的機會就大囉! Smile

參考資料:

而 mastermind 也是一家公司出的遊戲。
http://www.cut-the-knot.org/ctk/Mastermind.shtml/
網頁中有許多的資料。

在 wolfram research (出 mathematica 的公司) 的網頁有許多的參考資料。
http://mathworld.wolfram.com/Mastermind.html

guess.zip (126.81k)


reply to postreply to post
作者 Re:Greedy Algorithms [Re:owenlin_twn]
acad





發文: 1
積分: 0
於 2007-08-19 16:32 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
When i execute "java -jar guess.jar GuessTree besttree.bin" I got exception

Exception in thread "main" java.lang.RuntimeException: java.lang.IllegalArgumentException
  at org.fattybobo.guess.chooser.GuessTreeChooser$Builder.buildChooser(GuessTreeChooser.java:98)
  at org.fattybobo.guess.ChooserFactory.buildChooser(ChooserFactory.java:97)
  at org.fattybobo.guess.Game.main(Game.java:154)
  at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
  at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
  at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
  at java.lang.reflect.Method.invoke(Method.java:597)
  at com.intellij.rt.execution.application.AppMain.main(AppMain.java:90)
Caused by: java.lang.IllegalArgumentException
  at org.fattybobo.guess.GuessTreeNode.<init>(GuessTreeNode.java:69)
  at org.fattybobo.guess.GuessTreeNode.loadTree(GuessTreeNode.java:563)
  at org.fattybobo.guess.chooser.GuessTreeChooser$Builder.loadTree(GuessTreeChooser.java:79)
  at org.fattybobo.guess.chooser.GuessTreeChooser$Builder.buildChooser(GuessTreeChooser.java:88)
  ... 7 more

Where is problem?

P.S. Answer in english, please Smile


reply to postreply to post
作者 Re:[猜數字系列] 和大家分享我最近寫的猜數字…… ( 最佳解求出來了 5.2131 ) [Re:owenlin_twn]
a60301





發文: 2
積分: 0
於 2008-07-28 04:21 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
owenlin_twn wrote:
從以前就陸陸續續地對猜數字作了一些研究,
最近發現這個網站上有許多網友,似乎對這個遊戲也蠻有興趣的,
所以最近寫了一個猜數字的遊戲,和大家分享。

可是這些主要的目的在於研究猜數字,而非遊戲本身,所以介面作的不是很好,
以下是遊戲的畫面(文字模式啦……Big Smile)

1
2
3
4
5
6
7
8
9
create BasicChooser with seed as 1135328405375
start game with random seed as 1135328405375
using chooser: BasicChooser
guess: 1059 ?A?B: 10
guess: 2839 ?A?B: 11
guess: 6489 ?A?B: 01
guess: 2354 ?A?B: 12
guess: 2043 ?A?B: 03
guess: 1234 ?A?B: 40


執行的方式如下:
java -jar guess.jar

預設的 AI 不是最強的,最強的又太慢,建議可以打
java -jar guess.jar InfoGain
用 InfoGain 這個 Guess Chooser ,又快效果也不錯……

因為程式很大,我也就不 post 出來程式碼了,附檔裡有 source code,
一個 jar 檔,和 javadoc 的文件。


對不起,我測試後為6次

guess6times.bmp (819.43k)


reply to postreply to post

http://bobweb.myweb.hinet.net/java/
作者 Re:[猜數字系列] 和大家分享我最近寫的猜數字…… ( 最佳解求出來了 5.2131 ) [Re:owenlin_twn]
人民





發文: 1
積分: 0
於 2008-09-02 01:24 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
我計劃把你的程式改寫為c++程式碼,使用google protocol buffers作為serialize的手段...
想和你聯繫取得許可...


人民 edited on 2008-09-02 01:38
reply to postreply to post
go to first page go to previous page  1   2  go to next page go to last page
» JWorld@TW »  Java 程式分享區 » 數獨、猜數字

reply to topicthreaded modego to previous topicgo to next topic
  已讀文章
  新的文章
  被刪除的文章
Jump to the top of page

JWorld@TW 本站商標資訊

Powered by Powerful JuteForum® Version Jute 1.5.8