著者

横田 雅也 築地 立家 北川 智博 諸橋 玄武 岩田 茂樹

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.100, no.402, pp.41-48, 2000-10-20

---

縦横nマスに将棋の盤面を拡張し, その盤面上で詰将棋が与えられる.この詰将棋が詰むかどうかを決定する問題を, 一般化詰将棋問題と呼ぶ.本稿では一般化詰将棋問題が指数時間完全であることを証明する.一般化詰将棋問題の指数時間困難さの証明はG_3を利用する.G_3はすでに指数時間完全であることが知られている問題である(Provably difficult combinatorial games, SIAM J.Comput.8, 1979)

著者

横田 雅也 築地 立家 北川 智博 諸橋 玄武 岩田 茂樹

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-情報処理 (ISSN:09151915)

巻号頁・発行日

vol.84, no.3, pp.239-246, 2001-03-01

被引用文献数

4

---

縦横nマスの盤面上に与えられた詰将棋で, 攻方が勝てるかどうかを決定する問題を, 一般化詰将棋問題と呼ぶ.本論文では一般化詰将棋問題が指数時間完全であることを証明した.指数時間困難さの証明は, 既に指数時間完全であることが知られている問題G_3(Provably difficult combinatorial games, SIAM J.Comput., vol.8, 1979)から対数領域還元可能であることを示した.

著者

方波見 尚之 築地 立家

出版者

一般社団法人情報処理学会

雑誌

研究報告アルゴリズム(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.

著者

若月 祐介 築地 立家

出版者

一般社団法人情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2009, no.9, pp.43-50, 2009-01-23

---

DNA コンピュータを用いれば,ナノスケールの計算素子として DNA 分子を利用することにより,超並列計算を実現することができる.実際, Adleman らは, DNA コンピュータが DES 暗号を効率的に解読できることを示した.そこで,本論文では, AES 暗号を効率的に解読するような,複数の DNA アルゴリズムを示す.ところで, AES は DES よりもはるかに解読が難しい暗号として知られている.実際, Adleman らの DES 解読アルゴリズムを単純に拡張した AES 解読アルゴリズムでは, DNA メモリコンプレックスの長さが 7 倍以上になってしまう.我々のアルゴリズムを用いれば, DNA を切り離すための制限酵素を使用することにより,高々 1.3 倍の長さのメモリコンプレックスで AES コードが解読できることが示される.DNA computer utilizes DNA molecules as nanoscale computational elements to provide efficient computations for currently intractable problems. Actually, Boneh, Dunworth, Lipton showed that a DNA computer can efficiently decrypt DES encryption codes. In this paper, we show a couple of algorithms decrypting given AES codes by a series of parallel DNA operations. Since AES is known as much harder than DES to be decrypted, e.g. AES uses 128 bits, while DES uses 64 bits, of the hidden key, a simple extension of their algorithm requires DNA memory complexes of 7 times longer than the previous ones. One of our results shows that, by inserting restriction enzyme DNA cutting operations, much shorter memory complex is enough to decrypt given AES codes.

著者

真﨑 拓也 築地 立家

雑誌

第78回全国大会講演論文集

巻号頁・発行日

vol.2016, no.1, pp.737-738, 2016-03-10

---

画像認識を利用したカードゲームシステムとして、絵柄認識によるタロット占い、対人式コミュニケーションにも対応した神経衰弱、インターネット通信によるジャンケンなどが開発されてきた。本研究では、これらの要素を併せ持つ遊戯王カードゲームシステムを、市販のWEBカメラを入力とするPC環境で開発し、高速性と誤認識率を計測した。さらに、リアルカードでのインターネットを介したカードゲーム対戦を実施して、ユーザー評価実験を行った。結果として、リアルカードの絵柄認識によるオンラインカードゲーム対戦を低コストで実現するための、カード枚数の上限、ゲームルールの複雑さ、カードの操作性に関する知見を得た。

著者

横田 雅也 築地 立家 藤井 愼二 伊藤 大雄

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

電子情報通信学会論文誌 D (ISSN:09151915)

巻号頁・発行日

vol.J84-D1, no.1, pp.58-61, 2001-01-01

---

縦横 N ますに王将を除く各駒が O(N) 枚ずつ配置されている盤面が与えられたとき,詰み手順があるかどうかを判定する問題を一般化詰め将棋問題と呼ぶ.伊藤らはその計算複雑さがNP困難であることを証明した.本論文では盤面とともに手数の上限を単進数で与えたときの一般化詰め将棋問題がPSPACE完全であることを証明する.

著者

松原 洋 小澤 正直 吉信 康夫 築地 立家 佐藤 潤也 井原 俊輔 三井 斌友

出版者

名古屋大学

雑誌

基盤研究(C)

巻号頁・発行日

1999

---

計算可能性と多項式時間計算可能性の分野は、集合論、帰納的関数論、計算量理論、学習理論、確率モデル論、量子計算量理論等と密接に関係しており、本研究の研究実績も多岐にわたる.以下はそれぞれの分野における成果のいくつかを報告する.詰め将棋の計算量:8×8の桝目をn×nに拡張し、コマの個数をo(n)にして詰め将棋を作成したとき、一般化詰め将棋問題はEXPTIME完全であることを示した.これにより、一般化将棋もEXPTIME完全であることになる.確率モデル:一様ランダムに生成される回路の出力端子の個数の分布を決定した.学習1:負例のみからなるサンプルと無矛盾なo(logn)長の単調単項式を提出する問題の計算複雑さは、AND-OR-AND型の3段並列回路でo((logn)^2)個の入力変数をもつものの充足回発見問題と対数領域還元について同等であることをしめした.学習2:包除の原理を応用してDNF式を2^<o(√n)>時間で学習するアルゴリズムをえた.さらに、これ以上高速には学習できないことを頑健学習モデルの上で証明した.学習3:o(logn)個の変数に依存する一般の関数について、その関係変数を高速に発見する3種類のアルゴリズムを提案した.吉信はApproachability Propertyという無限組合せ論の命題と、ある条件を満たしたゲームの必勝法の存在のextendabilityという性質が同値だということを証明した.松原はS.Shelahとの共同研究でλがstrong limit singular cardinalであれば、NS_<kλ>はprecipitousにはなれないことを証明した.さらにこの結果を使って、Menasの予想がλがstrong limit singular cardinalの場合に成立することを証明した.

著者

横田 雅也 築地 立家 藤井 愼二 伊藤 大雄

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-情報処理 (ISSN:09151915)

巻号頁・発行日

vol.84, no.1, pp.58-61, 2001-01-01

被引用文献数

1

---

縦横Nますに王将を除く各駒がO(N)枚ずつ配置されている盤面が与えられたとき, 詰み手順があるかどうかを判定する問題を一般化つめ将棋問題と呼ぶ.伊藤らはその計算複雑さがNP困難であることを証明した.本論文では盤面とともに手数の上限を単進数で与えたときの一般化詰め将棋問題がPSPACE完全であることを証明する.