抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
本稿では,新しい二人ゲームであるハッピーセットゲームを提案する.本ゲームは,W(白プレイヤー)とB(黒プレイヤー)の二人のプレイヤーによる以下のようなボード上での戦略ゲームである:まず,白または黒に頂点彩色されたグラフG=(V,E)について,もし頂点vとそのすべての隣接頂点が同じ色で彩色されていた場合,vをハッピー頂点と呼び,そうでない場合はアンハッピー頂点と呼ぶ.プレイヤーWとBは,交互に手番が回ってきて,それぞれの手番において未彩色の頂点を選び,それぞれ白と黒に頂点を彩色する.ゲームにおけるW(B)の目標は,相手のB(W)よりもより多くのハッピーとなる白頂点(黒頂点)を得ることができるように彩色することである.一部の頂点が彩色されたグラフG=(V,E)(もしくは特別の場合としてすべての頂点が未彩色であるグラフ)が与えられたとき,G上でのハッピーセットゲームをHV G(G;t)と表す.ここで,tは各手番で彩色できる頂点数を表す.ゲームHV G(G;t)は常にWが先手であり,すべての頂点が彩色されたところで終了する.本稿では,まず,一部の頂点が彩色されたグラフGが与えられたとき,それぞれが各手番で一つの頂点を彩色する場合,Wに必勝戦略が存在するか否かを判定する問題について,Gが平面二部グラフであったとしても,NP困難であることを示す.次に,すべての頂点が未彩色のパス/サイクル/2次元グリッドにおけるハッピーセットゲームについて,必勝戦略/引分戦略について考える.最後に,1度の手番しかない1ラウンド型ハッピーセットゲームHV G(G;|V(G)|/2)を考える.まず,Wが[|V(G)|/2]個の頂点を白に彩色し,次に,Bが残りの[|V(G)|/2]個の頂点を黒に彩色するゲームである.パス,サイクル,グリッドにおけるHV G(G;|V(G)|/2)の白と黒のハッピー頂点の最大差について考える.(著者抄録)
