(3.236.228.250) 您好!臺灣時間:2021/04/17 14:30
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:蘇粲程
研究生(外文):Tsan-Cheng Su
論文名稱:應用於黑白棋參數最佳化演算法
論文名稱(外文):Evolutionary Algorithms on Othello Parameter Optimization
指導教授:顏士淨顏士淨引用關係呂俊良
指導教授(外文):Shi-Jim YenChun-Liang Lu
學位類別:博士
校院名稱:國立東華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2016
畢業學年度:104
論文頁數:52
中文關鍵詞:人工智慧電腦對局電腦黑白棋參數最佳化遊戲樹
外文關鍵詞:Artificial IntelligenceComputer GameComputer OthelloParameter OptimizationGame Tree
相關次數:
  • 被引用被引用:0
  • 點閱點閱:81
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在今年人工智慧界的有了重大的突破,在Google DeepMind 公司開發的的圍棋程式Alpha Go戰勝了南韓棋王李世乭,繼1997年後人機大戰有驚人的表現,電腦對局程式是運用人工智慧演算法,其中由於黑白棋的分支度相較於圍棋來的小,通常以min-max搜尋法,配合alpha-beta pruning來設計的黑白棋程式,就擁有能擊敗人類棋士的棋力。
但現今電腦黑白棋,是電腦對電腦的競爭。本論文利用兩個方法,使用min-max search以及alpha-beta pruning更加精確的裁剪。於電腦黑白棋,在本程式使開發過程中有幾個參數會影響到整個棋局的勝負關鍵,因比賽時間的限制,如何利用演算法找到最佳的參數,更顯的重要,且最後在min-max search與alpha-beta pruning中調整參數加快搜尋速度,以提昇終局前的完整搜尋效率。

Artificial intelligence has recently attracted significant media interest when the AlphaGo program developed by Google DeepMind was defeated by Se-dol Lee in South Korea. The news follows the 1997 man versus machine performance where computer game programs utilize artificial intelligence algorithms. The degree of branching in Othello is smaller than Go. Generally, the computer Othello program is designed by MinMax search method with α–β pruning.
Computer Othello is a computer game program that competes with other computer game programs. In this study, the use of two methods, namely, MinMax search and α–β pruning, is more accurate. For computer Othello, this study developed a program that makes several parameters affect the winning or losing of the game. Given the time limitation in the game, algorithms are important to find the best parameters. These parameters are adjusted in the MinMax search with α–β pruning to accelerate the search and enhance its efficiency.

摘要 I
Abstract II
誌謝 III
Table of Contents IV
List of Figures VI
List of Tables VII
Chapter 1 Introduction 1
1-1 Motivation of the Research 2
1-2 Organization of the Dissertation 3
Chapter 2 Introduction to Othello 5
2-1 Othello Game Rule 5
2-2 Development of Computer Othello 7
2-2-1 Evaluation Function 7
2-2-2 Games solved 17
2-2-3 Search Algorithm 19
Chapter 3 Introduction for Parameter Optimization methods 23
3-1 Related Works of Optimizer 23
3-1-1 SaDE 23
3-1-2 jDE 24
3-1-3 JADE 25
3-1-4 MDE_pBX 27
3-2 The Proposed Method for Optimizer Parameter 28
Chapter 4 Experiment and Results 31
4-1 Experiment Setting 31
4-1-1 Experiment Platform 31
4-1-2 Experiment System 32
4-2 Experiment Results 33
4-3 Tournament Results 37
Chapter 5 Conclusions and Future Works 39
5-1 Conclusions 39
5-2 Future Works 39
References 41
APPENDIX A – Results of International Tournament 47
Vita 49


[1] Mackworth, Alan K. "AAAI Is Now the Association for the Advancement of Artificial Intelligence." The Association for the Advancement of Artificial Intelligence! http://www.aaai.org/Organization/name-change.php.
[2] S. Das and P. N. Suganthan “A Survey of the State-of-the-Art,” IEEE Trans. on Evolutionary Computation, vol. 15, no. 1, pp. 4-31, 2011.
[3] R. C. Eberhart and J. Kennedy, “A new optimizer using particle swarm theory,” in Proc. of 6th Int. Symp. Micro Machine and Human Science, Nagoya, Japan, pp. 39-43, 1995.
[4] J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, 1975.
[5] A. K. Qin, V. L. Huang, and P. N. Suganthan, “Differential evolution algorithm with strategy adaptation for global numerical optimization,” IEEE Trans. Evol. Comput., vol. 13, no. 2, pp. 398–417, Apr. 2009.
[6] J. Brest, S. Greiner, B. Boˇskovi´c, M. Mernik, and V. ˇZumer, “Selfadapting control parameters in differential evolution: A comparative study on numerical benchmark problems,” IEEE Trans. Evol. Comput., vol. 10, no. 6, pp. 646–657, Dec. 2006.
[7] S. Das, A. Abraham, U. K. Chakraborty, and A. Konar, “Differential evolution using a neighborhood based mutation operator,” IEEE Trans. Evol. Comput., vol. 13, no. 3, pp. 526–553, Jun. 2009.
[8] J. Zhang and A. C. Sanderson, “JADE: Adaptive differential evolution with optional external archive,” IEEE Trans. Evol. Comput., vol. 13, no. 5, pp. 945–958, Oct. 2009.
[9] Sk. M. Islam, S. Das, Saurav Ghosh, S. Roy and P. N. Suganthan, “An Adaptive Differential Evolution Algorithm With Novel Mutation and Crossover Strategies for Global Numerical Optimization,” IEEE Trans. on System, Man and Cybernetics, Part B - Cybernetics., vol. 42, no. 2, pp. 482–500, Apr. 2012.
[10] Korman, Michael. "Playing Othello with Artificial Intelligence." 2003. Accessed August 6, 2014. mkorman.org.
[11] J. D. Schaffer, Multiple Objective Optimization with Vector Evaluated Genetic Algorithms, Ph.D. thesis, Vanderbilt University, 1984.
[12] E. Zitzler, M. Laumanns and L. Thiele, “SPEA2: improving the performance of the strength pareto evolutionary algorithm,” Technical Report 103, Computer Engineering and Communication Networks Lab (TLK), Swiss Federal Institute of Technology (ETH) Zurich, 2001.
[13] K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Trans. on Evolutionary Computation, vol. 6, no. 2, pp. 182-197, 2002.
[14] M. Buro , “Improving heuristic mini-max search by supervised learning”, Artificial Intelligence, Volume 134, pp. 85-99, Number 1, January 2002.
[15] M. Buro, “The Othello Match of the Year: Takeshi Murakami vs. Logistello”, ICCA Journal, Vol. 20, No. 3, pp. 189-193, 1997.
[16] M. Buro, “How Machines have Learned to Play Othello,” IEEE Intelligent Systems Journal, Vol. 14, No. 6, pp. 12-14, 1999.
[17] J. Kennedy and R. Eberhart, “Particle Swarm Optimization,” in proc. of the Fourth IEEE International Conference on Neural Networks, pp. 1942-1948, 1995.
[18] R. Storn and K. V. Price, “Differential evolution: A simple and efficient adaptive scheme for global optimization over continuous spaces,” ICSI, USA, Tech. Rep. TR-95-012, 1995 [Online]. Available: http://icsi.berkeley.edu/∼storn/litera.html
[19] K. V. Price, “Differential evolution vs. the functions of the 2nd ICEO,” in Proc. IEEE Int. Conf. Evol. Comput., pp. 153–157, Apr. 1997.
[20] A. K. Qin, V. L. Huang, and P. N. Suganthan, “Differential evolution algorithm with strategy adaptation for global numerical optimization,” IEEE Trans. Evol. Comput., vol. 13, no. 2, pp. 398–417, Apr. 2009.
[21] S. Rahnamayan, H. R. Tizhoosh, and M. M. A. Salama, “Oppositionbased differential evolution,” IEEE Trans. Evol. Comput., vol. 12, no. 1, pp. 64–79, Feb. 2008.
[22] S. Das, A. Abraham, U. K. Chakraborty, and A. Konar, “Differential evolution using a neighborhood based mutation operator,” IEEE Trans. Evol. Comput., vol. 13, no. 3, pp. 526–553, Jun. 2009.
[23] J. Zhang and A. C. Sanderson, “JADE: Adaptive differential evolution with optional external archive,” IEEE Trans. Evol. Comput., vol. 13, no. 5, pp. 945–958, Oct. 2009.
[24] S. Das, A. Abraham, U. K. Chakraborty, and A. Konar, “Differential evolution using a neighborhood based mutation operator,” IEEE Trans. Evol. Comput., vol. 13, no. 3, pp. 526–553, Jun. 2009.
[25] S. Rahnamayan, H. R. Tizhoosh, and M. M. A. Salama, “Oppositionbased differential evolution,” IEEE Trans. Evol. Comput., vol. 12, no. 1, pp. 64–79, Feb. 2008.
[26] J. Vesterstrøm and R. A. Thomson, “Comparative study of differential evolution, particle swarm optimization, and evolutionary algorithms on numerical benchmark problems,” in Proc. IEEE Congr. Evol. Comput., pp. 1980–1987, 2004.
[27] K. V. Price, “An introduction to differential evolution,” in New Ideas in Optimization, D. Corne, M. Dorigo, and V. Glover, Eds. London, U.K.: McGraw-Hill, 1999, pp. 79–108.
[28] K. Price, R. Storn, and J. Lampinen, Differential Evolution—A Practical Approach to Global Optimization. Berlin, Germany: Springer, 2005.
[29] Z. Michalewicz, T. Logan and S. Swaminathan, “Evolutionary operations for continuous convex parameter spaces,” in Proc. of the 3rd Annual Conference on Evolutionary Programming, pp. 84-97, 1994.
[30] M. Li and J. Mao, “A new algorithm of evolutional blind source separation based on genetic algorithm,” in Proc. of WCICA 5th world congress on Intelligent Control and Automation, vol. 3, pp. 2240-2244, 2004.
[31] P. Zheng, Y. Liu, L. Tian and Y. Cao, “A blind source separation method based on diagonalization of correlation matrices and genetic algorithm,” in Proc. of WCICA 5th world congress on Intelligent Control and Automation, vol. 3, pp. 2127-2131, 2004.
[32] M. G. H. Omran, A. Salman, and A. P. Engelbrecht, “Self-adaptive differential evolution,” in Proc. Comput. Intell. Security, Lecture Notes in Artificial Intelligence 3801. pp. 192–199, 2005.
[33] E. Mezura-Montes, J. Velázquez-Reyes, and C. A. Coello Coello, “A comparative study of differential evolution variants for global optimization,” in Proc. of GECCO, pp. 485–492, 2006.
[34] R. Gamperle, S. D. Muller, and A. Koumoutsakos, “Parameter study for differential evolution,” in Proc. of WSEAS NNA-FSFS-EC, Interlaken, Switzerland, Feb. 11–15, 2002.
[35] S. T. Hsieh, S. Y. Chiu and S. J. Yen, "Sharing Mutation Genetic Algorithm for Solving Multi-objective Optimization Problems," in Proc. of The 2011 IEEE Congress on Evolutionary Computation, pp. 1833-1839, USA, Jun. 5-8, 2011.
[36] . T. Hsieh, S. Y. Chiu and S. J. Yen, "Real Random Mutation Strategy for Differential Evolution," in Proc. of The 2012 Conference on Technologies and Applications of Artificial Intelligence, pp. 86-90, Taiwan, Nov. 16-18, 2012.
[37] A. A Khokhar, V. K. Prasanna, M. E. Shaaban, and C.-L Wang, “Heterogeneous computing: challenges and opportunities,” IEEE Computer, vol. 26, pp. 18-27, 1993.
[38] T. P. Bagchi, Multiobjective Scheduling by Genetic Algorithms, Springer, 1999.
[39] A. Coello, G. B. Lamont and D. A. Van Veldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems, 2nd, Springer, 2007.
[40] B. Hamidzadeh, L. Y. Kit, and D. J. Lilja, “Dynamic task scheduling using online optimization” IEEE Trans. on Parallel and Distributed Systems, vol. 11, pp. 1151-1163, 2000.
[41] S. Baruah, “Partitioning real-time tasks among heterogeneous multiprocessors,” in Proc. of the 33rd International Conference on Parallel Processing, pp. 467-474, 2004.
[42] S. Baruah, “Task partitioning upon heterogeneous multiprocessor platforms,” in Proc. of the 10th International IEEE Real-Time and Embedded Technology and Applications Symposium, pp. 536-543, 2004.
[43] W. Xia, and Z. Wu, “An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems,” Computers and Industrial Engineering, vol. 48, no. 2, pp. 409-425, 2005.
[44] Z. Jia, H. Chen, and J. Tang, “An Improved Particle Swarm Optimization for Multi-objective Flexible Job-shop Scheduling Problem,” in Proc. of 2007 IEEE International Conference on Grey Systems and Intelligent Services, pp. 1587-1592, 2007.
[45] N. B. Ho, and J. C. Tay, "Solving Multiple-Objective Flexible Job Shop Problems by Evolution and Local Search," IEEE Trans. on System, Man, and Cybernetics-Part C: Applications and reviews, vol. 38, no. 5, pp. 674-685, 2008.
[46] S. Astete-Morales, M.-L. Cauwet, and O. Teytaud, “Evolution Strategies with Additive Noise: A Convergence Rate Lower Bound,” in Foundations of Genetic Algorithms, ser. Foundations of Genetic Algorithms, Aberythswyth, United Kingdom, 2015, p. 9. [Online]. Available: https://hal.inria.fr/hal-01077625
[47] E. Popovici, A. Bucci, R. P. Wiegand, and E. D. de Jong, “Coevolutionary principles,” in Handbook of Natural Computing. New York/Heidelberg, Germany: Springer, 2010.
[48] S. Samothrakis and S. Lucas, “Approximating N-player behavioral strategy Nash equilibria using coevolution,” in Proc. 13th Annu. Conf. Genet. Evol. Comput., 2011, pp. 1107–1114
[49] S. Y. Chong, P. Tino, and X. Yao, “Relationship between generalization and diversity in coevolutionary learning,” IEEE Trans. Comput. Intell. AI Games, vol. 1, no. 3, pp. 214–232, Sep. 2009
[50] S. Y. Chong, P. Tino, D. C. Ku, and X. Yao, “Improving generalization performance in coevolutionary learning,” IEEE Trans. Evol. Comput., vol. 16, no. 1, pp. 70–85, Feb. 2012.
[51] W. Konen and T. Bartz-Beielstein, “Reinforcement learning for games: Failures and successes,” in Proc. 11th Annu. Conf. Companion Genet. Evol. Comput. Conf. Late Breaking Papers, 2009, pp. 2641–2648.
[52] R. Herbrich, T. Minka, and T. Graepel, “TrueSkill(TM): A Bayesian skill rating system,” in Proc. Adv. NIPS, vol. 20. Jan. 2007, pp. 569–57.
[53] J. v. d. Herik H, Jos W Uiterwijk, and Jack van Rijswijck., “Games solved: Now and in the future,” Artificial Intelligence Journal,Vol. 134, No. 1-2, January 2002, pp. 277-311.
[54] Solved game Wiki, https://en.wikipedia.org/wiki/Solved_game, access at Jun, 2016
[55] V. Neumann, Jr. and O. Morgenstern, “Theory of Games and Economic Behavior,” Princeton: Princeton, 1944
[56] J. C. Chen, T. C. Su and S. J. Yen, "TAAI2013 Computer Game Tournaments, "ICGA Journal, vol. 37, no. 1, pp. 40-43, 2014.
[57] S. Y. Chiu, 2013. Evolutionary Algorithms on Numerical Optimization and Scheduling Problems. PhD Thesis. National Dong Hwa University, Hualien, Taiwan.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔