著者
方波見 尚之 築地 立家
出版者
一般社団法人情報処理学会
雑誌
研究報告アルゴリズム(AL) (ISSN:09196072)
巻号頁・発行日
vol.2009, no.9, pp.51-58, 2009-01-23

はさみ将棋とは、自分の駒を用いて相手の駒をはさんでとる 2 人対戦型ゼロサムゲームであり、日本のはさみ将棋、タイの Mak-yak などが有名である。本稿では、盤面を n×n に拡張した一般化はさみ将棋の計算複雑さについて考察する。ここでは、縦、横方向に自由に動く駒に加えて、不動駒も使用するものとする。また、縦横方向に加えて斜め方向の取りも許すものとし、相手の駒を先に 5 個取った方が勝ちとする。このとき、任意に与えられた一般化はさみ将棋の盤面について、勝ち・負け・引き分けのいずれであるかを判定する問題が、 EXPTIME 完全問題であることを証明する。Hasami-Shogi is a two-person zero-sum board game where each player aims to take a number of the opponent's pieces at once by making a sandwich position; a sandwich position occurs when the player's two pieces sandwich a number of the opponent's pieces placed consecutively on a row, a column, or a diagonal squares. In this paper, we generalize it to the n×n board, on which each piece moves like the rook. In addition, we allow a number of the immobile piece to exist. The winner is the player who takes at least 5 opponent's pieces at first. Then, we prove that the problem of determining whether a given position of the generalized Hasami-Shogi is either a player's winning position, or an opponent's winning position, or a draw position, is EXPTIME Complete.

言及状況

はてなブックマーク (1 users, 1 posts)

[ゲーム][将棋][数学]

Twitter (4 users, 4 posts, 1 favorites)

こんな論文どうですか? 一般化はさみ将棋のEXPTIME完全性(方波見尚之ほか),2009 http://id.CiNii.jp/d3QgL はさみ将棋とは、…
>一般化はさみ将棋のEXPTIME完全性 http://ci.nii.ac.jp/naid/110007123956

収集済み URL リスト