テトリスにおけるAI の開発 情報論理工学研究室 13—1--037--0113 川原 翔太
目次 研究の背景と目的 研究内容 結果と考察 今後の課題 参考文献
研究の背景 テトリスは1985年に開発されたコンピュータゲーム 完全な解を得るのは難しい 得点最大化問題はNP困難*1 初心者と上級者のミノの積み方の違い *1:Demaineら Tetris is Hard(2002)
研究の目的 短時間でミノを置く場所を見つける手助け 初心者にテトリスの置き方を理解してもらう
研究内容 ミノの配置可能場所を以下の 3 段階に分けて表示す る 1. 1段以上消せる場所 2. 隙間無く置ける場所 ■ ■■■ □ □ ■ ■■■ □ □ □□□ □□■ ■□□ □ ■□■ ■□■ ■□■ ■□□□■ ■■■ ■■■ ■■■ ■■■■■ 1. 1段以上消せる場所 2. 隙間無く置ける場所 3. 置かない方が良いと思える場所
候補場所の探し方 □□□□□□□□ ミノが積まれるたびに盤面を 把握するために積まれたミノ □□□□□○□○ ○□□○○■□■ ■○○■■■□■ ■■■■■■○■ ■■■■■■■■ ミノが積まれるたびに盤面を 把握するために積まれたミノ の上のy座標(pile)を求める □・・空白 ■・・固定ミノ ○・・pileの値となる 場所
○の部分を中心に5×5の場面を探索しミノの有無を確認している。 生成されたミノの形に合わせて隙間が出来るか判定し、隙間が出来ないと判断したら候補として表示する。 1段以上消せると判断したら、色を変えて表示する。 □□□□□ □□○□○ ○○■□■ ■■■□■
プレイ映像
実行結果
考察 隙間無く置かれてるが隣接面以外で隙間が生まれ てしまう 序盤だと隙間無く埋まる場所が多く候補同士が重な り見にくくなる場面がある 後半になるにつれて考える時間が短くなると候補が プレイを助けてくれる場面が増えた。
今後の課題 横スライドの対応 候補先の厳選 自動プログラムの作成 多段消しを目指す戦略の実施
参考文献 村山要司:楽しく学べるJavaゲーム・アプレット、工学 社(2002) 長久勝:Javaゲームプログラミング、SBクリエイティ ブ(2007) 中山亮士, 平原誠, 遺伝的アルゴリズムを用いたテト リスの解法, 電子情報通信学会2015年総合大会,、 情報・システムソサイエティ特別企画 学生ポスター セッション予稿集, p.51, 電子情報通信学会, (2015)https://www.ieice.org/iss/jpn/Publications/iss poster_2015/data/pdf/ISS-P-51.pdf
宮崎真奈実, 荒川正幹, ニューラルネットワークと遺 伝的アルゴリズムを用いたテトリスコントローラの開 発, 第74回全国大会講演論文集, Vol.2012, No.1, pp.539-540, 情報処理学会, (2012), http://id.nii.ac.jp/1001/00109944/ Erik D. Demaine, Susan Hohenberger, David Liben-Nowell, Tetris is Hard, Even to Approximate, Computer Science Vol.2002, No.20 pp, 1-56, Cornell Univesity Lbrary(2002), https://arxiv.org/abs/cs/0210020
田伏未来, 萩原将文, ファジィ推論ニューラルネット ワークを用いたテトリスのスキル獲得のための自動 学習, 日本ファジィ学会誌 Vol 田伏未来, 萩原将文, ファジィ推論ニューラルネット ワークを用いたテトリスのスキル獲得のための自動 学習, 日本ファジィ学会誌 Vol.11, No,6, pp.1089- 1097, 日本ファジィ学会, (1999), http://ci.nii.ac.jp/naid/110002946575 Heidi Burgiel, How to lose at Tetris, The Mathematical Gazette, Vol.81, No.491, pp.194- 200(1997),http://www.geom.uiuc.edu/java/tetris/tet ris.ps
遠城秀和, 実時間知識処理をめざした制約推論のレ スポンスタイム推定法, 全国大会講演論文集, 第44 回(人工知能及び認知科学), pp