|
|
|
| A Proof for Minimal Game Trees Leaf Node Number Theorem |
| ZHANG Ming-Liang1,2, WU Jun1, LI Fan-Zhang2 |
1.Electronics Information College,Suzhou University of Science and Technology,Suzhou,215011
2.College of Computer Science and Technology,Soochow University,Suzhou,215006 |
|
|
|
|
Abstract A concise proof for minimal game trees leaf node number theorem is presented according to some deficiencies in its pervious proofs, and also some misunderstandings of minimal game-tree are clarified. On the analyses and experiments of the efficiency source of the window searches, this paper reveals the fact that the improvement of the window searches efficiency results from the position of the window. This qualitative conclusion, which contains some inconsistencies from the common knowledge, gives accurate comprehension and utilization of window searches.
|
|
Received: 12 April 2010
|
|
|
|
|
|
[1] Knuth D E,Moore R W.An Analysis of Alpha-Beta Pruning.Artificial Intelligence,1975,6(4): 293-326
[2] Kjeldsen T H.John von Neumanns Conception of the Minimax Theorem: A Journey through Different Mathematical Contexts.Archive History Exact Sciences,2001,56(1): 39-68
[3] Brudno A L.Bounds and Valuations for Shortening the Scanning of Variations.Problems of Cybernetics,1963,10: 225-241
[4] Slagle J R,Dixon J K.Experiment with Some Programs That Search Game Trees.Journal of the Association for Computing Machinery,1969,16(2): 189-207
[5] Fishburn J,Finkel R.Parallel Alpha-Beta Search on Arachne.Techical Report,394.Department of Computer Sciences,University of Wisconsin.Madison,USA,1980
[6] Pearl J.Asymptotic Properties of Minimax Trees and Game Searching Procedures.Artificial Intelligence,1980,14(2): 113-138
[7] Pearl J.Scout: A Simple Game-Searching Algorithm with Proven Optimal Properties // Proc of the 1st Annual National Conference on Artificial Intelligence.Stanford,USA,1980: 143-145
[8] Marsland T A,Campbell M.Parallel Search of Strongly Ordered Game Trees.ACM Computing Surveys,1982,14(4): 533-551
[9] Campbell M,Hoane A,Feng-hsiung H.Deep Blue.Artificial Intelligence,2002,134: 57-83
[10] Plaat A,Schaeffer J,Pijls W,et al.A New Paradigm for Minimax Search.Technical Report,TR-CS-94-18.Department of Computing Science,University of Alberta.Edmonton,Canada,1994
[11] Plaat A,Schaeffer J,Pijls W,et al.Best-First Fixed-Depth Minimax Algorithms.Artificial Intelligence,1996,87(1/2): 255-293
[12] Slate D J,Atkin L R.Chess 4.5-The Northwestern University Chess Program // Frey P W,ed.Chess Skill in Man and Machine,New York,USA: Springer-Verlag,1977: 82-118
[13] Schaeffer J,Plaat A.New Advances in Alpha-Beta Searching // Proc of the 24th ACM Computer Science Conference,1996: 124-130
[14] Plaat A,Schaeffer J,Pijls W.An Algorithm Faster than NegaScout and SSS* in Practice // Proc of Computing Science in the Netherlands,Utercht,Netherlands,1995: 182-193
[15] Lim Y J.On Forward Pruning in Game-Tree Search.Ph.D Dissertation.Singapore,Singapore: National University of Singapore.Department of Computer Science,2007
[16] Veness J,Blair A.Effective Use of Transposition Tables in Stochastic Game Tree Search.IEEE Symposium on Computational Intelligence and Games,2007: 112-116
[17] Hennig P,Stern D,Graepel T.Coherent Inference on Optimal Play in Game Trees // Proc of the 13th International Conference on AISTATS.Chia Laguna Resort,Italy,2010: 326-333
[18] Stockman G C.A Minimax Algorithm Better than Alpha-Beta? Artificial Intelligence,1979,12(2): 179-196
[19] Zhang Mingling,Li Fanzhang.A New Search Method for a Game Tree.Journal of Shandong University (Engineering Science),2009,39(6): 1-8 (in Chinese)
(张明亮,李凡长.一种新的博弈树搜索方法.山东大学学报(工学版),2009,39(6): 1-8) |
|
|
|
2011, Vol. 24 
