論文誌(ジャーナル)
論文誌(ジャーナル)
 |
|
| ■文献番号： | IPSJ-JNL4811006 |
■文 献 名 ： |
囲碁における連数の最大値について
On the Maximum Number of Strings in Go |
| ■著 者： |
宮代隆平 (東京農工大学)
Ryuhei Miyashiro(Tokyo University of Agriculture and Technology) |
| ■言 語 ： | 日本語 |
| ■発行年月日： | 2007年 11月 15日 |
| ■ページ数： | 7ページ 本誌掲載頁：3463-3469ページ |
| ■サ イ ズ ： | A4 |
■価 格： |
購読者：\0
会員：\315
非会員 \630
※ PDF(ダウンロード)の価格です。 ペーパー(論文単位)の価格はこちら |
| ■抄 録： | 囲碁の盤上において，縦または横に連結している同じ色の石の極大集合を連と呼ぶ．連数最大化問題とは，「囲碁のルールの下でn 路盤上に最大でいくつの連が存在できるか」という問題である．この問題はごく最近に提起され，これまでは16 路盤までの連数の最大値しか求められていなかった．本論文では，連数最大化問題を整数計画問題として定式化し，問題の特徴を利用した制約条件を追加することにより，19 路盤における連数の最大値とその盤面を求めた結果を報告する．
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. |
| ■カテゴリ： |
論文誌(ジャーナル)
特集：ゲームプログラミング 解析 |
