一种新的博弈树搜索算法及其应用研究
摘要
机器博弈是人工智能研究领域的一大热点,博弈树搜索则是机器博弈的引擎。本文在博弈树搜索算法和博弈树优化技术等方面做了深入研究,将理论和实践紧密结合,取得了以下的主要创新成果:
⑴提出并成功验证了一种新的博弈树搜索算法:基于广度优先的接力式空窗探测搜索算法。实验证实该方法在实际应用中的平均搜索效率,高于目前公认搜索效率最高、也是最流行的PVS和MTD(f)搜索方法;在迭代深化搜索中,该方法也具有相对优势;并且该算法的最小搜索极限小于极小树。因此,该方法具有广阔的应用前景。
⑵给出了一种新的博弈树优化技术—“子树复用”技术。该技术在几乎不需要额外时间开销的情况下,就能使深层博弈树搜索的效率提高10%以上,并随着搜索深度的加大,效率提高得愈多。“子树复用”技术在限定用时或必胜局面的对弈中还具有额外的实用价值,因而“子树复用”技术无疑具有极好的应用价值。
⑶给出了极小搜索树叶结点数定理的新的证明方法,指出了以前的有关证明的缺陷。针对很多人对极小树的不准确理解,以及对窗口搜索效率的有关误解,给出了正确的结论。
⑷开发了高水平的五子棋人机对弈系统,该系统在估值函数设计上,探索了不同颗粒度估值函数的应用效果,证实粗颗粒度估值函数在深度搜索中可以具有更好的综合效果;部分局面下的估值函数延伸评估技巧,同样可以替代搜索,来减少地平线效应;这些为同行提供了很好的借鉴。证实借助棋类知识的走法生成函数,在五子棋对弈系统中具有很好的效果。在博弈树优化方面,挖掘出极小极大值搜索算法的优势,应用收到了良好的效果。
Computer game is a very popular field in AI, Game-tree search is the key core of computer game. This paper gives profound research is game-tree search algorithm and game-tree optimization technique. The author combines theory and practice presents the following results:
⑴It puts forward a new game-tree search algorithms which based on breadth-first continuously null-window test method. Experiments have proved that the efficiency of this algorithm out-performs the popular algorithms such as PVS and MTD(f) which are considered as having most high efficiencies. The new method also has some advantages in iterative-deepening search, and the search limit of this algorithm is smaller than minimal game-tree. Thus a wide application can be promised by this algorithm.
⑵It gives a new technique of optimizing game tree: sub-game-tree reuse. This technique can improve deep search efficiency by 10 percent and more with deeper depth but no extra expenditure. The sub-game-tree reuse technique has added effect in limit time game or must victory phase. Of course, it has a better application value.
⑶It gives a new proof of the theory about the number bottom-nodes of minimal game-tree, and points out the deficiency of old method. It also clarifies the misunderstanding concepts of minimal tree and window searching efficiency and gives the correct conclusion.
⑷In this paper a high level human-machine playing gobang system is developed, and the author proves that by using evaluation function of rough value the better whole effect in depth searching can acquire, and the extending evaluating technique of the evaluation function also can reduce the horizon effect. The author also testifies that with the help of playing gobang knowledge, the move-generation function can produce good results in human-computer play gobang system. The author also extends use of minimax search algorithm in the optimizing game-tree area and achieves good result. With all these ideas and experiments, the paper provides a good reference to fellow researchers.
⑴提出并成功验证了一种新的博弈树搜索算法:基于广度优先的接力式空窗探测搜索算法。实验证实该方法在实际应用中的平均搜索效率,高于目前公认搜索效率最高、也是最流行的PVS和MTD(f)搜索方法;在迭代深化搜索中,该方法也具有相对优势;并且该算法的最小搜索极限小于极小树。因此,该方法具有广阔的应用前景。
⑵给出了一种新的博弈树优化技术—“子树复用”技术。该技术在几乎不需要额外时间开销的情况下,就能使深层博弈树搜索的效率提高10%以上,并随着搜索深度的加大,效率提高得愈多。“子树复用”技术在限定用时或必胜局面的对弈中还具有额外的实用价值,因而“子树复用”技术无疑具有极好的应用价值。
⑶给出了极小搜索树叶结点数定理的新的证明方法,指出了以前的有关证明的缺陷。针对很多人对极小树的不准确理解,以及对窗口搜索效率的有关误解,给出了正确的结论。
⑷开发了高水平的五子棋人机对弈系统,该系统在估值函数设计上,探索了不同颗粒度估值函数的应用效果,证实粗颗粒度估值函数在深度搜索中可以具有更好的综合效果;部分局面下的估值函数延伸评估技巧,同样可以替代搜索,来减少地平线效应;这些为同行提供了很好的借鉴。证实借助棋类知识的走法生成函数,在五子棋对弈系统中具有很好的效果。在博弈树优化方面,挖掘出极小极大值搜索算法的优势,应用收到了良好的效果。
Computer game is a very popular field in AI, Game-tree search is the key core of computer game. This paper gives profound research is game-tree search algorithm and game-tree optimization technique. The author combines theory and practice presents the following results:
⑴It puts forward a new game-tree search algorithms which based on breadth-first continuously null-window test method. Experiments have proved that the efficiency of this algorithm out-performs the popular algorithms such as PVS and MTD(f) which are considered as having most high efficiencies. The new method also has some advantages in iterative-deepening search, and the search limit of this algorithm is smaller than minimal game-tree. Thus a wide application can be promised by this algorithm.
⑵It gives a new technique of optimizing game tree: sub-game-tree reuse. This technique can improve deep search efficiency by 10 percent and more with deeper depth but no extra expenditure. The sub-game-tree reuse technique has added effect in limit time game or must victory phase. Of course, it has a better application value.
⑶It gives a new proof of the theory about the number bottom-nodes of minimal game-tree, and points out the deficiency of old method. It also clarifies the misunderstanding concepts of minimal tree and window searching efficiency and gives the correct conclusion.
⑷In this paper a high level human-machine playing gobang system is developed, and the author proves that by using evaluation function of rough value the better whole effect in depth searching can acquire, and the extending evaluating technique of the evaluation function also can reduce the horizon effect. The author also testifies that with the help of playing gobang knowledge, the move-generation function can produce good results in human-computer play gobang system. The author also extends use of minimax search algorithm in the optimizing game-tree area and achieves good result. With all these ideas and experiments, the paper provides a good reference to fellow researchers.
引文
[1]D.E. Knuth, R.W. Moore. An analysis of alpha-beta pruning[J]. Artificial Intelligence, 6(4), 1975:293-326.
[2]Tinne Hoff Kjeldsen. John von Neumann’s Conception of the Minimax Theorem: A Journey Through Different Mathematical Contexts. Arch. Hist. Exact Sci 56(2001) 39-68, Springer-Verlag 2001
[3]尚宇红. 极小极大值理论的历史发展[J]. 西北大学学报,第 33 卷第 2 期 2003(4):245-248。
[4]尚宇红. 博弈论前史研究. 博士论文,西北大学,2003
[5]A.L. Brudno, Bounds and valuations for shortening the scanning of variations. Problems of Cybernetics, 1963, 10:225-241
[6] J. Fishburn, R. Finkel, Parallel alpha-beta search on Arachne. Tech. Rept. 394, Computer Sciences Dept., University of Wisconsin, Madison, WI, 1980.
[7] J. Fishburn, Analysis of speedup in distributed algorithms. Ph.D. Thesis, University of Wisconsin, Madison, May, 1981.
[8]A. Plaat, J. Schaeffer, W. Pijls. Best-first and depth-first minimax search in practice. Proceedings of Computing Science in the Netherlands, 1995. Utrecht, the Netherlands, November : 27-28.
[9]J.R. Slagle, J.K. Dixon. Experiment with some programs that search game trees[J]. Journal of the ACM 1969, 2:189-207
[10]J. Pearl, The solution for the branching factor of the alpha-beta pruning algorithm and its optimality. Communications of the ACM, August 1982, 25(8): 559—564.
[11]J. Pearl, Asymptotic properties of minimax trees and game searching procedures, Artificial Intelligence 14,2(1980): 113-138.
[12]J. Pearl. Scout: A simple game-searching algorithm with proven optimal properties. First Annual National Conference on Artificial Intelligence. Stanford, 1980.
[13]A. Reinefeld. T.A. Marsland. A quantitative analysis of minimal window search. IJCAI 1987: 951-954.
[14]G. Baudet. The design and analysis of algorithms for asynchronous multiprocessors. Ph.D. thesis, Department of Computer Science, Carnegie-Mellon University, 1978.
[15] G.M. Baudet, On the branching factor of the alpha-beta pruning algorithm. Artificial Intelligence. 10(1978): 173-199.
[16]H.J. Berliner, Chess as problem solving: The development of a Tactics Analyzer, Ph.D. Thesis, Carnegie-Mellon University, Pittsburgh, March 1974.
[17]J. Gillogy, Performance analysis of the technology chess program, Ph.D. Thesis, Carnegie-Mellon University, Pittsburgh, PA, 1978.
[18]D.J. Slate, L.R. Atkin, Chess 4.5 – The Northwestern University Chess Program, in chess skill in man and machine, P.W. Frey (ed.), Springer-Verlag, New York, 1977, 82-118.
[19] A. Reinefeld, An improvement of the Scout tree-search algorithm, Int. Computer chess Assoc. J. 6,4(1983), 4-14.
[20]T.A. Marsland and M. Campbell, Parallel search of strongly ordered game trees, Computing Surveys 14,4(1982): 533-551.
[21]A. Plaat, J. Schaeffer, W. Pijls. Exploiting Graph Properties of game trees. In Proceedings of AAAI’96, Volume 1(1996): 234-239
[22]J.W. Romein, A. Plaat, H.E. Bal, J. Schaeffer, W. Pijls. Transposition table driven work scheduling in distributed search. AAAI 1999.
[23]A. Plaat, J. Schaeffer, W. Pijls, A. Bruin. A new paradigm for minimax search. Technical Report. TR-CS-94-18. University of Alberta, Edmonton, Alberta, Canada, 1994.
[24]A. Plaat, J. Schaeffer, W. Pijls, A. Bruin. Best-First Fixed-Depth minimax algorithms. Artificial Intelligence, Vol.87(1996a), Nos.1-2:255-293.
[25]J. Schaeffer, A. Plaat. New advances in alpha-beta searching. Proceedings of the 24th ACM computer science conference, 1996: 124-130.
[26]A. Plaat, J. Schaeffer, W. Pijls. An algorithm faster than NegaScout and SSS* in practice*. Computing Science in the Netherlands, 1995: 182-193.
[27]G.C. Stockman. A minimax algorithm better than alpha-beta? Artificial Intelligence 12,2(1979): 179-196.
[28]M.S. Campbell, T.A. Marsland. A comparison of minimax tree search. Artificial Intelligence. 20(1983): 347-367.
[29]T.A. Marsland, A. Reinefeld, J. Schaeffer. Low overhead alternatives to SSS*. Artificial Intelligence 31(1987): 185-199.
[30] 孙伟, 马绍汉. 博弈树搜索算法设计与分析. 计算机学报,1993(5) :361-369
[31]A. Reinefeld. A minimax algorithm faster than alpha-beta*. Advances in Computer Chess 7,1994: 237-250.
[32]J. Schaeffer. The history heuristic and alpha-beta search enhancements in practice. IEEE Transations on Pattern Analysis and Machine Intelligence, November 1989, PAMI-11(1):1203-1212
[33]T.A. Marsland. A review of game-tree pruning+, ICCA Journal 9(1), March, 1986: 3-19
[34]王小春. PC 游戏编程[M]. 重庆:重庆大学出版社,2002
[35]J. Schaeffer. The history heuristic, Journal of the International Computer Chess Association 6,3(1983): 16-19
[36]J. Schaeffer. Experiments in search and knowledge, Ph.D. thesis, Dept. of Computer Science, University of waterloo, 1986
[37]S.G. Akl, M.M. Newborn. The principle continuation and the killer heuristic. ACM annual Conference, 1977: 466-473
[38]A. Bruin, W. Pijls, A. Plaat, Solution trees as a basis for game tree search. Technical report EUR-CS-94-04, May 1994.
[39] H.J. Berliner. The B* tree search algorithm: A best-first proof procedure. Artificial Intelligence, 12:23-40, 1979.
[40]H.J. Berliner, C. McConnell. B* probability based search*. Artificial Intelligence 86 (1996) 97-156.
[41]Y. Bjornsson, T.A. Marsland. Risk management in game-tree pruning. Technical Report TR 98-07
[42]Allis L.V. Searching for solutions in games and artificial intelligence. Ph.D. thesis, University of Limburg, Maastricht, The Netherlands. ISBN 90-9007488-0, 1994.
[43]A.E. Prieditis, E. Fletcher. Two-agent IDA*. Experimental & Theoretical Artificial Intelligence, 10(1998): 451-485.
[44]Qian Liang. The evolution of mulan: some studies in game-tree pruning and evaluationfunction in the game of the amazons. Ph.D. 2003
[45]M.H.M. Winands. Informed search in complex games. Ph.D. 2004
[46]D. Kopec, T.A. Marsland, J.L. Cox, Search. September 4, 2003
[47]C.E. Shannon. Programming a Computer for Playing Chess. Philosophical Magazine, Vol. 41: 256-275, 1950.
[48] A. Newell, J. C. Shaw, H. A. Simon. Chess-Playing Programs and the Problem of Complexity. IBM Journal, Oct, 320-335, 1958.
[49]http://www.chessbase.com/columns/column.asp?pid=102; http://www.chessit.net/file_topic/computerchess/c_briefhistory.htm
[50]http://www.pinqi.net/qi/software.html
[2]Tinne Hoff Kjeldsen. John von Neumann’s Conception of the Minimax Theorem: A Journey Through Different Mathematical Contexts. Arch. Hist. Exact Sci 56(2001) 39-68, Springer-Verlag 2001
[3]尚宇红. 极小极大值理论的历史发展[J]. 西北大学学报,第 33 卷第 2 期 2003(4):245-248。
[4]尚宇红. 博弈论前史研究. 博士论文,西北大学,2003
[5]A.L. Brudno, Bounds and valuations for shortening the scanning of variations. Problems of Cybernetics, 1963, 10:225-241
[6] J. Fishburn, R. Finkel, Parallel alpha-beta search on Arachne. Tech. Rept. 394, Computer Sciences Dept., University of Wisconsin, Madison, WI, 1980.
[7] J. Fishburn, Analysis of speedup in distributed algorithms. Ph.D. Thesis, University of Wisconsin, Madison, May, 1981.
[8]A. Plaat, J. Schaeffer, W. Pijls. Best-first and depth-first minimax search in practice. Proceedings of Computing Science in the Netherlands, 1995. Utrecht, the Netherlands, November : 27-28.
[9]J.R. Slagle, J.K. Dixon. Experiment with some programs that search game trees[J]. Journal of the ACM 1969, 2:189-207
[10]J. Pearl, The solution for the branching factor of the alpha-beta pruning algorithm and its optimality. Communications of the ACM, August 1982, 25(8): 559—564.
[11]J. Pearl, Asymptotic properties of minimax trees and game searching procedures, Artificial Intelligence 14,2(1980): 113-138.
[12]J. Pearl. Scout: A simple game-searching algorithm with proven optimal properties. First Annual National Conference on Artificial Intelligence. Stanford, 1980.
[13]A. Reinefeld. T.A. Marsland. A quantitative analysis of minimal window search. IJCAI 1987: 951-954.
[14]G. Baudet. The design and analysis of algorithms for asynchronous multiprocessors. Ph.D. thesis, Department of Computer Science, Carnegie-Mellon University, 1978.
[15] G.M. Baudet, On the branching factor of the alpha-beta pruning algorithm. Artificial Intelligence. 10(1978): 173-199.
[16]H.J. Berliner, Chess as problem solving: The development of a Tactics Analyzer, Ph.D. Thesis, Carnegie-Mellon University, Pittsburgh, March 1974.
[17]J. Gillogy, Performance analysis of the technology chess program, Ph.D. Thesis, Carnegie-Mellon University, Pittsburgh, PA, 1978.
[18]D.J. Slate, L.R. Atkin, Chess 4.5 – The Northwestern University Chess Program, in chess skill in man and machine, P.W. Frey (ed.), Springer-Verlag, New York, 1977, 82-118.
[19] A. Reinefeld, An improvement of the Scout tree-search algorithm, Int. Computer chess Assoc. J. 6,4(1983), 4-14.
[20]T.A. Marsland and M. Campbell, Parallel search of strongly ordered game trees, Computing Surveys 14,4(1982): 533-551.
[21]A. Plaat, J. Schaeffer, W. Pijls. Exploiting Graph Properties of game trees. In Proceedings of AAAI’96, Volume 1(1996): 234-239
[22]J.W. Romein, A. Plaat, H.E. Bal, J. Schaeffer, W. Pijls. Transposition table driven work scheduling in distributed search. AAAI 1999.
[23]A. Plaat, J. Schaeffer, W. Pijls, A. Bruin. A new paradigm for minimax search. Technical Report. TR-CS-94-18. University of Alberta, Edmonton, Alberta, Canada, 1994.
[24]A. Plaat, J. Schaeffer, W. Pijls, A. Bruin. Best-First Fixed-Depth minimax algorithms. Artificial Intelligence, Vol.87(1996a), Nos.1-2:255-293.
[25]J. Schaeffer, A. Plaat. New advances in alpha-beta searching. Proceedings of the 24th ACM computer science conference, 1996: 124-130.
[26]A. Plaat, J. Schaeffer, W. Pijls. An algorithm faster than NegaScout and SSS* in practice*. Computing Science in the Netherlands, 1995: 182-193.
[27]G.C. Stockman. A minimax algorithm better than alpha-beta? Artificial Intelligence 12,2(1979): 179-196.
[28]M.S. Campbell, T.A. Marsland. A comparison of minimax tree search. Artificial Intelligence. 20(1983): 347-367.
[29]T.A. Marsland, A. Reinefeld, J. Schaeffer. Low overhead alternatives to SSS*. Artificial Intelligence 31(1987): 185-199.
[30] 孙伟, 马绍汉. 博弈树搜索算法设计与分析. 计算机学报,1993(5) :361-369
[31]A. Reinefeld. A minimax algorithm faster than alpha-beta*. Advances in Computer Chess 7,1994: 237-250.
[32]J. Schaeffer. The history heuristic and alpha-beta search enhancements in practice. IEEE Transations on Pattern Analysis and Machine Intelligence, November 1989, PAMI-11(1):1203-1212
[33]T.A. Marsland. A review of game-tree pruning+, ICCA Journal 9(1), March, 1986: 3-19
[34]王小春. PC 游戏编程[M]. 重庆:重庆大学出版社,2002
[35]J. Schaeffer. The history heuristic, Journal of the International Computer Chess Association 6,3(1983): 16-19
[36]J. Schaeffer. Experiments in search and knowledge, Ph.D. thesis, Dept. of Computer Science, University of waterloo, 1986
[37]S.G. Akl, M.M. Newborn. The principle continuation and the killer heuristic. ACM annual Conference, 1977: 466-473
[38]A. Bruin, W. Pijls, A. Plaat, Solution trees as a basis for game tree search. Technical report EUR-CS-94-04, May 1994.
[39] H.J. Berliner. The B* tree search algorithm: A best-first proof procedure. Artificial Intelligence, 12:23-40, 1979.
[40]H.J. Berliner, C. McConnell. B* probability based search*. Artificial Intelligence 86 (1996) 97-156.
[41]Y. Bjornsson, T.A. Marsland. Risk management in game-tree pruning. Technical Report TR 98-07
[42]Allis L.V. Searching for solutions in games and artificial intelligence. Ph.D. thesis, University of Limburg, Maastricht, The Netherlands. ISBN 90-9007488-0, 1994.
[43]A.E. Prieditis, E. Fletcher. Two-agent IDA*. Experimental & Theoretical Artificial Intelligence, 10(1998): 451-485.
[44]Qian Liang. The evolution of mulan: some studies in game-tree pruning and evaluationfunction in the game of the amazons. Ph.D. 2003
[45]M.H.M. Winands. Informed search in complex games. Ph.D. 2004
[46]D. Kopec, T.A. Marsland, J.L. Cox, Search. September 4, 2003
[47]C.E. Shannon. Programming a Computer for Playing Chess. Philosophical Magazine, Vol. 41: 256-275, 1950.
[48] A. Newell, J. C. Shaw, H. A. Simon. Chess-Playing Programs and the Problem of Complexity. IBM Journal, Oct, 320-335, 1958.
[49]http://www.chessbase.com/columns/column.asp?pid=102; http://www.chessit.net/file_topic/computerchess/c_briefhistory.htm
[50]http://www.pinqi.net/qi/software.html