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

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

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

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

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

はじめに

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

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

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

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分ごろから行う予定です.こちらは「オープン研究室」ということで,研究室紹介が主体ですので各研究室がどんなことを研究しているのかを知るのに適しています.学部生や大学院進学を考えていらっしゃる方にはとても良い機会と思いますので是非ご活用ください.

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年生対象のセミナーで取り組んだものです.

Human Resource Machine

Human Resource Machine というパズルゲームの話です.

Human Resource Machine

足し算引き算,0との比較,gotoくらいの機能だけでお題のプログラムをしようというパズルですが,ちまちま遊べます.各種プラットフォーム(iOS, android,SWITCHも!)で出ています.

お題は全部で3題.それぞれ単にタスクを実現するコードを書くか,いかに短いコードを書くかのSizeチャレンジと,いかに実行ステップ数を少なくするかのSpeedチャレンジがあります.もちろん,できるだけ短いコードを書くのとステップ数を少なくするのとは必ずしも両立しません.

以下では実現できたコードサイズとステップ数を一覧にしておきます.*は目標が実現できたことを示しています.

“Human Resource Machine” の続きを読む

山中寿登さんのスケジューリング学会奨励賞の受賞

山中寿登さん(M2)のスケジューリング学会奨励賞の授賞式がスケジューリングシンポジウム2018で行われました.受賞は,昨年のスケジューリングシンポジウムでの発表「外平面グラフに対するKollerのL(2,1)-ラベリングアルゴリズムの計算時間解析とその改善」に対するものです.

この研究は,Kollerによって提案されていた外平面グラフに対するL(2,1)-ラベリングを行う多項式時間アルゴリズムの計算量解析を精緻化した上で,さらにいくつかの高速化アイデアを組み込むことにより,Kollerの解析による計算量O(n^1001)をO(n^16.5)程度にまで改善したというものです.

山中さん,おめでとうございます.

情報科学ワークショップに参加(+大久保さんの受賞)

昨年度に引き続き,一同で情報科学ワークショップに参加してきました.

今年は福岡県飯塚での開催,参加者も70名を超えるとのことで大変盛況でした.
小野研からは以下の発表をしてきました:

社会的距離に基づくグラフ最適分割の計算量(⼤久保 壮浩)
⼿札公開ババ抜きの最適戦略(⽊⾕ 裕紀)
カード組を⽤いた正論理関数の安全な計算について(迫⽥ 賢宜)
グラフ制限下のヘドニックゲームにおけるナッシュ安定性判定のPLS完全性(前井 康秀)
弦グラフ関連クラスにおける拡散競争ゲームのナッシュ均衡の存在性(福薗 菜央佳)
閾値付影響ゲームにおける最適反応計算の複雑度とグラフクラス(⼭中 凛奈)

ちなみに,OBの土中さんの発表もありました(有向辺⽀配集合問題の核と近似)

そして,ワークショップの最後で良い発表に与えられる「優秀プレゼンテーション賞」を大久保さんが受賞しました.おめでとうございます.