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

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

按列印兼容模式列印這個話題 列印話題    把這個話題寄給朋友 寄給朋友    訂閱主題
reply to postflat 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
話題樹型展開
人氣 標題 作者 字數 發文時間
27677 [精華] [猜數字系列]深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 8882 2004-02-29 09:49
24113 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 257 2004-02-29 11:58
24081 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 405 2004-02-29 12:14
24049 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 406 2004-02-29 12:23
24078 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 367 2004-02-29 12:31
24057 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 623 2004-02-29 14:33
23975 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 292 2004-02-29 12:48
23974 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) jini 19 2004-02-29 12:53
23992 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1153 2004-02-29 12:57
23910 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 1143 2004-02-29 13:36
23947 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Yoshi 374 2004-02-29 14:05
23626 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) JiaYun 233 2004-03-01 21:19
23553 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Duncan 745 2004-03-01 23:09
23738 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1384 2004-03-02 00:42
23322 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 874 2004-03-02 01:18
23550 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) JiaYun 692 2004-03-02 01:33
23532 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 155 2004-03-02 01:43
23417 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 834 2004-03-02 02:09
23437 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1966 2004-03-02 02:50
23377 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 2225 2004-03-02 03:03
23275 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 781 2004-03-02 03:14
24759 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 773 2004-03-02 03:19
23410 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 314 2004-03-02 01:55
23435 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) JiaYun 112 2004-03-02 01:58
23490 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) koji 130 2004-03-02 02:02
23964 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Yoshi 227 2004-02-29 13:33
23874 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 870 2004-02-29 22:43
23876 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Yoshi 348 2004-02-29 23:39
23852 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 1267 2004-03-01 01:26
23843 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) TAHO 347 2004-03-01 01:59
23743 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Yoshi 477 2004-03-01 02:12
23701 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 568 2004-03-01 02:13
23678 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) TAHO 858 2004-03-01 02:46
23923 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 998 2004-03-01 04:07
23864 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1042 2004-03-01 04:23
23770 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 0 2004-03-01 04:28
23765 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 402 2004-03-01 05:14
23725 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 447 2004-03-01 05:41
23798 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 292 2004-03-01 05:08
23726 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 399 2004-03-01 05:50
23784 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 180 2004-03-01 05:57
23718 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 294 2004-03-01 09:15
23622 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1446 2004-03-01 06:27
23596 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 1295 2004-03-01 07:25
23672 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1234 2004-03-01 09:12
23646 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 1631 2004-03-01 10:02
23645 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 146 2004-03-01 16:36
23825 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 595 2004-03-01 03:39
23948 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 718 2004-03-01 03:34
23705 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 252 2004-03-01 04:20
23702 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 6047 2004-03-01 05:01
23591 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) TAHO 297 2004-03-01 12:34
23564 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 637 2004-03-01 16:40
23601 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 137 2004-03-01 16:45
23494 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 236 2004-03-01 17:31
23528 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 756 2004-03-01 17:04
23523 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 971 2004-03-01 18:35
23633 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) ramb 753 2004-03-01 18:01
23391 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1046 2004-03-02 01:11
23469 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) TAHO 716 2004-03-01 18:23
23559 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 847 2004-03-01 18:44
23576 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) TAHO 12 2004-03-01 18:48
» JWorld@TW »  Java 程式分享區 » 數獨、猜數字

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

JWorld@TW 本站商標資訊

Powered by Powerful JuteForum® Version Jute 1.5.8