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
話題樹型展開
人氣 標題 作者 字數 發文時間
27740 [精華] [猜數字系列]深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 8882 2004-02-29 09:49
24161 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 257 2004-02-29 11:58
24134 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 405 2004-02-29 12:14
24100 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 406 2004-02-29 12:23
24127 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 367 2004-02-29 12:31
24110 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 623 2004-02-29 14:33
24026 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 292 2004-02-29 12:48
24022 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) jini 19 2004-02-29 12:53
24043 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1153 2004-02-29 12:57
23959 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 1143 2004-02-29 13:36
23996 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Yoshi 374 2004-02-29 14:05
23678 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) JiaYun 233 2004-03-01 21:19
23604 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Duncan 745 2004-03-01 23:09
23789 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1384 2004-03-02 00:42
23372 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 874 2004-03-02 01:18
23601 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) JiaYun 692 2004-03-02 01:33
23582 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 155 2004-03-02 01:43
23466 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 834 2004-03-02 02:09
23488 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1966 2004-03-02 02:50
23427 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 2225 2004-03-02 03:03
23326 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 781 2004-03-02 03:14
24815 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 773 2004-03-02 03:19
23460 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 314 2004-03-02 01:55
23485 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) JiaYun 112 2004-03-02 01:58
23539 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) koji 130 2004-03-02 02:02
24016 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Yoshi 227 2004-02-29 13:33
23923 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 870 2004-02-29 22:43
23926 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Yoshi 348 2004-02-29 23:39
23903 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 1267 2004-03-01 01:26
23892 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) TAHO 347 2004-03-01 01:59
23792 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Yoshi 477 2004-03-01 02:12
23750 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 568 2004-03-01 02:13
23729 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) TAHO 858 2004-03-01 02:46
23974 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 998 2004-03-01 04:07
23916 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1042 2004-03-01 04:23
23821 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 0 2004-03-01 04:28
23816 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 402 2004-03-01 05:14
23776 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 447 2004-03-01 05:41
23849 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 292 2004-03-01 05:08
23775 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 399 2004-03-01 05:50
23836 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 180 2004-03-01 05:57
23769 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 294 2004-03-01 09:15
23671 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1446 2004-03-01 06:27
23647 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 1295 2004-03-01 07:25
23722 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1234 2004-03-01 09:12
23697 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 1631 2004-03-01 10:02
23696 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 146 2004-03-01 16:36
23878 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 595 2004-03-01 03:39
23996 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 718 2004-03-01 03:34
23754 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 252 2004-03-01 04:20
23752 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 6047 2004-03-01 05:01
23641 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) TAHO 297 2004-03-01 12:34
23613 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 637 2004-03-01 16:40
23651 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 137 2004-03-01 16:45
23546 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 236 2004-03-01 17:31
23576 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 756 2004-03-01 17:04
23571 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 971 2004-03-01 18:35
23685 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) ramb 753 2004-03-01 18:01
23440 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1046 2004-03-02 01:11
23518 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) TAHO 716 2004-03-01 18:23
23607 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 847 2004-03-01 18:44
23627 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