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
話題樹型展開
人氣 標題 作者 字數 發文時間
27600 [精華] [猜數字系列]深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 8882 2004-02-29 09:49
24047 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 257 2004-02-29 11:58
24012 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 405 2004-02-29 12:14
23984 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 406 2004-02-29 12:23
24011 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 367 2004-02-29 12:31
23992 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 623 2004-02-29 14:33
23909 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 292 2004-02-29 12:48
23909 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) jini 19 2004-02-29 12:53
23921 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1153 2004-02-29 12:57
23846 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 1143 2004-02-29 13:36
23883 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Yoshi 374 2004-02-29 14:05
23561 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) JiaYun 233 2004-03-01 21:19
23487 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Duncan 745 2004-03-01 23:09
23668 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1384 2004-03-02 00:42
23255 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 874 2004-03-02 01:18
23483 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) JiaYun 692 2004-03-02 01:33
23463 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 155 2004-03-02 01:43
23351 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 834 2004-03-02 02:09
23369 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1966 2004-03-02 02:50
23312 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 2225 2004-03-02 03:03
23207 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 781 2004-03-02 03:14
24688 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 773 2004-03-02 03:19
23341 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 314 2004-03-02 01:55
23369 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) JiaYun 112 2004-03-02 01:58
23425 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) koji 130 2004-03-02 02:02
23897 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Yoshi 227 2004-02-29 13:33
23807 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 870 2004-02-29 22:43
23810 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Yoshi 348 2004-02-29 23:39
23784 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 1267 2004-03-01 01:26
23779 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) TAHO 347 2004-03-01 01:59
23678 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Yoshi 477 2004-03-01 02:12
23634 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 568 2004-03-01 02:13
23612 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) TAHO 858 2004-03-01 02:46
23859 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 998 2004-03-01 04:07
23798 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1042 2004-03-01 04:23
23703 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 0 2004-03-01 04:28
23697 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 402 2004-03-01 05:14
23658 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 447 2004-03-01 05:41
23731 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 292 2004-03-01 05:08
23660 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 399 2004-03-01 05:50
23720 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 180 2004-03-01 05:57
23651 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 294 2004-03-01 09:15
23557 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1446 2004-03-01 06:27
23529 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 1295 2004-03-01 07:25
23606 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1234 2004-03-01 09:12
23581 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 1631 2004-03-01 10:02
23579 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 146 2004-03-01 16:36
23756 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 595 2004-03-01 03:39
23883 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 718 2004-03-01 03:34
23639 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 252 2004-03-01 04:20
23636 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 6047 2004-03-01 05:01
23525 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) TAHO 297 2004-03-01 12:34
23498 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 637 2004-03-01 16:40
23536 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 137 2004-03-01 16:45
23426 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 236 2004-03-01 17:31
23461 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 756 2004-03-01 17:04
23454 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 971 2004-03-01 18:35
23567 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) ramb 753 2004-03-01 18:01
23325 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1046 2004-03-02 01:11
23404 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) TAHO 716 2004-03-01 18:23
23496 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 847 2004-03-01 18:44
23511 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