囲碁における連数の最大値について

• Item type: Journal(1)
• 公開日: 2007-11-15
• タイトル: 囲碁における連数の最大値について
• タイトル / 言語: en
• タイトル: On the Maximum Number of Strings in Go
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 特集：ゲームプログラミング
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 解析
• 著者所属: 東京農工大学
• 著者所属: 電気通信大学
• 著者所属: 電気通信大学
• 著者所属(英): en
• 著者所属(英): Tokyo University of Agriculture and Technology
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications
• 著者名: 宮代, 隆平; 矢野, 洋平; 村松, 正和
• 著者名(英): Ryuhei, Miyashiro; Yohei, Yano; Masakazu, Muramatsu
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 囲碁の盤上において，縦または横に連結している同じ色の石の極大集合を連と呼ぶ．連数最大化問題とは，「囲碁のルールの下でn 路盤上に最大でいくつの連が存在できるか」という問題である．この問題はごく最近に提起され，これまでは16 路盤までの連数の最大値しか求められていなかった．本論文では，連数最大化問題を整数計画問題として定式化し，問題の特徴を利用した制約条件を追加することにより，19 路盤における連数の最大値とその盤面を求めた結果を報告する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In computer Go, a string is defined as a maximal set of connected stones of an identical color. This paper concerns the maximum string problem described as follows: to find a position that maximizes the number of live strings on the n × n Go board. Previous researches proposed a 0-1 integer programming formulation of the maximum string problem, and solved the instances up to n = 16. We reformulate the problem by adding inequalities that break symmetry of the formulation and improve the objective value of linear relaxation. This refinement produces optimal positions up to n = 19, the regular size of Go board.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 48, 号 11, p. 3463-3469, 発行日 2007-11-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764