The Realization Probability Search Based on Search Results

IR IPSJ HANDLE Web Site Open Access

Bibliographic Information

Other Title
  • 探索結果を利用した実現確率探索
  • タンサク ケッカ オ リヨウ シタ ジツゲン カクリツ タンサク

Search this article

Description

本論文では，探索結果に基づく実現確率探索を提案する．実現確率による探索打ち切りアルゴリズム（実現確率探索）は，コンピュータ将棋において注目を集めている探索法の1つであり，多くのトップレベルのプログラムがこのアルゴリズムをベースとした探索法を用いている．実現確率探索は探索深さの決定にプロの棋譜から求めた指し手の確率を用いることで，ありえそうな展開を深く探索するという特長を持つアルゴリズムである．この手法は，多くの場面において優れた結果を収めているものの，プロの棋譜から求めた確率を利用するため，プログラムの探索手法や評価関数の性質によらず確率がつねに固定である点に改善の余地があると考えられる．また，実現確率探索では「王手」「駒を取る手」といった表面的な特徴から確率を算出するが，これらの特徴に加え，探索中の履歴を考慮することでさらに性能を改善することができる可能性があると考えられる．本論文ではこれらの点について，プログラムの探索結果を利用し，評価関数や探索の深さに応じた確率を利用する，探索中に得られる情報を特徴として利用する，といった改良を行うことにより改善を試みた．実験の結果，提案手法は全幅探索や従来の実現確率探索に勝ち越すことに成功し，その有効性を示した．

In this paper, we propose a realization probability search algorithm based on search results. The realization probability search is one of the search algorithms attracting much attention in the Computer-Shogi area, and it is used by many top-level programs. This method determines search depths according to probabilities of moves obtained from game records by professional players, and searches deeper for more probable moves. The realization probability search is an efficient algorithm, but it is considered that it still has room for improvement because probabilities of moves are fixed at any time. We improved the realization probability search by using the search results. In our method, probabilities change according to the rest of search depths and heuristics obtained while searching. In the result of our experiments, our program based on the proposed method is superior to existing methods.

Journal

  • IPSJ Journal

    IPSJ Journal 51 (11), 2021-2030, 2010-11-15

    一般社団法人情報処理学会

Keywords

Details 詳細情報について

Report a problem

Back to top