| Item type |
SIG Technical Reports(1) |
| 公開日 |
2024-05-01 |
| タイトル |
|
|
タイトル |
ハッピーセットゲームにおける戦略 |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
九州工業大学 |
| 著者所属 |
|
|
|
九州工業大学 |
| 著者所属 |
|
|
|
大阪公立大学 |
| 著者所属 |
|
|
|
九州工業大学 |
| 著者所属 |
|
|
|
九州工業大学 |
| 著者所属 |
|
|
|
九州工業大学 |
| 著者所属 |
|
|
|
九州工業大学 |
| 著者名 |
江藤, 宏
藤本, 晶子
木谷, 裕紀
松下, 瑠花
宮野, 英次
村尾, 優斗
斎藤, 寿樹
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
本稿では，新しい二人ゲームであるハッピーセットゲームを提案する．本ゲームは，W（白プレイヤー）とB（黒プレイヤー）の二人のプレイヤーによる以下のようなボード上での戦略ゲームである：まず，白または黒に頂点彩色されたグラフ G=(V,E) について，もし頂点 v とそのすべての隣接頂点が同じ色で彩色されていた場合，v をハッピー頂点と呼び，そうでない場合はアンハッピー頂点と呼ぶ．プレイヤー W と B は，交互に手番が回ってきて，それぞれの手番において未彩色の頂点を選び，それぞれ白と黒に頂点を彩色する．ゲームにおける W（B）の目標は，相手の B（W）よりもより多くのハッピーとなる白頂点（黒頂点）を得ることができるように彩色することである．一部の頂点が彩色されたグラフ G=(V,E)（もしくは特別の場合としてすべての頂点が未彩色であるグラフ）が与えられたとき，G 上でのハッピーセットゲームを HVG(G;t) と表す．ここで，t は各手番で彩色できる頂点数を表す．ゲーム HVG(G;t )は常にWが先手であり，すべての頂点が彩色されたところで終了する．本稿では，まず，一部の頂点が彩色されたグラフ G が与えられたとき，それぞれが各手番で一つの頂点を彩色する場合，W に必勝戦略が存在するか否かを判定する問題について，G が平面二部グラフであったとしても，NP 困難であることを示す．次に，すべての頂点が未彩色のパス/サイクル/2 次元グリッドにおけるハッピーセットゲームについて，必勝戦略/引分戦略について考える．最後に，1 度の手番しかない 1 ラウンド型ハッピーセットゲーム HVG(G; |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2024-AL-198,
号 15,
p. 1-6,
発行日 2024-05-01
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL24198015.pdf (967.7 kB)
