#procon29 競技部門参加記
※この記事は ICT Advent Calendar 2018 3日目の記事です.
昨日はPCKモバイル部門でグランプリを獲得したびーまかです.
結果
結果のソース
予選
P10リーグ
対戦相手 | 結果 | 勝敗 |
---|---|---|
木更津 | 98-84 | 敗 |
沼津 | 144-131 | 敗 |
舞鶴 | 89-56 | 敗 |
予選敗退 0勝3敗 リーグ4位
敗者復活戦
L7リーグ(リーグ内リーグ戦)
対戦相手 | 結果 | 勝敗 |
---|---|---|
呉 | 73-98 | 勝 |
石川 | 69-83 | 勝 |
リーグ内リーグ戦のため,2勝チーム同士で比較して総得点数が多いチームが通過
比較相手 | 結果 | 勝敗 |
---|---|---|
高知 | 102-181 | 勝 |
敗者復活 2勝0敗 リーグ1位
決勝トーナメント
対戦相手 | 結果 | 勝敗 |
---|---|---|
北九州 | 128-124 | 敗 |
1回戦敗退
チームメンバー
SolverのAlgorithm
この問題は,「二人零和有限確定不完全情報ゲーム」として分類できる(?) 不完全情報ゲームのAIを考えるのがめんどくさくなったので完全情報ゲームみたいな問題に置き換える.
不完全情報である理由
まず,完全情報ゲームは,「すべての意思決定ノードにおいて,今まで取られた行動などが得られる」ものである. この問題では,双方のチームの意思決定が同時であるため,上記を満たさないと考えられる.
この問題を,先手・後手に分かれ交互に手を打つ「完全情報ゲーム」とみなせば.囲碁等のAIで知られる モンテカルロ木探索(MCTS) が適用出来ると考えた. ちなみに,囲碁AIで世間を賑わしたAlphaGoはこのモンテカルロ木探索と機械学習を組み合わせているらしいが,囲碁のように各マスに同じ点数が割り振られているわけではないので,本問題に対しては機械学習は有効ではないと考えた.
モンテカルロ木探索において,次にプレイアウトするノードを決めるUCB1値という有名な計算式があるが,それだけでは弱いので,現在のマス8近傍を見て,マイナスのマスに行こうとする場合や相手マス削除の場合,重みをつけるようにした.
前日(10月26日)
実はGUIが完成していない状態だったので,飛行機やバスの移動中や旅館についてからもずっとGUI開発班の手伝いをしていた. 動くものが出来たのはAM2:00くらいだったと思う.ここで初めて指示出しの練習を始める.
一通りの確認をしたあと,エージェント役の二人には寝てもらった.当日,冷静な判断が出来なくなったら困るからだ.
司令塔である僕と,出場はしないMadofukiくんと一緒にパンフレットを眺めて対戦相手の分析をしたり,ソルバと人力で対戦してパラメータ調整を行ったりした.
AM4:30くらいに就寝.
1日目(10月27日)
AM6:00くらいに起床.全く眠気が取れていない状態で試合に臨むことになってしまった.
予行練習が始まる前に,GUIの重要な部分を実装するのを忘れていたことに気づく.自分たちが右側か左側によって見た目が変わるので反転が必要になることを忘れていた. 今後の試合で必要になってくるので実装を始めた.予行演習では反転する必要がなかったのでそこは問題ではなかった.が,GUIが落ちて何も出来なかった. 原因としては,Solverからの候補が送られて来ていない状態でGUIに候補を表示するボタンを押してしまうと死ぬことはわかった.バグを直す時間がなかったので,それを避けるように人間が頑張ることにした.
予行演習が終わったあと反転機能の実装を完了させることが出来た.
1試合目,1ターンごとにSolverが使える時間を長くしすぎたため,間に合わなくなる.人力に切り替えたものの負ける.
2試合目,1ターン目は他のターンよりも長い時間が使えるので,その分Solverも使える時間を増やした.と思っていたら,1ターン目が短くて,他のターンのほうを長くするようにしてしまい指示が間に合わなくなる.人力に切り替えたものの負ける.
3試合目,1ターンに書ける時間は問題なかった.が,盤面の入力ミスがかなり多くなってしまい,正しくSolverが探索が出来ない.GUI上では勝っていたが,当然実際の盤面と違うので負ける. どうも,冷静な判断が出来なくなってしまったのは司令塔である僕らしい.完全に寝不足だ.
旅館に戻ったあと,死ぬほど体調が悪いことに気づき,指導教員から薬をもらった. 奇しくも,この日は僕の19歳の誕生日だった.たぶん,今まで生きてきた中で一番最悪の誕生日だったように感じる.体調最悪だし,予選全敗だし.
予選の結果から,入力ミスが出ないようにGUIの改良が必須であるという意見が話し合いで出たため,3人に開発を丸投げして僕だけPM10:00くらいに寝た.
2日目,僕が冷静な判断を出来るようにするために.
2日目(10月28日)
AM6:00くらいに起床.ぼくはなんとか体調が回復していたので安心した.周りを見渡すと,敷布団も掛け布団も無しに寝ている3人が目に飛び込んできた. 正直,涙出そうになった.いつまで起きて開発していたか分からないが,彼らは相当頑張ってくれたと思う.
GUIの動作を確認するとかなり良くなっていた.1つのボタンで2人のエージェントを移動出来たり,元に戻したりするように出来ていたし,GUIの落ちるバグも修正されていた.
敗者復活戦が始まった.
1試合目.予選では座って指示を出していたが,自分は立ったほうが落ち着くことを思い出したので,椅子を外してもらって立ってやることにした. 入力ミスは少しだけあったので不安だったが,なんとか勝つことが出来た.
2試合目,またも若干のミスがあったので不安だった.結果は負けだった.待機席に戻りながら「あぁ,今年のプロコンは決勝にも上がれず終わりか」と落ち込んでいた. しかし,北九州のWA_TLEくんが,
「この盤面,ルール違反してる!!」
的なことを割と大きめな声で言っていた.驚いたぼくは,スクリーンと配られたデータを確認する.
なるほど,初期位置の時点で平等じゃないやん. ということで,すぐさま運営に抗議した.この画像は抗議したときの僕の画像.
運営に対するヘイトが溜まっていくにつれ,他高専との絆が深まったのでそこに関しては運営に感謝したいと思う.
10分ほどしてから,運営から「再試合をします」との連絡があった.謎の拍手が起こる.何の拍手だよ.(以下のストリーミングの2:41:38ほどから)
兎にも角にも,再び決勝トーナメントに行くチャンスが与えられた.
2試合目(再試合),落ち着きを取り戻すことが出来たのか,なんと入力をノーミスでやることが出来た.試合が終わったあとに勝利を確信した.結果,勝っていた. 本当に良かった.「最後まで諦めるな」という言葉はこの現象にピッタリなのではないか.
敗者復活戦はリーグリーグという特殊なルールで,6,7チームのうち,勝率が高いチームが2つあった場合,総得点数で復活者を決めるという理不尽ルールが適用されている. なんとか突破できた.なるべく膠着した試合にならないように,人力で補正を掛けたのは良かったと思う.
決勝トーナメント,さっきルール違反に気づかせてくれたWA_TLEのいる北九州と当たった. あのIOI金メダリストと戦えると思うと怖さもあったが,ここで勝てば優勝すらいけるのではないかと内心ワクワクしていた.試合中はほとんどミスもなく,最後まで勝ち負けが分からない接戦だった.
結果,最後のターンで逆転されてしまい4点差で敗北を喫した.あとで彼らに聞くと,最後はWA_TLEくんが天才的な頭で指示を出したので勝てたらしい.流石だ.
反省
良かったこと
- タスクをちゃんと振れた
- 昨年は僕のワンマンチームで,ほとんどのプログラムを僕が書いてしまったのでストレスが半端なかった.この反省を生かして,ちゃんとチームメンバーにタスクを振って分散させることが出来た.
- ちゃんとプログラムで勝てた
- 最後まで人力でやるチームがある中で,諦めずにプログラムで戦えたのは良かったと思う.
悪かったこと
- 練習が前日にしか出来なかった
- 1日目のミスは明らかに練習してないことに起因する.開発を平行にやるよりも全員でGUIを先に完成させてしまったほうが良いような気がする.
- デスマをしたこと
- デスマをしない高専は負けると言われるが,体調を壊すと元も子もないのでやめましょう.
感想
運営に対する愚痴
ゲームの内容は良い.ただ謎の人力要素をやめてほしかった.人力要素にしてもあまりにも本質的じゃないヒューマンエラーを生んでしまうような競技はどうなんだろう.来年からは期待したい.
あと,ちゃんと問題をチェックしているのか.procon27でも再試合があったのでもう二度と繰り返してほしくない.この大会には高専生活を掛けて戦っている人もいる.そういう人たちのために真面目にやってほしい.
阿南高専生の補助学生に対する扱いがひどい.ただでさえボランティアなのにどうにかならないのか.
雑多な感想
我々沖縄高専競技部門のチームは「塗、無言、枡目にて。~私はずっとそうやって過ごしてきた~」というものだ. これは涼宮ハルヒの憂鬱の長門有希のキャラクターソングである雪、無音、窓辺にて。を改変したものだが,全然言及されなくて悲しくなった.結構いい名前だと思うんだが.
今回は決勝トーナメントまで出場できた.優勝を目標にしていたが,上出来の結果だと思っている. 来年も参加したい気持ちは山々だが,僕は来年5年生で受験勉強や卒研があるので参加しない予定である.後輩にはぜひ優勝を目標に頑張ってほしい.(助け舟くらいは聞いてくれれば全然だすけども)
また,最後までついてきてくれたチームメンバーと,何かとお世話になった教授に感謝の意を表したいと思う.本当にありがとうございました.
最後に,沖縄高専競技部門の努力の結晶であるgithubリポジトリを貼って締めようと思う.みなさんお疲れ様でした.
https://github.com/kurokoji/procon29-kyogigithub.com
明日はみずきち先輩の記事
http://shimamiz-m.hatenadiary.jp/entry/2018/12/05/002027shimamiz-m.hatenadiary.jp