人間は他人から助言を受けてパフォーマンスを上げることができるが, 同じことをコンピュータプレイヤはできるかという問いを立て, 研究を行っている. これまでのコンピュータプレイヤは他プレイヤを考慮しておらず, どのように助言を活用するかを考える必要がある. また, 「助言」として何を与えるべきかも良くわかっていない. まずは他のプレイヤが考えた指手をアドバイスとみなし, 探索延長という形で活用することで性能が改善することを示した.
Shogo Takeuchi: Advice is useful for game AIs: Experiments with alpha-beta search players in Shogi. The 16th Advances in Computer Games Conference (ACG2019), Aug. 2019.
竹内聖悟. アドバイスを活用する協調的ゲームAI. ゲームプログラミングワークショップ2016論文集, pp.21--27, Nov. 2016
複数のプレイヤが利用可能な時に, より良い使い方としてどのような手法があるかについて研究を行っている. 将棋では多数決合議や楽観合議と呼ばれる手法が利用されてきた.
強弱に関係なく全プレイヤが1票持つよりも, 強さなどに応じて重みを変えるべきと考え, 強さ以外の要素も票の重みの計算に加え, 重み付き合議によって性能が改善することを示した.
Shogo Takeuchi: Weighted Majority Voting with a Heterogeneous System in the Game of Shogi. The 2018 Conference on Technologies and Applications of Artificial Intelligence (TAAI2018), pp. 122 - 125, Dec. 2018.
楽観合議は評価値の問題などから同種プログラム間でしか利用できなかったが, 異種プログラム間でも利用できるように工夫を行った.
竹内聖悟, 異種プログラム間における楽観合議について. 情報処理学会研究報告, 2018-GI-40, (2018)
コンピュータ将棋では、評価関数を利用して形勢判断を行う。評価関数とは、局面を入力として、形勢を数値化したものを返す関数である。 この評価関数のパラメータを調整するために機械学習の手法が利用されている。
人間の指手と一致するように調整されているが、人間の指手と一致することは必ずしも強くなることを意味しない。このギャップを埋めるために、調整のための目的関数にメタパラメータを導入し、そのメタパラメータを進化的アルゴリズムにより調整する手法を提案した。
Yoshikuni Sato, Makoto Miwa, Shogo Takeuchi, and Daisuke Takahashi: Optimizing Objective Function Parameters for Strength in Computer Game-Playing, Twenty-Seventh AAAI Conference on Artificial Intelligence (AAAI-13), pp. 869--875, 2013
将棋で提案された機械学習の手法をチェスへと応用した。
山本一成, 竹内聖悟, 金子知適, 保木邦仁. チェスの棋譜を利用した評価関数の学習. ゲームプログラミングワークショップ2010論文集, pp.75--78, Nov. 2010
保木による機械学習手法が登場する前の研究。棋譜の勝敗と評価値から調整を試みた手法である。
竹内聖悟, 林芳樹, 金子知適, 山口和紀, 川合慧. 勝率に基づく評価関数の評価と最適化. 情報処理学会論文誌, Vol.48, No.11, pp.3446--3454 (2007)
Shogo Takeuchi, Tomoyuki Kaneko, Kazunori Yamaguchi and Satoru Kawai: Visualization and Adjustment of Evaluation Functions Based on Evaluation Values and Win Probability, 22nd National Conference on Artificial Intelligence (AAAI-07), pp. 858--863, 2007.
竹内聖悟, 林芳樹, 金子知適, 川合慧. 勝率と評価値の歪みに基づく評価関数調整法 --将棋における進行度差の評価-- . 第11回ゲームプログラミングワークショップ, pp.56--63, Nov. 2006
棋譜を使い、棋譜の勝率と評価値の関係から、評価関数の調整が不十分である特徴の発見を行った。また、その手法をモンテカルロ木探索へと適用し、モンテカルロ木探索手法が苦手とする特徴を確認した。
Shogo Takeuchi, Tomoyuki Kaneko, and Kazunori Yamaguchi: Evaluation of Game Tree Search Methods by Game Records. IEEE Transactions on Computational Intelligence and AI in Games, vol.2, no.4, pp.288-302, Dec. 2010
Shogo Takeuchi, Tomoyuki Kaneko and Kazunori Yamaguchi: Evaluation of Monte Carlo Tree Search and the Application to Go, Proceedings of 2008 IEEE Symposium on Computational Intelligence and Games, pp. 191--198, Perth, Australia, December 15-18, 2008.
竹内聖悟, 金子知適, 山口和紀. 棋譜データにおける勝率を利用したモンテカルロ木探索の性能評価手法. 第13回ゲームプログラミングワークショップ, pp.9--16, Nov. 2008
竹内聖悟, 林芳樹, 金子知適, 山口和紀, 川合慧. 勝率に基づく評価関数の評価と最適化. 情報処理学会論文誌, Vol.48, No.11, pp.3446--3454 (2007)
Shogo Takeuchi, Tomoyuki Kaneko, Kazunori Yamaguchi and Satoru Kawai: Visualization and Adjustment of Evaluation Functions Based on Evaluation Values and Win Probability, 22nd National Conference on Artificial Intelligence (AAAI-07), pp. 858--863, 2007.
囲碁で成功したモンテカルロ木探索手法を将棋へと応用した。将棋ではモンテカルロ木探索手法は向いていないと言われている。評価関数を利用したプレイアウト手法を提案し、従来の評価関数とアルファベータ探索の組み合わせには敵わないが、一定の強さを得ている。
竹内聖悟. 将棋における, 評価値に基づくモンテカルロ木探索へのDynamic Komi の応用. ゲームプログラミングワークショップ2013論文集, pp.50--57, Nov. 2013
竹内聖悟, 金子知適, 山口和紀. 将棋における,評価関数を用いたモンテカルロ木探索. ゲームプログラミングワークショップ2010論文集, pp.86--89, Nov. 2010
竹内聖悟, 金子知適, 山口和紀. 棋譜データにおける勝率を利用したモンテカルロ木探索の性能評価手法. 第13回ゲームプログラミングワークショップ, pp.9--16, Nov. 2008
モンテカルロ木探索のパラメータ調整を試みる手法は様々に提案されている。今回は遺伝的アルゴリズムを使いパラメータ調整を試みるにあたり、適切な目的関数(GAの場合は適応度)の調査を行った。強くするためには対戦結果を用いるのが直接的であるが、時間がかかるという難点がある。調整時間の短縮と強さとのバランスが取れる、適切な目的関数について調査を行った。
竹内聖悟, 金子知適. 探索パラメータの調整に適した目的関数の調査 --モンテカルロ木探索将棋の探索パラメータの調整--. ゲームプログラミングワークショップ2012論文集, pp.84--91, Nov. 2012
手法の高速化にはアルゴリズム自体の高速化と実装やハードウェアによる高速化がある。 シングルCPU の速度向上が頭打ちとなり、マルチコア, マルチCPU による高速化の方向に向かっている現在、ハードウェアの性能を引き出すためには、並列化が必要である。
Zero-suppressed Decision Diagram における単項演算の並列化について提案した。
Shogo Takeuchi, Takahisa Toda, Shin-ichi Minato, "A General Framework for Parallel Unary Operations on ZDDs", The fourth International Workshop on Algorithms for Large-Scale Information Processing in Knowledge Discovery (ALSIP2014), Tainan, Taiwan, 2014.
竹内聖悟, 戸田貴久, 津田宏治, 湊真一. ZDD における単項演算並列化の一般的枠組みの提案. 人工知能学会第92回人工知能基本問題研究会(SIG-FPAI)予稿集, January, 2014.
グラフを列挙索引化する手法、フロンティア法の並列化手法について研究を行った。 マルチCPU 環境ではNon-Uniform Memory Access が使われる。CPU へのタスク割当やメモリ配置によって性能に影響が出るため、それを適切に行う必要がある。
安井 雄一郎, 藤澤 克樹, 竹内 聖悟, 湊 真一. Ulibc ライブラリを用いた共有メモリ型並列 アルゴリズムの高速化. ハイパフォーマンスコンピューティングと計算科学シンポジウム2014, pp.106--115, 2014
Shogo Takeuchi, Jun Kawahara, Akihiro Kishimoto, and Shin-ichi Minato. Shared-Memory Parallel Frontier-Based Search. Seventh International Workshop on Algorithms and Computation (WALCOM2013), pp. 170--181, 2013
竹内聖悟, 岸本章宏. SMP 環境におけるSimpath アルゴリズムの並列化. 電子情報通信学会, 総合大会, DK-2-3, 2012年 3月
ゲーム木探索: 枝刈など
枝刈りを将棋やチェスへと適用した。
竹内聖悟, 金子知適, 山口和紀. 局面の情報を利用した, 静止探索の動的手生成. 第14回ゲームプログラミングワークショップ, pp.156--161, Nov. 2009
竹内聖悟, 金子知適, 山口和紀. 情報量に基づく探索制御手法 --チェスにおけるSingular Extensionへの応用-- . 第12回ゲームプログラミングワークショップ, pp.52--59, Nov. 2007
竹内聖悟, 金子知適, 川合慧. 将棋におけるProbCut の静止探索への応用. 情報処理学会研究報告, 2005-GI-14, Vol.2005, No.14, pp.9--15 (2005)
プレイヤのレーティング解析
プレイヤのレーティングを推測する手法について、floodgate の棋譜を利用することで低コストな推測する手法を提案した。
Shogo Takeuchi and Tomoyuki Kaneko: Estimating Ratings of Computer Players by the Evaluation Scores and Principal Variations in Shogi. 3rd International Conference on Applied Computing and Information Technology (ACIT 2015), July 2015
竹内聖悟, Floodgateの棋譜を利用した悪手の計算とレーティングの関係について. 情報処理学会研究報告, 2015-GI-33, (2015)
グラフ探索アルゴリズムについての研究に取り組んでいる。主に決定グラフを用いたグラフ列挙問題を対象としている。
アイテム集合の上位集合、元のアイテム集合を部分集合として持つ集合、を列挙する手法、オイラー路の列挙をハミルトン路の列挙を使って行う手法など。
Takahisa Toda, Shogo Takeuchi, Koji Tsuda and Shin-ichi Minato. Superset Generation on Decision Diagrams. 9th International Workshop on Algorithms and Computation (WALCOM2015), pp. 317--322, 2015.
Hiroyuki Hanada, Shuhei Denzumi, Yuma Inoue, Hiroshi Aoki, Norihito Yasuda, Shogo Takeuchi and Shin-ichi Minato. Enumerating Eulerian Trails via Hamiltonian Path Enumeration. 9th International Workshop on Algorithms and Computation (WALCOM2015), pp. 161--174, 2015.
列挙索引化アルゴリズムの対象をグラフから線形システムへと変え, プライバシの問題へ適用した.
竹内聖悟, 津田宏治, 佐久間淳, 二分決定図による複数の線形モデルの出力値公開の安全性評価と疾患リスク予測値公開への適用. コンピュータセキュリティシンポジウム2018論文集, pp. 785--792, 2018年10月.