Blog

新年おめでとうございます

皆さま,今年もよろしくお願い申し上げます.

  • 10月に書くべきだったニュースですが,名大の未来社会創造機構の特任助教だった木谷先生が,九大の経済学研究院へ転出されました(助教).
  • こちらも10月に書くべきだったニュースですが,M2の吉渡叶さんが2021 年度日本オペレーションズ・リサーチ学会 関西支部 若手研究発表会 優秀発表賞を受賞しました(10/17付け).おめでとうございます.

というニュースのお知らせでした.

「ぷよぷよは計算困難」―パズル・ゲームと最適化アルゴリズム―

はじめに

最近,「一般化ぷよぷよのより強い計算困難性」なる研究を発表しました(東北大学の江藤宏先生,九州大学の木谷裕紀先生との共同研究.国内研究会であるゲームプログラミングワークショップで江藤先生による口頭発表.2021年12月30日現在,pdfはここから取れます).

これは有名なビデオゲーム「ぷよぷよ」を一人用のパズルと見立てたとき,かつそれを一般化した場合,どの程度難しいものであるのかを(最適化)アルゴリズム論的に分析したものです.今回「最適化技術の応用・実践」に関する記事を集めよう,ということになりましたので,ちょうどよい題材ということで,この研究をより一般向けに解説してみようと思います.一般向けですので証明自体には踏み込まず,既存の定理と得られた定理の意義をおよそわかっていただくことをこの記事の目標とします.ただし「ぷよぷよ」について関してはおよそルール等がわかっている方を対象としています.ぷよぷよ自体をご存じない方はWikipedia や,セガによるぷよぷよポータルサイトをご覧になった上でこの記事を読んでいただけると幸いです.

“「ぷよぷよは計算困難」―パズル・ゲームと最適化アルゴリズム―” の続きを読む

2021年度メンバー

新年度になりましたので,メンバーリストをアップデートしました.

http://www.tcs.mi.i.nagoya-u.ac.jp/members/

  • (小野研メンバーと言うわけではありませんが)2020年3月に熊本大学から大舘陽太先生が隣の講座の准教授で着任されて,一緒に活動しています.また2021年3月に中央大学から土中哲秀先生が(これも)隣の講座の助教で着任されて,一緒に活動しています.
  • D3の木谷裕紀さんが修了,博士号を取得されました.木谷さんは名古屋大学のTMIプロジェクト(ライフスタイル革命のための超学際移動イノベーション人材養成学位プログラム)の特任助教に採用されました.本務と含めて一緒に協力して活動しましょう,と言うことになっています.
  • M2の4名(川井一馬さん,木村輝海さん,関本健悟さん,廣瀬暁之さん)が修了しました.それぞれ企業に就職しました.
  • B4の岩田知旺さん,宇田冴輝さん,小笹稜太さんが卒業しました.岩田さん,宇田さんは修士課程に進学しました.小笹さんは企業に就職しました.
  • 他にM1に新しく,瀧塚公太郎さん,杜文博さんが加わりました.
  • 新B4で池山 愛梨さん, 岡田 優斗さん,杉山 康恭さん,関口 裕也さん,野呂 浩平さん,平本 響一さんが配属されました(小野研あるいは大舘研に配属).

ということで,以上の体制で今年度はやっていきます.どうぞよろしくお願いします.

イタリア・トリノ開催の学会に参加してきました

こんにちは。小野研究室修士2年の前井康秀です。今回は2019年10月に1週間ほどイタリア・トリノで開催された国際学会に行ってきた経験について紹介します。本文章の主な対象読者は「大学進学を考えている高校生」や「大学院進学を考えている学部生」ですので、そのあたりの方たちがこれを読んで「学会って面白そう!」と感じ、進路選択等の助けになるようであれば幸いです.

私が今回参加した国際学会はPRIMA2019という通称で呼ばれており、正式な名称は「The 22nd International Conference on Principles and Practice of Multi-Agent Systems」です。つまり、マルチエージェントシステムと呼ばれるような、様々な特徴を持った複数の意思決定主体が行動する社会や空間において、全体として課題を達成したり、シミュレーションしたりする研究を主に取り扱う研究者が集まる学会です。私が現在大学院で行っている研究は、簡単にいうとグループ分けを行う研究であり、前述のマルチエージェント関連の分野とも重なるところがあると思い、論文投稿を行いました。以下に研究概要を簡単に書いておきます.

“イタリア・トリノ開催の学会に参加してきました” の続きを読む

LINEスタンプ

研究室のメンバーがLINEスタンプを作成しました.
それなりの汎用性があると思いますので,よろしければぜひお使いください.

研究者ねこ – LINE stickers | LINE STORE

Download these stickers from the Sticker Shop on the More or Wallet tab in the LINE app.Some stickers may only be usable for a limited time or only available for certain devices or regions.

研究者ねこ 2 – LINE stickers | LINE STORE

Download these stickers from the Sticker Shop on the More or Wallet tab in the LINE app.Some stickers may only be usable for a limited time or only available for certain devices or regions.

(遅くなったけれど)新年度

新年度になって1か月半経ってしまいましたがメンバーリストを更新しました.
http://www.tcs.mi.i.nagoya-u.ac.jp/members/

およそ以下のように変わっています:

  • 昨年度M2の山中寿登さんが修了,企業へ就職.迫田賢宜さんが博士後期課程に進学.
  • B4の伊藤正貴さんが卒業,企業へ就職.川井一馬さん,関本健悟さんがM1に進学.
  • 新M1として, 木村輝海 さん,廣瀬暁之さん,研究生として 王向京さんが新たに研究室に.
  • 新B4として,伊藤雅士さん, 山本峻輝さんが新たに研究室に.

以上,このメンバーで今年度はやっていきます.どうぞよろしくお願い申し上げます.

数理ランチ&ミニオープン研究会

*この記事は小野研に関するものではなく,数理情報学専攻に関するものです.

「数理ランチ」というものを毎月,数理情報学専攻(=自然情報学科数理情報系)では行っています.

数理情報系/数理情報学専攻に興味のある方が,当系/専攻の教員や学生と気軽に話せる機会を提供するため, 弁当持参のランチ会を行っています.
学内外・年齢を問わずどなたでも参加できます.手ぶらで来てちょっと話だけしていくのもいいですし, ランチ持参で来て一緒に食事するのも歓迎です.


時間: 12時頃から1時間程度
場所: 名古屋大学 東山キャンパス 情報学研究科棟 3階314号室

http://www.math.mi.i.nagoya-u.ac.jp/


上のリンク先では旧日程は出ているのですが,まだ来年度の予定が出ていないので,こちらに書かせていただきます.あくまで予定ですのでご注意ください.

  • 2019/04/17
  • 2019/05/22
  • 2019/06/19
  • 2019/07/17
  • 2019/09/18
  • 2019/10/16
  • 2019/11/20
  • 2019/12/18
  • 2020/01/22
  • 2020/02/19
  • 2020/03/06

ということで,次回は4月17日です.ご興味がある方はぜひお越しください.

あとこれとは別件ですが,ミニオープン研究室を4月3日15時30分ごろから行う予定です.こちらは「オープン研究室」ということで,研究室紹介が主体ですので各研究室がどんなことを研究しているのかを知るのに適しています.学部生や大学院進学を考えていらっしゃる方にはとても良い機会と思いますので是非ご活用ください.

長手数詰将棋「桃花源・改」

詰将棋とは将棋が元となったパズルゲームであり, 将棋が今の形になったのと同時期に生まれたとされています.詰将棋のルールは将棋のルールに加え,いくつかの固有のルールがあります.その固有のルールのうち,代表的なものとしては攻め方の各手は王手でなければならない,などがあります.

長手数詰将棋とは詰将棋の一種で,名前の通り長手数からなるもので,詰将棋パラダイスなどの専門誌などで「作品」が発表されています.通常,詰将棋は 「原則解答手順は一通りに定まる (余詰めが存在しない) 」という性質を満たしていなければならないのですが,長手数 詰将棋はその長手数の実現のため, 慣例的にこの「余詰めが存在しない」性質に関しては目をつぶることとなっています.

実際, 2019年3月現在の最長手数詰将棋作品とされているものは「ミクロコスモス」(橋本孝治)の1525手ですが,これにも余詰めが存在することが知られています.つまり,ミクロコスモスは厳密には「詰将棋」の条件を満たしていません.さらに詳しく述べると,現在知られている長手数詰将棋は2019年1月末時点のランキング上位1位から16位までの全てに余詰めが存在することが知られています.つまりこれらも厳密な意味では「詰将棋」の条件をみたしていないこととなります.

そのような観点から見ると,余詰めのない厳密な意味での過去最長の詰将棋は「STARSHIP TROOPER」(2010 年.摩利支天,625 手詰め) でした.これは長手数第17位にランクされています.

そこで私(都)は,「余詰めのない長手数詰将棋」の手数を更新することを目標に卒業研究に取り組みました.様々なアプローチをとった結果,既存の「桃花源」(添川浩司,767手詰め,ランキング10位)という長手数詰将棋を改変することで本来の詰将棋のルールにのっとった,過去最長となる767手の詰将棋を作成することに成功しました.もちろんこの結果は 「桃花源」があってものものですし,私の作品ではなく添川浩司さんの作品というべきものと思いますが, 実質的には 「桃花源」 が厳密な意味での過去最の 余詰めのない長手数詰将棋となったということで,添川さんには喜んでいただけるのではと思っています.

“長手数詰将棋「桃花源・改」” の続きを読む

GAT2019のガイスターAI大会に出場し, 優勝しました

GAT(Game AI tournaments) とは,Game AI の強さを競う大会で,今年が第4回の大会になります(GAT2019のページ).ここでの「ゲーム」は,デジタルカーリングからターン制ゲーム,さらにミニ四駆までと幅広く 取り上げられています.取り上げられているゲームの一つが「ガイスター」です.ガイスターは,wikipedia の記事によると,1982年に ドイツ で発売されたボードゲームであり,その年の ドイツ年間ゲーム大賞にノミネートされており,その後も何度も再販が繰り返されている,根強い人気のゲームと言えるかと思います.ガイスター自体は, 6×6のマスからなる盤面状に 2種8個のコマをお互いに種類がわからないように配置し取り合う,不完全情報型のゲームです.

ガイスターAI大会はGPW(ゲームプログラミングワークショップ)2017から行われており,今回が4度目の大会となります.過去の大会ページはGPW2017, GAT2018, GPW2018にあります.今回の大会も委員長の橋本剛先生により公開されています(ガイスターAI大会
GAT2018

前置きが長くなりましたが,2019年3月10日に電気通信大学にて開催されたこのガイスターAI大会に,B3の伊藤雅士さんが中心となって作ったプログラムStrongStrongMasashi(
伊藤雅士,大久保壮浩,木谷裕紀,小野廣隆(名古屋大学) )で出場し,見事優勝を果たしました.このプログラム作成は情報文化学部の3年生対象のセミナーで取り組んだものです.