全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

极小树叶结点数定理的补充证明及有关分析

, PP. 521-526

Keywords: 极小博弈树,alpha-beta剪枝,MTD(f),空窗探测

Full-Text   Cite this paper   Add to My Lib

Abstract:

通过对博弈树搜索情形的深入分析,给出极小树叶结点数定理新的完整证明,指出以往证明源于对极小搜索树的认识偏差而不完备。对窗口搜索效率来源的细致分析和实验验证,则揭示出博弈树窗口搜索提高效率的首要原因是窗口位置而不是窗口大小。这一与人们的感性认知不符的定性结论,将有助于人们准确理解和运用有关博弈树搜索算法。

References

[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)

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133