電腦暗棋程式Darkness的設計與實作
No Thumbnail Available
Date
2013
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
電腦暗棋於2010 年正式加入電腦奧林匹亞競賽，從此開始有許多團隊加入研究的行列。其共通課題皆為：走步與翻子的時機如何掌握？這個問題是相當困難的，想要完滿的解決並不容易。
我們的目的是開發出一款能夠處理翻走問題的暗棋程式，目前來說顯然這是不實際的。在折衷處理之下，本程式以速度為優先考量，同時也希望能夠具有一定水準的棋力。
暗棋程式的棋力強弱，與搜尋的深度息息相關，而搜尋的深度又受電腦硬體以及演算法限制，所以我們的核心目標就是使用各種手段為程式加速，來加強棋力。
本程式使用Alpha-beta pruning以及Bitboard，並搭配Transposition table加速，擁有高速運算的能力，能夠在大部分的局面下走出較好的走步，並在搜尋中避開大量的重複盤面來節省時間。
目前本程式已於TAAI 2012 以及TCGA 2013 分別取得銅牌，比賽中也發現仍然有可修正的部分，接下來將全力發展後續改良設計，期望能於未來的比賽取得更好的成績。
Computer Dark Chess officially became a competition item in the computer Olympiad in 2010. From then on, there are many teams joined this research area. Its common topics are: what's the strategy to choose to "Move" or "Reveal"? This topic is quite difficult; hence perfect solution is not easy to be derived. Our aim is to develop a program which can solve this topic. But, it is clearly not practical at present time. In a compromise deal, speed is the first priority in our consideration. We hope that our program has a stronger ability than others. The ability of Dark Chess program is decided by its searching depth. The searching depth is limited by computer hardware and the algorithms used in the program. Here our core goal is to use a variety of means to speed up and improve the ability of our program. Our program uses alpha-beta pruning algorithm, bitboard structure, and transposition table to achieve a high performance objective. And it can output better moves in most cases, and avoids a huge amount of repeated boards during the search to save time. So far our program has won the bronze medals in TAAI 2012 and TGCA 2013. We still found our many deficiencies during the competitions. We hope that we can continuously improve our program and get good scores in the future competitions.
Computer Dark Chess officially became a competition item in the computer Olympiad in 2010. From then on, there are many teams joined this research area. Its common topics are: what's the strategy to choose to "Move" or "Reveal"? This topic is quite difficult; hence perfect solution is not easy to be derived. Our aim is to develop a program which can solve this topic. But, it is clearly not practical at present time. In a compromise deal, speed is the first priority in our consideration. We hope that our program has a stronger ability than others. The ability of Dark Chess program is decided by its searching depth. The searching depth is limited by computer hardware and the algorithms used in the program. Here our core goal is to use a variety of means to speed up and improve the ability of our program. Our program uses alpha-beta pruning algorithm, bitboard structure, and transposition table to achieve a high performance objective. And it can output better moves in most cases, and avoids a huge amount of repeated boards during the search to save time. So far our program has won the bronze medals in TAAI 2012 and TGCA 2013. We still found our many deficiencies during the competitions. We hope that we can continuously improve our program and get good scores in the future competitions.
Description
Keywords
電腦暗棋, 人工智慧, Chinese Dark Chess, artificial intelligence