完整后设资料纪录
DC 栏位语言
dc.contributor.author杨秉恩en_US
dc.contributor.authorYang, Ping-Enen_US
dc.contributor.author吴毅成en_US
dc.contributor.authorWu, I-Chenen_US
dc.date.accessioned2014-12-12T02:35:59Z-
dc.date.available2014-12-12T02:35:59Z-
dc.date.issued2013en_US
dc.identifier.urihttp://140.113.39.130/cdrfb3/record/nctu/#GT070056102en_US
dc.identifier.urihttp://hdl.handle.net/11536/72774-
dc.description.abstract近来蒙地卡罗树状搜寻(Monte Carlo Tree Search;简称MCTS)方法,已相当成功地应用于电脑围棋程式;工作层级搜寻(Job-level Search)方法,最近也成功地应用于解六子棋开局问题。本论文的研究方向是将此两项技术结合,成为工作层级MCTS(Job-level MCTS;简称JL-MCTS),并将其应用于解7x7 Killall围棋问题。
对于JL-MCTS,我们设计一些预先更新策略(Pre-update Policy),分析对平行化的效率。而为了解7x7 Killall 围棋,由于搜寻树太庞大,我们利用资料库解决记忆体使用问题,并改善资料库存取效率与解决同步问题。另外,为了不浪费运算资源,我们使用Transposition Table,但因此产生了GHI问题(Graph History Interaction),为了解决GHI问题,我们提出一新的GHI问题解决方法,来解出7x7 Killall围棋的盘面。
最后我们解出一个仅有四子的7x7 Killall围棋开局盘面,总共算了37,792,301个节点,若使用288核心,将耗时89天,这是目前可能解出之围棋开局中,有最多空点的盘面。
zh_TW
dc.description.abstractMonte Carlo tree search has been successfully applied to the improvement of Go program strengths, and Job-level Search has been successfully applied to solving Connect6 openings. We combine the two techniques into Job-level Monte Carlo Tree Search(JL-MCTS) and use it to solve the game of 7x7 Killall-Go.
Several pre-update policies were designed for our JL-MCTS. Experiments were performed to compare the parallelized efficiency of each policy. In order to solve 7x7 Killall-Go , for which the search tree memory requirements are huge, we provided a solution to store the search tree into a database, which solved the problem of access efficiency and synchronization. The GHI (Graph History Interaction) problem for Go was also an issue since transposition tables were used. For solving 7x7 Killall-Go correctly, we designed a new approach to solve the GHI problem.
We have solved a 7x7 Killall-Go position with only four stones on the board, which is computed in parallel with 288 cores by 37,792,301 nodes and 89 days. This is one of the most difficult Killall-Go openings that have been solved to date because of its larger board size and the large amount of playable space involved.
en_US
dc.language.isozh_TWen_US
dc.subject蒙地卡罗zh_TW
dc.subject蒙地卡罗树状搜寻zh_TW
dc.subject工作层级搜寻zh_TW
dc.subject围棋zh_TW
dc.subject杀光围棋zh_TW
dc.subjectGHI问题zh_TW
dc.subject资料库zh_TW
dc.subjectMonte Carloen_US
dc.subjectMonte Carlo Tree Searchen_US
dc.subjectJob-level Searchen_US
dc.subjectGoen_US
dc.subjectKillall-Goen_US
dc.subjectGHI Problemen_US
dc.subjectDatabaseen_US
dc.title工作层级蒙地卡罗树状搜寻之研究zh_TW
dc.titleA Study of Job-level Monte Carlo Tree Searchen_US
dc.typeThesisen_US
dc.contributor.department资讯科学与工程研究所zh_TW
显示于类别:Thesis