{"updated":"2025-01-20T18:13:53.729456+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00145800","sets":["6164:6165:6210:8358"]},"path":["8358"],"owner":"11","recid":"145800","title":["QBFソルバを用いた一般化三並べの拡張の勝敗判定"],"pubdate":{"attribute_name":"公開日","attribute_value":"2015-10-30"},"_buckets":{"deposit":"38c795b7-2bd7-4c33-937f-46697f43a00c"},"_deposit":{"id":"145800","pid":{"type":"depid","value":"145800","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"QBFソルバを用いた一般化三並べの拡張の勝敗判定","author_link":["225616","225618","225611","225612","225613","225615","225610","225617","225614","225609"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"QBFソルバを用いた一般化三並べの拡張の勝敗判定"},{"subitem_title":"Solving Generalized Tic-Tac-Toe by Using QBF Solver","subitem_title_language":"en"}]},"item_type_id":"18","publish_date":"2015-10-30","item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_18_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"東北大学大学院情報科学研究科"},{"subitem_text_value":"東北大学大学院情報科学研究科"},{"subitem_text_value":"東北大学大学院情報科学研究科"},{"subitem_text_value":"東北大学大学院情報科学研究科"},{"subitem_text_value":"北海道大学大学院情報科学研究科"}]},"item_18_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Graduate School of Information Sciences, Tohoku University","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Information Sciences, Tohoku University","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Information Sciences, Tohoku University","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Information Sciences, Tohoku University","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Information Science and Technology, Hokkaido University","subitem_text_language":"en"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/145800/files/IPSJ-GPWS2015025.pdf","label":"IPSJ-GPWS2015025.pdf"},"date":[{"dateType":"Available","dateValue":"2015-10-30"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-GPWS2015025.pdf","filesize":[{"value":"888.5 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"5"},{"tax":["include_tax"],"price":"0","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"18"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"b873baad-7712-487e-9c82-539437f5a714","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2015 by the Information Processing Society of Japan"}]},"item_18_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"ディプタラマ, 　"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"石黒, 裕也"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"成澤, 和志"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"篠原, 歩"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"ジョーダン, チャールズ"}],"nameIdentifiers":[{}]}]},"item_18_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Dipta, rama","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Yuya, Ishiguro","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Kazuyuki, Narisawa","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Ayumi, Shinohara","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Charles, Jordan","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_5794","resourcetype":"conference paper"}]},"item_18_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"一般化三並べはFrank Hararyによって提案された2人完全情報ゲームであり，碁盤面上に先手後手が交互に石を1つずつ置き，あらかじめ定められた動物を先に作ったプレイヤが勝ちというゲームである．2人完全情報ゲームの勝敗判定問題は与えられたゲームに対して，先手必勝，後手必勝または引き分けとなるかを判定する問題である．オセロや五目並べなど，多くの2 人完全情報ゲームの勝敗判定問題はPSPACE完全であることが知られている．それに対して，代表的なPSPACE 完全問題としてQuantified Boolean Formula (QBF) に対する充足可能性問題(TQBF)が存在し，TQBFを高速に解くプログラム，QBFソルバが開発されてきた．本研究では一般化三並べの拡張であるGTTT(p,q)およびTorusGTTT(m,n)の勝敗判定問題をTQBFに帰着し，QBFソルバを用いてゲーム勝敗判定問題を解く．ゲームのパラメータによっては既存のゲームの探索手法より，QBFソルバの方がより速く勝敗判定問題を解けることが見られた．","subitem_description_type":"Other"}]},"item_18_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Generalized tic-tac-toe is an achievement game for polyominoes introduced by Frank Harary. Two players alternately put one stone over a board, and the player who first achieves a given polyomino wins the game. The game solving problem for 2 players game with perfect information is to determine whether the first player wins the game, the second player wins the game, or the game draws if both players play optimally. Many game solving problems for two players with perfect information games, such as Gomoku and Othello are PSPACE complete. On the other hand, boolean satisfiability problem for quantified boolean formula (QBF) is a representative of PSPACE complete problems, and efficient QBF solvers have been developed. In this paper we solve the game solving problems for two extensions of generalized tic-tac-toe, GTTT(p,q) and TorusGTTT(m,n) by reducing them to TQBF, and then use QBF solvers. From the results, in some cases, QBF solvers can solve the games faster than game tree search algorithm.","subitem_description_type":"Other"}]},"item_18_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"161","bibliographic_titles":[{"bibliographic_title":"ゲームプログラミングワークショップ2015論文集"}],"bibliographicPageStart":"154","bibliographicIssueDates":{"bibliographicIssueDate":"2015-10-30","bibliographicIssueDateType":"Issued"},"bibliographicVolumeNumber":"2015"}]},"relation_version_is_last":true,"weko_creator_id":"11"},"created":"2025-01-19T00:21:23.201190+00:00","id":145800,"links":{}}