MOO An optimal MOO strategy Tetsuro Tanaka, Faculty of Engineering, University of Tokyo tanaka@ipl.t.u-tokyo.ac.jp MOO ( ) (exhaustive search). [1], MOO. MOO,.,, 0.5., MOO. 1 MOO MOO, Hit & Blow, Cow & Bull, 1.. 2 4 ( MOO ),. 0586 0., MOO. MOO bull ( ) cow( ). 2 MOO bull, cow MOO. MOO 4 bull. 4 bull.. 1 MUD(Multi User Dungeon). 1
, 1 3951 1 0123 2C 2 1245 2C 3 2671 1B 4 2850 1B 5 9351 2B2C 6 3951 4B 1: MOO. ( ) 6 MOO, MOO, BSD Unix MOO. 2 MOO, bull, cow MOO. [2] 1971.,,,,. MOO,, [3], [4] shell., MOO [2]. MOO 5040 ( 10 P 4 ). MOO,, 5040 MOO MOO. MOO π, MOO T, 4B, 3B, 2B2C, 2B1C, 2B, 1B3C, 1B2C, 1B1C, 1B, 4C, 3C, 2C, 1C, 0C 14, π t 1,..., t 14. f(t ), T. 2
J. Larmouth, n log(n), f(t )= t i log( t i )( 2log2 if T π) i [1,14],t i 0, 5.24., B. Landy f(t )=max( t i ) 14 f(t )= t i log(1 + t i ) i=1 14 f(t )= T i F ( t i ) where F (n) is the solution of x x = n i=1. 1987 bit [5]. f(t ),., B.Landy, 5.22( 26347). 3 f(t ), t 1,..., t 14 5040,,., 2., 5040 MOO, 1,.,,. [2],, This is far too expensive on computation.. [1]., 6 4 = 1296, MOO 10 P 4 = 5040, 3
4,,,., 1. 2. 3.,., (Sparc Station 20), 60, 30 ( 26274).. 4 4.1 MOO, 26. 16, 4 10 1 packed decimal. 10, 0-9 MOO 1. MOO a, b bull, a ^ b (^ ) 16 10 0., 64K. cow a & b 10 1, bull., 1K. MOO. typedef int Question2; int moo(question2 q1,question2 q2) { int bull,cow; } bull=bulltable[(q1^q2)&0xffff]; cow=cowtable[(q1&q2)>>16]; return(moo_product[bull][cow]); SS20, 3. 5040x5040, 1, 1 25M (1 4 12.5M ). 4
4.2 5040 5040.. ([1234,3456,1256] [0,7,8,9] ). (1 0123 2 1234 [5,6,7,8,9] ),,,.,.. 1. {a 1,a 2,..., a n }(a 1 <a 2 <... < a n ), a 1,a 2,... 2.,, ( 4! = 24),., 1 0123. 2 4567, 0456, 4056, 0145, 0415, 4501, 1045, 1405, 0124, 0142, 0214, 0241, 1204, 1240, 1023, 1032, 0231, 1230) 19 3, 4, 1900, 5040. 4.3 1,2,3 1,2,3,.. 1 1 5
2 2 3 3 2 3 1 5 3 6 6 3 6
4.4, 5040 heap sort. heap sort., n n 14, 1 1, 2 n 1,, 1+2(n 1) = 2n 1.,., (4-10)., n(4 n 10) MOO, m 1. 10,, 3 80, 9 3, 59. 1. 1, 10 2. 5,. C 800. 1, 14, (0-13),., 14,. 7
1: n 1 2 3 4 4 12 24 5 8 45 109 6 11 78 276 7 13 101 494 8 14 114 674 9 14 122 783 10 14 127 864 2: 10 (n) 1 n 14 2n 1 15 n 127 3n 15 128 n 864 4n 142 865 n 5n 1006 C gcc, SS20., 27 26274( 5.213). 3.,, 4, 5040 MOO. 6 MOO,?. MOO,,, 3, 1 2.,. ( 0.5 ) γ n, Γ n = γ n 5040 2 5040. 8
3: 1 2 ( ) 4B 1 0 0.0 2B2C 0132 6 15 0.0 1B3C 0134 8 22 0.1 4C 1230 9 23 0.1 3B 0245 24 73 0.5 2B1C 0145 72 240 2.1 2B 0245 180 659 2:08.3 1B2C 0245 216 804 1:48.3 3C 1435 264 1004 5:00.5 0C 4567 360 1446 2.1 1B 0456 480 1913 2:52.5 1B1C 0245 720 2992 9:28.6 2C 1245 1260 5548 2:12:29.7 1C 1456 1440 6495 24:24:47.2 4: 1 2 3 4 5 6 7 1 7 63 697 2424 1774 74 9
. 5. 5: 1 2 3 4 5 6 7 8 5039 5032 4969 4272 1848 74 0 0 0 1 8 71 768 3192 4966 5040 1 7 63 697 2424 1774 74 0 (Γ n ) 5039 5041 4961 4201 1080-3118 -4966-5040, (, ). 58.,,. 6. 6: 1 2 ( ) 4B 1 0 0.0 2B2C 0214 6 16 0.5 1B3C 0134 8 22 0.5 4C 1034 9 24 0.5 3B 0456 24 74 1.2 2B1C 0145 72 240 17.4 2B 0456 180 661 4:01.8 1B2C 0245 216 804 3:48.9 3C 1435 264 1004 7:29.5 0C 4567 360 1449 10.2 1B 0456 480 1915 38:18.1 1B1C 0145 720 2996 1:46:15.2 2C 1245 1260 5555 16:23:42.8 1C 1456 1440 6512 38:56:42.9, 5.221 ( 26312),,, 50.20823 %., 50 % 10
, 50%. A, B, C, A>B,B>C,C>A,.,. 52,, 0.5.,. 7. 5. 7: 1 2 3 4 5 6 7 8 1 7 63 697 2424 1774 74 0 1 4 47 688 2531 1628 141 0 7 C, 850, 650.,., WWW (http://www.ipl.t.u-tokyo.ac.jp/~tanaka/moo/moo.html),., Knuth TeX,.,, Lisp,.,,. 8 MOO.,, 11
,., 1.,,, MOO,,. 2.,,.., n, n,.,.,. [1] Kenji Koyama, Tony W.Lay: An optimal Mastermind Strategy, J. Recreational Mathematics, Vol. 25, No. 4, pp. 251-256 (1994). [2] ℵ 0 : Computer Recreations. SOFTWARE, Vol. 1, No. 2, pp. 201-204 (1971). [3] MOO,, pp. 93-125 (1979). [4] srekcah@sra.junet: Shell (2),, Vol.1, No.2, pp. 80-83 (1986). [5] :, bit, Vol.19, No.7 (1987). [6] Donald E.Knuth: The Computer as Master Mind, J. Recreational Mathematics Vol. 9, No. 1, pp. 1-6 (1976-77). 12