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

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

按列印兼容模式列印這個話題 列印話題    把這個話題寄給朋友 寄給朋友    訂閱主題
reply to topicthreaded modego to previous topicgo to next topic
本主題所含的標籤
無標籤
作者 [猜數字系列]深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [精華]
T55555

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2004-02-29 09:49 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
Information about 深綠
http://www.javaworld.com.tw/jute/post/view?bid=35&id=35423&sty=1&tpg=1&age=0

本人在咖啡杯泡了一陣子,因看不慣DeepGreen打遍天下無敵手,決定研發深咖啡. Big Smile

目前DeepCafe 0.1號 CPU 研發成功,馬上挑戰 DeepGreen.
事實證明 DeepCafe 0.1 小勝 DeepGreen !!

目前, DeepCafe 0.1 加了一條規則, 也因為這條規則, 小勝了DeepGreen.

規則:
如果一開始 number of A + number of B == 3 then guess any other 4 numbers no used,
this is try to quickly find the digit missing.

Ex.: "0123" ==> 3A0B
DeepGreen will try to guess
0124, 0125, ..., 0129,
0143, 0153, ..., 0193,
... etc
In worst case, this will eliminate the rest (4 ~ 9) digit by digit.

It is more efficient to do next guess "4567" to eliminate the (8, 9) or (4, 5, 6, 7).

如何證明 DeepCafe 0.1號 優於 DeepGreen 呢?

It is easy, let the DeepGreen guess all possible numbers then take the average.
Which algorithm has better average number will win out.

Below is the code (modified) to test DeepGreen:
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
public class TestDeepGreen {
  
  String answerSet[] = new String[10*9*8*7];
  boolean validSet[] = new boolean[10*9*8*7];
  
  void generateAnswerSet() {
    int i = 0;
    for (int a = 0; a < 10; a++) {
      for (int b = 0; b < 10; b++) {
        if (b == a) { continue; }
        for (int c = 0; c < 10; c++) {
          if (c == a || c == b) { continue; }
          for (int d = 0; d < 10; d++) {
            if (d == a || d == b || d == c) { continue; }
            answerSet[i++] = "" + a + b + c + d;
          }
        }
      }
    }
  }
  
  void initValidSet() {
    for (int i = 0; i < validSet.length; i++) {
      validSet[ i ] = true;
    }
  }
  
  int getA(String s1, String s2) {
    int a = 0;
    for (int i = 0; i < 4; i++) {
      if (s1.charAt( i ) == s2.charAt( i )) { a++; }
    }
    return a;
  }
  
  int getB(String s1, String s2) {
    int b = 0;
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        if (i==j) { continue; }
        if (s1.charAt( i ) == s2.charAt(j)) { b++; }
      }
    }
    return b;
  }
  
  void reduce(String s, int a, int b) {
    for (int i = 0; i < validSet.length; i++) {
      if (!validSet[ i ]) { continue; }
      if ((getA(s, answerSet[ i ]) != a) || (getB(s, answerSet[ i ]) != b)) {
        validSet[ i ] = false;
      }
    }
  }
  
  int guess(String solution) {
    int count = 0;
    for (int i = 0; i < validSet.length; i++) {
      if (!validSet[ i ]) { continue; }
      count++;
      int a = getA(solution, answerSet[ i ]);
      if (a == 4) { break; }
      int b = getB(solution, answerSet[ i ]);
      reduce(answerSet[ i ], a, b);
    }
    return count;
  }
  
  public static void main(String[] args) {
    TestDeepGreen t = new TestDeepGreen();
    t.generateAnswerSet();
  
    int[] guessNb = new int[15];
    for (int i = 0; i < guessNb.length; i++) { guessNb[ i ] = 0; }
  
    for (int i = 0; i < t.answerSet.length; i++) {
      t.initValidSet();
      int guessTimes = t.guess(t.answerSet[ i ]);
      guessNb[guessTimes]++;
    }
    for (int i = 0; i < guessNb.length; i++) {
      System.out.println( i + " => " + guessNb[ i ]);
    }
  
    int sum = 0;
    for (int i = 0; i < guessNb.length; i++) {
      sum += i * guessNb[ i ];
    }
  
    System.out.println(" Average : " +
        sum + " / " + t.answerSet.length + " = " +
        ((double)sum / t.answerSet.length));
  }
}

Compiler and Run, here is the result:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0 => 0
1 => 1
2 => 13
3 => 108
4 => 596
5 => 1668
6 => 1768
7 => 752
8 => 129
9 => 5
10 => 0
11 => 0
12 => 0
13 => 0
14 => 0
 Average : 28024 / 5040 = 5.56031746031746


Which means: 108 numbers, DeepGreen guesses only on 3 times to get it right.
596 numbers, DeepGreen guesses on 4 times to get it right.
... etc

(5040 == total possible numbers; 28024 == 1*1 + 2*13 + 3*108 + ... + 9*5)

Which means DeepGreen by average will guesses your number correctly on 5.560317 times.


BTW:
"5293" "9204" "9214" "9241" "9431" 是DeepGreen 的五大死穴!
要九次才猜中!


Now, let's see the DeepCafe test code:
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
public class TestDeepCafe {
  
    String answerSet[] = new String[10*9*8*7];
    boolean validSet[] = new boolean[10*9*8*7];
  
    void generateAnswerSet() {
        int i = 0;
        for (int a = 0; a < 10; a++) {
            for (int b = 0; b < 10; b++) {
                if (b == a) { continue; }
                for (int c = 0; c < 10; c++) {
                    if (c == a || c == b) { continue; }
                    for (int d = 0; d < 10; d++) {
                        if (d == a || d == b || d == c) { continue; }
                        answerSet[i++] = "" + a + b + c + d;
                    }
                }
            }
        }
    }
  
    void initValidSet() {
        for (int i = 0; i < validSet.length; i++) {
            validSet[ i ] = true;
        }
    }
  
    int getA(String s1, String s2) {
        int a = 0;
        for (int i = 0; i < 4; i++) {
            if (s1.charAt( i ) == s2.charAt( i )) { a++; }
        }
        return a;
    }
  
    int getB(String s1, String s2) {
        int b = 0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (i==j) { continue; }
                if (s1.charAt( i ) == s2.charAt(j)) { b++; }
            }
        }
        return b;
    }
  
    void reduce(String s, int a, int b) {
        for (int i = 0; i < validSet.length; i++) {
            if (!validSet[ i ]) { continue; }
            if ((getA(s, answerSet[ i ]) != a) || (getB(s, answerSet[ i ]) != b)) {
                validSet[ i ] = false;
            }
        }
    }
  
    int guess(String solution) {
        int count = 1;
  
        int a1 = getA(solution, answerSet[ 0 ]);
        if (a1 == 4) { return count; }
        int b1 = getB(solution, answerSet[ 0 ]);
        reduce(answerSet[ 0 ], a1, b1);
  
        // rule #1 :
        if (a1+b1 == 3) {
            count++;
            int a2 = getA(solution, "4567"); // pick any 4 digit not in answerSet[ 0 ]
            if (a2 == 4) { return count; }
            int b2 = getB(solution, "4567");
            reduce("4567", a2, b2);
        }
          
        for (int i = 1; i < validSet.length; i++) { // we start from 1 instead of 0 because we already check the answerSet[ 0 ]
            if (!validSet[ i ]) { continue; }
            count++;
            int a = getA(solution, answerSet[ i ]);
            if (a == 4) { break; }
            int b = getB(solution, answerSet[ i ]);
            reduce(answerSet[ i ], a, b);
        }
        return count;
    }
  
    public static void main(String[] args) {        
        TestDeepCafe t = new TestDeepCafe();
        t.generateAnswerSet();
  
        int[] nb = new int[15];
        for (int i = 0; i < nb.length; i++) { nb[ i ] = 0; }        
  
        for (int i = 0; i < t.answerSet.length; i++) {
             t.initValidSet();
             int guessNumber = t.guess(t.answerSet[ i ]);
             nb[guessNumber]++;
        }          
        for (int i = 0; i < nb.length; i++) { 
            System.out.println( i + " => " + nb[ i ]);
        }
  
        int sum = 0;
        for (int i = 0; i < nb.length; i++) { 
            sum += i * nb[ i ];
        }
        System.out.println(" Average : " + 
                           sum + " / " + t.answerSet.length + " = " + 
                           ((double)sum / t.answerSet.length));
    }
  
}

Compiler and Run, here is the result:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0 => 0
1 => 1
2 => 9
3 => 89
4 => 556
5 => 1746
6 => 1839
7 => 692
8 => 103
9 => 5
10 => 0
11 => 0
12 => 0
13 => 0
14 => 0
 Average : 27987 / 5040 = 5.5529761904761905


As you can see, the average to guess your number correctly, DeepCafe need 5.552976 times

==> DeepCafe win out!!


Note About Program:
(1) 目前偏重 CPU AI 部份, 暫時不做 Performance turning.
If you allow user to continue play the game...
DeepGreen will create more than 5040 String objects each time (and Garbage Collection)
This is why the Test code reuse directly 5040 string objects (instead of create them on each game)
The better way is hard coded, create a big String object contents "5040*4 bytes", and using offset to simulate the answerSet. This will save memory and construct objects time.
And it maybe can usnig swap table element, instead of always perform the loop from beginning of the table for checking... etc

(2) 目前是Algorithm 較量, 不加運氣成份.
In final product, it may use Random function, but add Random in test code will just make the test complexe and incorrect.

(3) 人機界面就留給新手練習吧.

歡迎 深紫, 深紅 等等雜七雜八挑戰霸主地位. Big Smile (Be Careful, DeepCafe 0.2 may coming out soon...)


caterpillar edited on 2005-12-26 00:36
reply to postreply to post
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:T55555]
worookie

Small Ship

版主

發文: 2092
積分: 21
於 2004-02-29 11: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
T55555 wrote:
目前, DeepCafe 0.1 加了一條規則, 也因為這條規則, 小勝了DeepGreen.

規則:
如果一開始 number of A + number of B == 3 then guess any other 4 numbers no used,


這個規則好像不是很有說服力
因為最後平均只減少猜 0.007 次而已
我是沒仔細去看雙方的程式, 但我的
感覺上相差 0.007 次可能只是隨機上的一個誤差


reply to postreply to post
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:worookie]
T55555

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2004-02-29 12:14 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:
這個規則好像不是很有說服力
因為最後平均只減少猜 0.007 次而已
我是沒仔細去看雙方的程式, 但我的
感覺上相差 0.007 次可能只是隨機上的一個誤差

No, there are no any random or precision error.
Because by guessing all numbers, DeepGreen need exactly 28024 times.
And DeepCafe *only* need exactly 27987 times.
If you check the code, or think about statistic, probability, you will know what happend, and why DeepCafe win out.


T55555 edited on 2004-02-29 12:26
reply to postreply to post
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:T55555]
worookie

Small Ship

版主

發文: 2092
積分: 21
於 2004-02-29 12:23 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
T55555 wrote:
No, there are no any random or precision error.
Because by guessing all numbers, DeepGreen need 28024 times.
And DeepCafe *only* need 27987 times.
If you check the code, or think about statistic, probability, you will know what happend, and why DeepCafe win out.


上面都只是我的感覺霸了
我真的沒去看妳們寫的程式
我只是覺得花了那麼多工夫結果效能只增進大概千分之一點多, 好像不是很值得.

看看有沒有人能夠寫出個程式可以少猜個一次或半次的那我就佩服了


reply to postreply to post
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:worookie]
T55555

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2004-02-29 12:31 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:
我只是覺得花了那麼多工夫結果效能只增進大概千分之一點多, 好像不是很值得.

(1) 值得? What do you think the research of deep blue ?
(2) 花了那麼多工夫 ? Not at all. It is just one simple rule. The time was spend on thinking and writing test environement, not the rule itself.

>> 看看有沒有人能夠寫出個程式可以少猜個一次或半次的那我就佩服了

Wait the new version of DeepCafe, I have some ideas...


T55555 edited on 2004-02-29 12:35
reply to postreply to post
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:T55555]
worookie

Small Ship

版主

發文: 2092
積分: 21
於 2004-02-29 12:48 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
T55555 wrote:
No, there are no any random or precision error.


剛剛大概看了一下您的程式
發現您在程式中用了個隨機取的 "0123" 和 "4567"
如果我把它改成 "9876" 和 "0123" 的話, T5 的程式跑出來的結果反而比 Yoshi 的要差 (多上 0.02 次).
除非說 T5 的程式中不管用什麼數字來代替 "0123" 和 "4567" 跑出來的結果都比 Yoshi 的程式好, 不然是無法說服我的.


reply to postreply to post
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:worookie]
jini

SoftLeader Taiwan

版主

發文: 1266
積分: 23
於 2004-02-29 12:53 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
為何不考慮 反向思考 的 邏輯 @@"

reply to postreply to post
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:worookie]
T55555

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2004-02-29 12:57 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:
剛剛大概看了一下您的程式
發現您在程式中用了個隨機取的 "0123" 和 "4567"
如果我把它改成 "9876" 和 "0123" 的話, T5 的程式跑出來的結果反而比 Yoshi 的要差 (多上 0.02 次).
除非說 T5 的程式中不管用什麼數字來代替 "0123" 和 "4567" 跑出來的結果都比 Yoshi 的程式好, 不然是無法說服我的.

You still don't get it.
"0123" is the first answerSet number.
Which is the Yoshi start number.
if Yoshi start by "4567", then DeepCafe will start also by "4567" ( not "0123").
It is not random number. It is base on the "equal" test environment.
I really don't know how to explain to you.
Hope Yoshi or Duncan can explain to you.

the fisrt start number must be the same, the second number you could take any 4 of the rest of 6, the result will be the same, since we guess all possible numbers. (ex. "0123", "0987" ==> the result will be the same) but the fist one must exactly like Yoshi start number, if not, which means you try add "random" stuff, then of course, the result will be incorrect.
(Don't you see the 2 program are almost the same, same answerSet, same guessing order, only DeepCafe add a rule, the same set, same order make sure the test environement is *equal*, no random stuff to influence the result)


T55555 edited on 2004-02-29 13:24
reply to postreply to post
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:T55555]
Yoshi

塵世中一個迷途小書僮

版主

發文: 874
積分: 22
於 2004-02-29 13:33 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
T55555 wrote:

BTW:
"5293" "9204" "9214" "9241" "9431" 是DeepGreen 的五大死穴!
要九次才猜中!



這個死穴要解決很簡單
只要讓第一次猜的數字是answerSet裡的隨便一組就好了
就和金鐘罩罩門會移動一樣,想找也很難

其它的部份等我先去吃個中飯再來研究好了...


reply to postreply to post
YOSHI!
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:T55555]
worookie

Small Ship

版主

發文: 2092
積分: 21
於 2004-02-29 13:36 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
T55555 wrote:
You still don't get it.
"0123" is the first answerSet number.
Which is the Yoshi start number.
if Yoshi start by "4567", then DeepCafe will start also by "4567" ( not "0123").
It is not random number. It is base on the "equal" test environment.
I really don't know how to explain to you.
Hope Yoshi or Duncan can explain to you.

the fisrt start number must be the same, the second number you could take any 4 of the rest of 6, the result will be the same, since we guess all possible numbers. (ex. "0123", "0987" ==> the result will be the same) but the fist one must exactly like Yoshi start number, if not, which means you try add "random" stuff, then of course, the result will be incorrect.
(Don't you see the 2 program are almost the same, same answerSet, same guessing order, only DeepCafe add a rule, the same set, same order make sure the test environement is *equal*, no random stuff to influence the result)


謝謝您的回覆和指正
我在沒完全了解您們的程式前是不該講太多的
無論如何, 我還差一點點就可以被您說服你新增的 rule 是有用的了
那一點點是:
您的程式和 Yoshi 的程式目前都用 "0123" 當作第一次猜的值, 那麼是不是不管用哪組數字來當作第一次猜的值, 結果都是您的比較好呢? 謝謝

最後期待您下一版的程式... 謝謝啦


reply to postreply to post
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:worookie]
Yoshi

塵世中一個迷途小書僮

版主

發文: 874
積分: 22
於 2004-02-29 14: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:
謝謝您的回覆和指正
我在沒完全了解您們的程式前是不該講太多的
無論如何, 我還差一點點就可以被您說服你新增的 rule 是有用的了
那一點點是:
您的程式和 Yoshi 的程式目前都用 "0123" 當作第一次猜的值, 那麼是不是不管用哪組數字來當作第一次猜的值, 結果都是您的比較好呢? 謝謝

最後期待您下一版的程式... 謝謝啦


我覺得這是重點...如果都採用亂數當第一個猜的數字的話
我不覺得DeepGreen會比DeepCafe 0.1表現來得差
而真的要比較二者的優異性,大概要經過大量的數字去測式並且統計才準
因為亂數很難說得準的...

如果我每次猜,都是選擇解集合裡的隨便一組,而非第一組呢?
看來這場仗還有得打...


reply to postreply to post
YOSHI!
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:T55555]
worookie

Small Ship

版主

發文: 2092
積分: 21
於 2004-02-29 14:33 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
T55555 wrote:
(1) 值得? What do you think the research of deep blue ?

關於這個 "減少猜 0.007 次到底直不值得" 的問題和 DeepBlue 的關係, 我要很小心的回答...

我暫時根據兩點來討論:

(1) 假設您的程式比 Yoshi 的程式平均快上了 0.007 次猜中 (所花次數少了千分之ㄧ).
現在暫時不館 Yoshi 的程式, 我調整了一下您的程式中的參數, 結果猜中次數的平均值就有可能相差到 0.02 次.
似乎參數調整就足夠把您新加上的程式的功能給蓋掉了.

(2) 那麼如果拿深藍 (DeepBlue) 那個下西洋棋的程式來討論的話. DeepBlue 要考慮的不僅僅是少猜 0.007 次, 他還要考慮它的整體計算時間 (或他的記憶體使用量等等). 加上那幾行程式後, 雖然可能可以少猜 0.007 次, 但是每次遇到那幾行程式所多花的計算時間會不會多到 0.007 秒呢? 不要忘了現實中的西洋棋比賽是有時間限制的. 深藍的設計原則是在有限的時間內做出最佳的猜測, 而不是在無限的時間內找出必殺絕招.

所以我覺得整體來講為了減少 0.007 次而大費周章的在此討論並不是很值得.
等到下一版的程式可以減少猜 1.000 次時, 我們再來討論其內容才比較值得, 您說是不是?


worookie edited on 2004-02-29 15:05
reply to postreply to post
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:T55555]
T55555

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2004-02-29 22:43 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
>> 看來這場仗還有得打...

唉, 您們還是不明白...
(我已經打贏了, 可是你們還是看不出來, 希望有高高手出來指點你們)

先想想, 如何才能達到公平的測試呢...
我一開始就說撇開 Random 的不準.

並不是只有第一組的number 那麼簡單.
必須所有的 AnswerSet 都相同 (所有組的number都必須相同!! 所以不管你 Random 到如何去避開死穴, 你還是有五個死穴, 你的System 還是沒有進步 --- 對猜所有數字來講 --- 不管你 Random 到如何, to test DeepCafe and DeepGreen, they must using the same Randomed answerSet !!! ==> No more Random to influence the 2 System.)

而且並不是只有使用相同的AnswerSet那麼簡單. 他們必須猜測的Order 相同.
( Check the 2 program the loop is the same order )
要不然, 又是有Random 成份存在, 測試又不準了.

在這種完全相同的測試環境下, DeepCafe 永遠勝出.
(No matter you random to any kind of environment, you must test the 2 system in the same environemt (same random-set, same random-order))

唉, 如果從 program 看不出來, 用 Statistic-Probability 等數學概念想想, 或許你會比較容易了解.

<< DeepCafe 是研究如何減少死穴, 而不是研究如何隱藏死穴 (random), 因為只有死穴減少, 我們才可以說 在相同的環境下 (same random factor), DeepCafe 勝出 >>


T55555 edited on 2004-02-29 23:13
reply to postreply to post
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:T55555]
Yoshi

塵世中一個迷途小書僮

版主

發文: 874
積分: 22
於 2004-02-29 23:39 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
T55555 wrote:
<< DeepCafe 是研究如何減少死穴, 而不是研究如何隱藏死穴 (random), 因為只有死穴減少, 我們才可以說 在相同的環境下 (same random factor), DeepCafe 勝出 >>


戰依然是沒有打完,近期內DeepGreen新版會出來(GUI大眾版DeepGreen已經搶先上市)
,而且還會順勢推出第二波主打
Anti-DeepCafe程式,此程式專打DeepCafe, 目的是為了讓DeepCafe怎麼猜都猜不著
就算被警察抓到了也告不了你~

好吧,我承認我在打嘴炮,如果J2EE的作業如期完成的話
我會重頭把這個討論串好好的研究一次的~~~Approved


reply to postreply to post
YOSHI!
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:T55555]
worookie

Small Ship

版主

發文: 2092
積分: 21
於 2004-03-01 01:26 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
如果說有個人告訴一個媚妹說他的A車跑的比B車快, 並提出他在山坡上滿地大石頭的路上跑兩種車的測試證據 (結果是 A 車在坎珂的路上跑的比 B 車快 0.007 秒).
如果說妹妹提出質疑這樣的證據不過全面, 應該要再提出跑平地路上的數據, 但那個人卻對妹妹說你不董汽車, 要這個媚妹去問一個汽車工程師為什麼A車比B車快? 為何那個人不乾脆就去平地上實際測測讓媚妹相信就好了, 反而要這樣在言語上欺負一個媚妹呢?


T55555 wrote:
唉, 您們還是不明白...
(我已經打贏了, 可是你們還是看不出來, 希望有高高手出來指點你們)


不知道你指的是我不明白你的程式還是你的統計證據?
先聲明我從來沒說過我看明白過妳們的程式, 可是我對你的統計證據到是看的很清楚明白.
事實上就我們的討論而言並沒需要去看程式, 因為我的重點是在你所提出來的證據並不能證明你的程式比較好. 我要討論的是證據而不是程式.
所以你現在要說服的對象並不需要懂 Java. 你必須要說服的對象是一個懂統計數據的人.

再強調一次, 我所說的是我尚未被你所提出來的證據所說服.
結果你要說服的方式不是拿出針對我的質疑提出更充分的證據, 反而是請別的高高手出來解釋, 你這樣逃避的說法不僅不尊重別人會讓別人不愉快, 也沒達到證明你的程式的目的.

你可以很簡單的跑幾次程式, 證明說你用不是 "0123" 的數字也可以跑的比 Yoshi 的程式好. 這樣子我就被說服了. 我覺得這對你來講應該是很簡單的事.


唉, 如果從 program 看不出來, 用 Statistic-Probability 等數學概念想想, 或許你會比較容易了解.

沒錯, 我沒去看妳們的 program, 我想看的只是 statistic 上的統計結果,
您把統計結果拿出來給我看我就相信了, 這不是很簡單的事嗎?
我又從來沒說過你的程式有錯, 我只是說你還需要拿出更多的證據來讓人信服.
目前為止我還沒看到你拿出完整的統計數據.


<< DeepCafe 是研究如何減少死穴, 而不是研究如何隱藏死穴 (random), 因為只有死穴減少, 我們才可以說 在相同的環境下 (same random factor), DeepCafe 勝出 >>

這部分我從一開始就不是很清楚你要表達的是什麼
你的程式和 yoshi 的程式都會產生 5 個死穴, 而這 5 個死穴也各都會變換位置.
看不出哪裡有減少啊.


worookie edited on 2004-03-01 02:42
reply to postreply to post
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:worookie]
TAHO

可愛吧∼∼

版主

發文: 271
積分: 7
於 2004-03-01 01:59 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
我也沒仔細去看測試程式,但是我想 T55555 兄的作法是這樣的:
由 1234 開始,一直到 7890 為止
所有可能的數字『全部』都讓 深綠 & 深咖啡 算過一次
每一種數字需要猜幾次是固定的∼∼
然後將這些次數作總計,發現深咖啡所需花費的總次數比較少
因為是『全部』的可能性都合計起來,並不是取亂數讓程式猜做抽樣
所以理論上它的猜測次數比較少應該是準確的

至於所謂的死穴
例如,目標數字是 1239,首先猜 1234 時,會將一些不可能的數字剔除
然後從剩下的數字中再猜一個,很可能猜到 1235 ,這時對剔除不可能的數字上沒啥幫助
如果接著猜原來沒猜過的數字,如 4567,那一下子就可以排除掉四個數字跟一堆可能性
( T55555 兄應該就是做了這個工作 )


reply to postreply to post
請養成良好的 Java 程式碼慣例 習慣
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:TAHO]
Yoshi

塵世中一個迷途小書僮

版主

發文: 874
積分: 22
於 2004-03-01 02: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
TAHO wrote:
我也沒仔細去看測試程式,但是我想 T55555 兄的作法是這樣的:
由 1234 開始,一直到 7890 為止
所有可能的數字『全部』都讓 深綠 & 深咖啡 算過一次
每一種數字需要猜幾次是固定的∼∼



我的問題在此,試圖讓解集合不停的縮小,
在這裡使用不同的手法,手段,策略
去選出一個適合的,(近似)最佳的選擇來猜

如何證明DeepCafe的策略可以贏過DeepGreen?
我的"策略"就是"使用亂數去選擇下一次解集合要被選出的人"
我還沒有寫出這個程式,目前只有"第一次"是使用亂數選的
後面幾次都是去選解集合裡的第一組
(其實集合沒有順序,這裡指的是array裡第一個遇到的合理猜測值)
那麼肯定DeepCafe已經勝過這個做法嗎? 這個是我的疑問。

我的第二個演算法已經想好了,我覺得有希望可以突破目前DeepCafe的成績,
不過還是要等我過一陣子有空才能開始動工~~

至於TAHO的第二段我看不懂...


Yoshi edited on 2004-03-01 02:27
reply to postreply to post
YOSHI!
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:TAHO]
worookie

Small Ship

版主

發文: 2092
積分: 21
於 2004-03-01 02:13 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
TAHO wrote:
我也沒仔細去看測試程式,但是我想 T55555 兄的作法是這樣的:
由 1234 開始,一直到 7890 為止
所有可能的數字『全部』都讓 深綠 & 深咖啡 算過一次
每一種數字需要猜幾次是固定的∼∼
然後將這些次數作總計,發現深咖啡所需花費的總次數比較少
因為是『全部』的可能性都合計起來,並不是取亂數讓程式猜做抽樣
所以理論上它的猜測次數比較少應該是準確的

我很懷疑你的對其程式作法的解釋
就算你對其程式作法的解釋是正確的, 那照你的說法: T5 程式中只算了 0123~4567 這一部分的數據 (並不是 1234~7890).


至於所謂的死穴
例如,目標數字是 1239,首先猜 1234 時,會將一些不可能的數字剔除
然後從剩下的數字中再猜一個,很可能猜到 1235 ,這時對剔除不可能的數字上沒啥幫助
如果接著猜原來沒猜過的數字,如 4567,那一下子就可以排除掉四個數字跟一堆可能性
( T55555 兄應該就是做了這個工作 )


這個工作有利有弊, 他雖可以較快剔除數字, 但是在判斷位置上就比較慢了.
目前 T5 所提出來的證據還不足以證明這個工作對整體上的判斷有幫助.


worookie edited on 2004-03-01 02:17
reply to postreply to post
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:worookie]
TAHO

可愛吧∼∼

版主

發文: 271
積分: 7
於 2004-03-01 02:46 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:
我很懷疑你的對其程式作法的解釋
就算你對其程式作法的解釋是正確的, 那照你的說法: T5 程式中只算了 0123~4567 這一部分的數據 (並不是 1234~7890).


喔?此話怎講?為什麼只有 0123~4567 ?

worookie wrote:
這個工作有利有弊, 他雖可以較快剔除數字, 但是在判斷位置上就比較慢了.
目前 T5 所提出來的證據還不足以證明這個工作對整體上的判斷有幫助.


我想我說的不夠清楚
程式應該分成兩部分,一是主要的部分,也就是『猜數字』
另一個是用來驗證哪種比較好的『測試』部分
『猜數字』的演算法優劣當然直接看不出來,所以才需要用測試部分來驗證
一般大家會想到的是利用亂數取樣的方式來測試
也就是隨機產生一個數字,讓『猜數字』程式來猜,看這程式需要猜幾次
重複的隨機產生數字,累積個幾十萬次,算平均值
這種『測試』法,是『抽樣』的測試
但是 T55555 兄的『測試』法並不是這樣做的
因為目前兩種『猜數字』程式,並非是從可能的數字中隨機拿一個出來猜,而是有一定順序的
所以如果目標數字固定,不管實驗幾次,程式需要猜測的次數是『固定』的
因此可以算出如果目標數字是 1234,程式需要猜幾次 (定值),1235 需要幾次 (定值)
1236, 1237.....依此類推,一直到 6890, 7890 為止
把所有可能的『目標數字』都是算過一遍
你就可以知道這程式猜某個數字需要幾次 (定值)
T55555 兄想要得到的測試結果並不是他的程式猜『某一個』數字會比較快
而是對『所有目標數字』所需要的猜測次數的總和比較少次

你們想的比較方式是像 SCJP 考試,從題庫抽幾題出來考,分數高的就比較厲害
T55555 想的是,所有的題庫題目都要作答,而不只是挑幾題出來做,答對越多的越厲害


reply to postreply to post
請養成良好的 Java 程式碼慣例 習慣
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:T55555]
T55555

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2004-03-01 03:34 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
其實 DeepCafe 是從 DeepGreen 演變而來.
只是加了一條 Rule.

如果第一次猜測的數目,#A+#B != 3, 那麼DeepCafe 是用DeepGreen 的解法.
所以兩者沒有任何區別.

問題出在 第一次猜測的數目,#A+#B == 3, DeepCafe 不馬上用 DeepGreen 的 next guessing number
而是先用 (another 4 digits), 在用完 (another 4 digits)之後才回到 DeepGreen 的 logic.
所以有些數目, DeepCafe 可能會多猜一次過 DeepGreen ( the time for the another 4 digits guessing )
可是很多數目反而超前DeepGreen 的猜測次數.
對總體(#A+#B==3)的數目來講,DeepCafe 超前 DeepGreen 37 次而已.

(你可以很容易修改程式, to print out what number DeepGreen > DeepCafe, and what number DeepCafe > DeepGreen)

Did you get it ?

如果遊戲已"死"了, 像四子棋, 五子棋, 如果讓電腦先走, 它一定贏你, 也就沒有研究的興趣了.
要不然, 人們總是想精益求精, 不斷挑戰, 不斷求進. 即使是勝億萬分之一.
好像Olympia, 即使是百分之一秒. 至於值得與否, 那就見人見智了.

這將是我最後一次解說, 開始有點厭煩, 也有點累了. 開始覺得是否值得解說了.


T55555 edited on 2004-03-01 04:12
reply to postreply to post
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:worookie]
T55555

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2004-03-01 03:39 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:

再強調一次, 我所說的是我尚未被你所提出來的證據所說服.
結果你要說服的方式不是拿出針對我的質疑提出更充分的證據, 反而是請別的高高手出來解釋, 你這樣逃避的說法不僅不尊重別人會讓別人不愉快, 也沒達到證明你的程式的目的.


I am sorry for that, maybe I am not good at communication with other people or I am not good at explanation. Sorry again for that.
Hope my previous post explains well. If not, I will try explain again.


這部分我從一開始就不是很清楚你要表達的是什麼
你的程式和 yoshi 的程式都會產生 5 個死穴, 而這 5 個死穴也各都會變換位置.
看不出哪裡有減少啊.

You are right the 5 bad numbers still there. The only different for DeepCafe and DeepGreen are the numbers which #A+#B == 3


T55555 edited on 2004-03-01 03:49
reply to postreply to post
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:TAHO]
worookie

Small Ship

版主

發文: 2092
積分: 21
於 2004-03-01 04:07 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
TAHO wrote:
喔?此話怎講?為什麼只有 0123~4567 ?

老實講, 我看不大懂你之前寫的東西, 所以我可能在這部份誤解你的意思了.

不過你要注意! T5 的測試程式是所有的數目都去猜一遍沒錯
但是他猜的方法中的參數的變化並沒有通通都做過一遍.

似乎你還沒發現 T5 的程式中的 "0123" 和 "4567" 是寫死的.
T5 並沒有詳細說明他只用 "0123" 和 "4567" 這兩個參數來跑過一次猜所有的數字, 其結論就可以代表所有的結果.
所以, 要嘛就是 T5 解釋 "0123" 和 "4567" 可以代表所有的參數. (希望他不要又要我自己去研究來幫他解釋為什麼)
不然就是他要把程式中的 "0123" 和 "4567" 用所有可能的參數置換過, 重新跑過程式並和 Yoshi 的相對應且修正過後的同等程式來做比較. 如果用任何不是 "0123", "4567" 跑出來的結果都一樣, 這樣才稱的上是讓人信服的統計數據.


......
你們想的比較方式是像 SCJP 考試,從題庫抽幾題出來考,分數高的就比較厲害
T55555 想的是,所有的題庫題目都要作答,而不只是挑幾題出來做,答對越多的越厲害

對, 沒錯.
但是你忽略了一點. 他只做了 SCJP 的題庫, 他還沒作 SCWCD, SCJA, ... 等等的題庫. 假如 TAHO SCJP 考 100 分, Yoshi SCJP 考 99 分. 但是有可能 TAHO SCWCD 考 99 分, Yoshi 考 100 分. 雖然說很可能 TAHO 確實在 SCWCD 上比 Yoshi 厲害, 但是你只拿出 SCJP 的證據就要別人相信你在所有領域都比 Yoshi 厲害這樣並不能讓人信服.

我從頭到尾並沒說 T5 的程式有錯, 我所說的是他提出的證據還不夠讓人信服.
我希望這個討論串的圓滿結局是 T5 提出一個完整的證據來證明他的方法確實有用, 而不是要我自己去研究 T5 的程式, 如果我研究不出來就說要另外一個高高手來教我如何看懂他的程式.


worookie edited on 2004-03-01 04:55
reply to postreply to post
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:T55555]
worookie

Small Ship

版主

發文: 2092
積分: 21
於 2004-03-01 04:20 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
T55555 wrote:
(你可以很容易修改程式, to print out what number DeepGreen > DeepCafe, and what number DeepCafe > DeepGreen)


如果你一開始就提出這樣的證據來, 那可能就可以省掉大家許多的無謂的討論.
我沒深入去看你的程式, 所以我沒法很容易的去修改你的程式.
不過, 我想這是你的很好的機會去把你的程式修改好後, 把你的新的證據提供出來給大家看.


reply to postreply to post
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:TAHO]
T55555

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2004-03-01 04:23 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
TAHO wrote:
我想我說的不夠清楚
程式應該分成兩部分,一是主要的部分,也就是『猜數字』
另一個是用來驗證哪種比較好的『測試』部分
『猜數字』的演算法優劣當然直接看不出來,所以才需要用測試部分來驗證
一般大家會想到的是利用亂數取樣的方式來測試
也就是隨機產生一個數字,讓『猜數字』程式來猜,看這程式需要猜幾次
重複的隨機產生數字,累積個幾十萬次,算平均值
這種『測試』法,是『抽樣』的測試
但是 T55555 兄的『測試』法並不是這樣做的
因為目前兩種『猜數字』程式,並非是從可能的數字中隨機拿一個出來猜,而是有一定順序的
所以如果目標數字固定,不管實驗幾次,程式需要猜測的次數是『固定』的
因此可以算出如果目標數字是 1234,程式需要猜幾次 (定值),1235 需要幾次 (定值)
1236, 1237.....依此類推,一直到 6890, 7890 為止
把所有可能的『目標數字』都是算過一遍
你就可以知道這程式猜某個數字需要幾次 (定值)
T55555 兄想要得到的測試結果並不是他的程式猜『某一個』數字會比較快
而是對『所有目標數字』所需要的猜測次數的總和比較少次

你們想的比較方式是像 SCJP 考試,從題庫抽幾題出來考,分數高的就比較厲害
T55555 想的是,所有的題庫題目都要作答,而不只是挑幾題出來做,答對越多的越厲害


You got it! TAHO.

And again, DeepCafe is came from DeepGreen.
DeepGreen can change what ever he want.
In the final versoin of his change (by adding as many random as he want). Then again I will just use his last code and add this rule inside it. Then it will become better DeepGreen (which I call DeepCafe ).
The principle is the "same" DeepGreen, one with rule, one without rule, the one with rule always win out.


reply to postreply to post
作者 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [Re:TAHO]
worookie

Small Ship

版主

發文: 2092
積分: 21
於 2004-03-01 04:28 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
Post is deleted

worookie edited on 2004-03-01 07:46
reply to postreply to post
go to first page go to previous page  1   2   3  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