共同研究・競争的資金等の研究課題

2018年4月 - 2022年3月

グラフ上のゲームおよびオンライン性を持つゲームの必勝性

日本学術振興会  科学研究費助成事業 基盤研究(C)  基盤研究(C)

課題番号
18K11601
体系的課題番号
JP18K11601
担当区分
研究代表者
配分額
(総額)
3,120,000円
(直接経費)
2,400,000円
(間接経費)
720,000円

オンライン性を持つゲームの必勝性に関しては、主に落ちものゲームの一種であるぷよぷよを1人ゲームとして扱い、盤面の幅と色数を変更した場合に関する従来研究を、入力ピースの先読みが可能な場合に拡張した。主な結果として、どれだけ先読みが多くても色数が多ければプレイヤーの必敗となることを、盤面の幅が2および3の場合に対して証明した。
グラフ上のゲームについては、グラフ上のペグソリティアやチャイニーズチェッカー(ダイヤモンドゲーム)等のペグ移動ゲームを扱い、これらに関する可解性の判定や必勝性判定などの問題の計算困難性を証明した。また、これらのゲームのルールの変種における必勝性についても扱った。

リンク情報
KAKEN
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18K11601
ID情報
  • 課題番号 : 18K11601
  • 体系的課題番号 : JP18K11601