情報処理学会 第75回全国大会講演要旨

囲碁における合法局面中に存在する連と呼ばれる石の集まりの数の
最大値を連数最大値と呼ぶ．19路盤に対する連数最大値問題は，
それと同値な碁盤グラフに対する最小支配点集合問題を0-1整数
計画問題に定式化し，それに対して既存の整数計画ソルバーを適用
することにより既に解かれている．本研究では，0-1整数計画問題
への定式化において対称な最適解の排除をより促す制約式を構成
することにより，従来よりも短時間で連数最大値が求まることを示す．
さらに，碁盤を分割して得られる複数の領域に対する支配点集合を
整数計画ソルバーにより求め，それらの組合せの中から碁盤全体の
最小支配点集合を探索する方法の有効性について述べる．