論文

査読有り
2017年

Sankaku-Tori: An old Western-Japanese game played on a point set

Journal of Information Processing
  • Takashi Horiyama
  • ,
  • Masashi Kiyomi
  • ,
  • Yoshio Okamoto
  • ,
  • Ryuhei Uehara
  • ,
  • Takeaki Uno
  • ,
  • Yushi Uno
  • ,
  • Yukiko Yamauchi

25
8
開始ページ
708
終了ページ
715
記述言語
英語
掲載種別
研究論文(学術雑誌)

We study a combinatorial game named "sankaku-tori" in Japanese, which means "triangle-taking" in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In each turn, a player adds a line segment to join two points, and the game ends when a triangulation of the point set is completed. The player who completes more triangles than the other wins. In this paper, we formalize this game and investigate three restricted variants of this game. We first investigate a solitaire variant; for a given set of points and line segments with two integers t and k, the problem asks if you can obtain t triangles after k moves. We show that this variant is NP-complete in general. The second variant is the standard two player version, but the points are in convex position. In this case, the first player has a nontrivial winning strategy. The last variant is a natural extension of the second one; we have the points in convex position but one point inside. Then, it turns out that the first player has no winning strategy.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.708------------------------------We study a combinatorial game named "sankaku-tori" in Japanese, which means "triangle-taking" in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In each turn, a player adds a line segment to join two points, and the game ends when a triangulation of the point set is completed. The player who completes more triangles than the other wins. In this paper, we formalize this game and investigate three restricted variants of this game. We first investigate a solitaire variant; for a given set of points and line segments with two integers t and k, the problem asks if you can obtain t triangles after k moves. We show that this variant is NP-complete in general. The second variant is the standard two player version, but the points are in convex position. In this case, the first player has a nontrivial winning strategy. The last variant is a natural extension of the second one; we have the points in convex position but one point inside. Then, it turns out that the first player has no winning strategy.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.708------------------------------

リンク情報
CiNii Articles
http://ci.nii.ac.jp/naid/170000148848
CiNii Books
http://ci.nii.ac.jp/ncid/AN00116647
URL
http://id.nii.ac.jp/1001/00182922/
ID情報
  • ISSN : 1882-7764
  • CiNii Articles ID : 170000148848
  • CiNii Books ID : AN00116647

エクスポート
BibTeX RIS