jj1gujのブログ

アイコン画像は音速の奇行子 様よりいただきました

第4回世界将棋AI電竜戦本戦参加記

この記事はOpenEsys Advent Calendar 6日目の記事です。

第4回世界将棋AI電竜戦本戦に参加してきました

自己紹介

こんにちは。JJ1GUJです。esys17&imis21で現在はあきはばらようちえんで園児をしています。 プロセカが好きで先日推しイベのガチャで爆死しました。

jiskey.dev

その後更に課金して限定全員引けたのは嬉しかったです(白目)

jiskey.dev

遥ちゃんかわええ

しれっとリンクを載せているのですが夏あたりからRaspberry Pi4を使用してMisskeyサーバーを建てて自宅でホスティングしています。 よかったらフォローしてくれると嬉しいです

jiskey.dev

jiskey.dev

電竜戦とは

電竜戦は2020年から始まった比較的新しい将棋AIの大会です。 カツ丼将棋(@katsudonshogi)さんがNPO法人を建てられて大会を運営しています。 よくある形式の対局だけでなく、指定局面から指し継いで競うTSECやハードウェア統一戦など様々なルールで大会を開いているのが大きな特徴です。 今大会では41チームが参加し、2日にかけて行われました。 持ち時間は先手5分1手ごとに2秒加算、後手10分1手ごとに2秒加算というルールで行われました。

ソフトの概要

今回もponkotsuというソフト名で出場しました。 Deep Learningを使用しており、学習モデルにDenseNetを使用しているのが大きな特徴です。 今大会に向けてブロック数を10ブロックから20ブロックに増やし、定跡を新たに掘り直しました。 モデル単体の性能で行くと世界11位を取ったモデルに対し約R+200と大きく強化されています。 また、マシンはGCPでNVIDIA L4を4台借りていました。

0回戦

クラウド勢は0回戦があります。 なにかというとGPUの確保です。 今回NVIDIA A100を4台借りたかったのですがみんなが生成AIの学習とかで使うので借りれませんでした。あ～あ。

この日を境に生成AIのアンチになりました。

ということで仕方なくNVIDIA L4を4台借りることにしました。 単体でRTX3090より少し性能が落ちるくらいだったのでまあ4台も借りれれば十分かなといったところでした。

今回対局数が多いので(2日合わせて28戦)ダイジェストで勝った対局と負けた対局を1局ずつ取り上げようかなと思います。

1日目

1日目は先後入れ替えて計14局を戦い、上位10チームがA級リーグに、11位~20位がB級リーグに、残りがC級リーグに振り分けられました。

4回戦表

4回戦はponkotsuの先手で5月に開催された世界コンピュータ将棋選手権でも当たったあすとら将棋が相手でした。 選手権のときにはponkotsuがマシントラブルにより敗北しており、こちらにとってはリベンジ戦でした。 角換わりのオープニングで序盤からponkotsuが評価値400点を出している一方で、あすとら将棋は評価値が100点前後でハラハラする展開でした。 今回のponkotsuはかなり自分に甘い評価値を出しており、評価値500点程度でもひっくり返されそうな印象でした。 68手目からあすとら将棋も評価値が500点となり、一安心かと思いきやなかなか詰まず、またドキドキしていました。 最終的には相入玉となり、そこからなんとか詰ますことができました。 個人的にリベンジ達成でき、嬉しい一局となりました。

棋譜はこちら。

denryu-sen.jp

7回戦表

最終7回戦はponkotsuの先手でKyoShogiとの対戦でした。 最終戦は自力でのB級リーグ入りがかかっており、ここまで先手で負けたソフトは後手でも負ける流れだったため、とても重要な一戦でした。 この対局も序盤でponkotsuが評価値300点と自分に甘い点数をだしており、不安に思っていたところその不安が的中し、KyoShogiにうまく指され、負けとなりました。

棋譜はこちら

denryu-sen.jp

KyoShogiには先後入れ替えた次戦でも負けとなり、B級リーグ入りは他力となりました。

結果は7勝7敗の22位となり、惜しくもB級リーグ入りを逃してしまいました。 一方で最終戦で当たったKyoShogiは最終戦で連勝した結果A級リーグ入りを果たし、完全に明暗が分かれる形となりました。

途中A級リーグ入りが見える7位までつけていたこともあり、かなり悔しかったです。

2日目

C級リーグであったこともあり、別にインスタンスを借りなくてもいいかと思っていたのですが、こうなったら優勝を目指そうと心を切り替え、結局借りることにしました。

4回戦表

4回戦はponkotsuの後手でAobaZeroとの対戦となりました。 AobaZeroとは2年前の世界コンピュータ将棋選手権依頼の直接対決で、ponkotsuにとってはリベンジがかかっていました。 また、ここまでAobaZeroとponkotsuは全勝できており、優勝を目指す上では落とせない一戦でした。 戦型不明の力戦？っぽい進行になり、80手目あたりまで互角の怖い展開だったのですがなんとか最後ponkotsuがリードを奪うことができなんとか勝つことができました。 リベンジ兼全勝を死守することができ嬉しかったです。

棋譜はこちら。

denryu-sen.jp

5回戦裏

5回戦は十六式いろは幻との対戦でした。 裏はponkotsuの後手番となりました。 十六式いろは幻には前日にも当たっており、そのときには表裏両方でponkotsuが勝っていました。 しかしながら前日からR200くらい強くなっているとの情報があり、かなり不安でした。

表でponkotsuが先手番を持ったときはなんとか勝つことができたのですが、この対戦では60手目を越えたあたりから徐々に十六式いろは幻にリードを奪われ、負けとなってしまいました。 それと同時に全勝も阻止され悔しい一局となりました。

どうも角換わりが苦手なようです

棋譜はこちら。

denryu-sen.jp

最終的に12.6勝1.4敗(後手番で1度引き分けたので0.6勝付与されている)となり、ギリギリではありましたがC級リーグを優勝することができました。

また、年明けから開催される第2回マイナビニュース杯電竜戦ハードウェア統一戦の出場権も獲得することができました。

感想とか

今回C級リーグで優勝することができ、非常に嬉しかったです。 個人的に任意の大会で優勝したことがなく、初めての経験でした。 また、ある程度ponkotsuが強いことがわかり安心しました。 一方で他ソフトのレベルが著しく上がっており、かなり厳しい大会でした。 ponkotsuも選手権と比べるとマシン性能込みでおそらくR200程度は強くなっているはずなのにC級リーグに振り分けられるという魔境でした。 半年程度でここまでレベルが上がるとかなりつらいものがあります。 正直来年の選手権の一次予選突破ラインがR4000になっていても震えどすれも驚かないと思います。

ponkotsuに関しては序盤でかなり楽観視しているだけでなく中終盤で頓死筋を読み切ることができず負けるようなケースもあり、課題が残る大会となりました。 おそらくですが今大会でオリジナルなDenseNetを採用するのは最後になります。 というのもDenseNetは層を深くしていくにつれてチャンネル数が増大するため、ブロック数を増やすことができないという課題があるためです。 そのため現在この問題を解消した改良版のモデルを作成しており、年明けのハードウェア統一戦では改良版のモデルを出す予定です。 今大会で使用したモデル・定跡・設定は後日やる気が出たときに公開する予定です。 しばらくお待ち下さい…

年明けも第2回マイナビニュース杯電竜戦ハードウェア統一戦に向け頑張っていきますので応援よろしくお願いします(みんな強すぎて勝てるビジョンが見えない…)

ponkotsuの評価関数及び定跡の公開(WCSC33 版)

コンピュータ プログラミング 機械学習

第33回世界コンピュータ将棋選手権(WCSC33)で使用した評価関数及び定跡を公開します。

特徴

  • 機械学習モデルにDenseNetを使用しています。
  • 軽量なモデルであるため、NPSが高く、手元の環境(RTX3090+Core-i7 8700)でNPSが6万～10万程度出ます。
  • より詳細を知りたい方はこちらのアピール文書を御覧ください。

評価関数ファイルのダウンロードについて

以下の3点を同封しています。 model.onnxが評価関数ファイル、book.binが定跡ファイルとなっています。 README.mdに利用規約を書いていますので使用前に必ずお読みいただき、ご確認ください。 また再配布は全面的に禁止します。

使用を開始した時点で利用規約に同意したものとみなします。

  • book.bin

  • model.onnx

  • README.md

以下のリンクからダウンロード可能です。

drive.google.com

WCSC33参加記

コンピュータ プログラミング 機械学習

第33回世界コンピュータ将棋選手権に参加してきました

ソフトの概要

今年もponkotsuというソフト名で出場しました. 今年はネットワーク構造にDenseNetという機械学習モデルを採用したらどこまで強くなるのか検証することをテーマにしていました. 手法や学習データについてはアピール文書に書いていますのでこちらをご覧ください. 大会で使用した評価関数と定跡はこちらからダウンロードできます(利用規約を必ずお守りください).

今年の成績

今年は一次予選を6勝2敗の3位という成績で二次予選に進出することができました. 二次予選では5勝4敗の11位という成績で、決勝進出とはならなかったものの来年の二次予選シードを獲得することができました. 順位表はこちらをご覧ください.

一次予選の様子とか

1日目は評価値をちゃんと送れていないのでponkotsuの評価値はないです.

1回戦(爆裂駒拾太郎戦)

初戦から早速初対戦の相手でした. 詰将棋の局面を教師に学習させたソフトで, もともと爆裂駒捨太郎という名前のソフトだったのですが, 一文字変わって爆裂駒拾太郎になっていて驚きました.

将棋は序盤早々にリードを取ることができ, 終始リードを保ったまま白星を上げることができました.

棋譜はこちらです.

live4.computer-shogi.org

2回戦(いちびん戦)

2回戦で早速強豪と当てられました. いちびんは前回大会では二次予選シードで出ていたソフトです.

将棋はいちびんの矢倉に対しponkotsuの雁木となりました. 80手くらい互角でしたが, 途中でなんとかリードを奪うことに成功し, 連勝を決めることができました.

棋譜はこちらです.

live4.computer-shogi.org

3回戦(まったりゆうちゃん戦)

3回戦は古豪との対戦となりました. まったりゆうちゃんは東京農工大学の小谷研究室で開発が続けられているソフトらしいです(今は小谷先生が退官されて研究室はないらしいですが…)

将棋は角交換三間飛車となり, 居飛車のponkotsuが序盤で銀・香・桂を確保し, 一方的な展開となり56手という短手数での勝利となりました.

棋譜はこちらです

live4.computer-shogi.org

4回戦(HoneyWaffle戦)

4回戦は再び強豪との対戦になりました. HoneyWaffleは振り飛車を指すソフトとして有名です. 6年前には決勝進出を果たしただけでなくDL系への路線変更を行った後には昨年末から年初に行われた, 電竜戦ハードウェア統一戦への出場も果たしています.

幸運にも本局は先手を取ることができ, 先手の利を生かしながら勝利を収めることができました. 開発者個人の感想としてponkotsuは対振り飛車が苦手だと思っていたので, ここで振り飛車ソフトの強豪に勝てたのは非常に嬉しかったです.

棋譜はこちらです.

live4.computer-shogi.org

5回戦(ねね将棋戦)

5回戦は全勝同士の対戦となりました. ねね将棋はiPadで動かしているソフトで, 前回大会では二次予選シードだった強豪です. 今年はNNUEとDLの合議を行っていたそうです.

将棋は途中までponkotsuがわずかにリードを奪ったかに見えたのですがそこからうまく指されて負けとなりました.

棋譜はこちらです.

live4.computer-shogi.org

6回戦(将スタ君戦)

6回戦は2敗勢との対戦となりました. 将スタ君は十六式いろは煌を開発しているすえよしさんがpython-dlshogi2をベースとして初心者でも手軽にDL系のソフトを開発できるように作られた, 将スタ -将棋ソフトスタジオ-をベースに開発されたソフトです. 本家の差分として, 定跡を搭載できるようにしたらしいです.

将棋は相雁木のような形となりました. 序盤から中盤の入り口にかけてponkotsuがリードを奪うことに成功し, 5勝目を挙げることができました.

棋譜はこちらです.

live4.computer-shogi.org

7回戦(技巧戦)

7回戦では強豪ソフトとの対戦となりました. 技巧は2017年の大会で準優勝しているソフトで, 今年久しぶりの出場でした. DL系に舵を切っており, 既存の技巧とは全く別のバージョンになっているようです.

将棋は後手のponkotsuが横歩取りにしました. 途中まで形勢不明でしたが42手目あたりで技巧がこちらに何度も手を渡すようになってから徐々にこちらに形成が傾き, 6勝目を挙げることができました.

棋譜はこちらです.

live4.computer-shogi.org

この対局での勝利によって最終戦の結果を待たずに初の二次予選進出が決定しました.

8回戦(アストラ将棋戦)

最終戦はここまで全勝のアストラ将棋との対戦となりました.

将棋としては相矢倉となり, 互角の展開だったのですがなんとここでponkotsuがクラッシュしてしまい, 負けとなりました…

棋譜はこちらです.

live4.computer-shogi.org

ということで一次予選は3位という結果になりました.

二次予選の様子とか

二次予選ではうまく評価値と読み筋を送れるようになったのであります.

1回戦(ティー⚪︎の振り飛車気持ちよすぎだろ戦)

完全にあれを彷彿とさせるソフト名ですが, 去年は決勝リーグ入りをしている強豪振り飛車ソフトです. 対抗系の将棋になるかと思われましたが3手目に相手が▲2六歩としたことで振り飛車の可能性がゼロになり, 呆気に取られていました.

序盤早々に飛車を取り合う激しい展開となりましたがなんとか勝つことができました.

棋譜はこちらです.

live4.computer-shogi.org

2回戦(HoneyWaffle戦)

2回戦では一次予選の再戦となりました. 一次予選とは違い今度はponkotsuが後手番となりました.

将棋は相入玉となり, ponkotsuの宣言勝ちが濃厚になってきたのですが, ちゃんと宣言できるのか分からず慌てていたらなぜか詰まして勝ちました…

棋譜はこちらです.

live4.computer-shogi.org

computer-shogi-live.cocolog-nifty.com

二次予選からはYouTubeで配信されている公式中継でプロ棋士の方が解説をしてくださっているのですが, そちらで取り上げていただきました.

www.youtube.com

3回戦(やねうら王戦)

3回戦は過去に優勝経験もある超強豪ソフトとの対戦となりました.

角換わりの将棋となり, 千日手模様となったのですが, こちらから打開しに行ったのが良くなかったらしく, 負けとなりました.

棋譜はこちらです.

live4.computer-shogi.org

こちらも解説で取り上げていただきました.

www.youtube.com

4回戦(いちびん戦)

2勝1敗で迎えた4回戦は再び一次予選で当たった相手との対戦となりました. いちびんの方は昨日使用したマシンよりスペックの高いものを用意しており, 苦戦することが予想されていました.

将棋は互いに中住まいっぽい形で進行していました. 終盤は互いの玉が中段にいる激しい展開となり, 最後まで勝負は分からなかったのですが, 207手目の△4五龍と龍を切る派手な手から詰ましきることができました.

棋譜はこちらです.

live4.computer-shogi.org

この対局を見ていたCSAの理事の方からいいものを見せてもらったとお昼ご飯を奢ってもらいました！！！

5回戦(名人コブラ戦)

5回戦はまたまた強豪ソフトとの対戦となりました. 名人コブラは昨年決勝に進出しているソフトです. 実は前日のテスト対局で当たっており, そのときには負けていたので正直勝てないと思っていました.

案の定というべきか力を出させてもらえないまま負けとなりました.

棋譜はこちらです.

live4.computer-shogi.org

6回戦(LightWeight戦)

6回戦も強豪ソフトとの対戦となりました. LightWeightはDL系のソフトでネットワーク構造にEfficientNetを使用しているのが大きな特徴です. 昨年には決勝に進出しています.

DenseNetの優位性を示したかったのですが, ずるずると形勢を広げられ負けとなりました.

棋譜はこちらです. live4.computer-shogi.org

7回戦(koron戦)

7回戦も強豪ソフトとの対戦となりました. koronは2年前が初出場で, そこから毎年二次予選シードを獲得しています.

将棋は角換わりとなり, 互角の展開だったのですが相手にトラブルがあったようで反則勝ちとなりました.

棋譜はこちらです.

live4.computer-shogi.org

8回戦(大将軍戦)

8回戦も強豪ソフトとの対戦となりました. 大将軍は2年前に決勝進出を果たしています.

かなりの苦戦が予想されたのですが, 序盤から大将軍にやりたいことをやらせないまま押し切り, 金星を上げることができました.

棋譜はこちらです.

live4.computer-shogi.org

こちらは解説で取り上げていただきました.

www.youtube.com

また, この勝利で初の二次予選で初の勝ち越しを決め, めちゃくちゃ喜んでいたら公式の中継ブログに記事にされました.

computer-shogi-live.cocolog-nifty.com

9回戦(二番絞り戦)

勝てば決勝進出の最終9回戦は昨年準優勝の超強豪との対戦となりました. 角換わりの将棋となったのですが序盤でなんとponkotsuがクラッシュしてしまい, 負けとなりました.

棋譜はこちらです.

live4.computer-shogi.org

また, この対局を最後に使用していたマシンが壊れました…

結果5勝4敗で11位という結果で今年のWCSCは終了となりました.

課題

今年は昨年と比べて大躍進だったものの, ハード面・ソフト面双方の課題が浮き彫りとなりました.

まず, ハード面に関してはまず長時間フルスロットルで安定して動かし続けることの重要性を実感しました. 特に排熱性能の重要性を実感しました. 昨年まではソフト自体の性能があまり良くなく, マシンリソースをフルに使うことがなかったのですが, 今年は一転してGPUは常時使用率100%, CPUも50~100%の使用率となっていました. その結果パーツが長時間熱にさらされて普段とは比べ物にならないほどのダメージを与えていました. 今回研究室のマシンを借りて出場していたのですが, そのマシンのケースが比較的小さく, 排熱性能が良くなく熱がこもりやすくなっていました.

また, 二次予選進出ソフトの中ではスペックはあまり高い方ではなく(それでもRTX3090を積んでいるので一般的にはとても良いのですが), マシンスペックの差が浮き彫りになった気がします. 特に二次予選シード勢はほとんどがクラウドを借りているかハイエンドGPUを複数枚積んでいました. 対局中や大会終了後, もっといいスペックのマシンを使用していればより大きい機械学習モデルを使えるのになあと考えていました. 大会前はこれでも十分なスペックだと思っていたのですが, 大会を通じて決勝進出や決勝で勝っていくことを考えると十分ではないのかもしれないと思いました.

次にソフト面ですが, 修論提出後から始めたこともあり時間がなく, 試したいことを試しきれませんでした. 特に定跡の整備や探索パラメータの最適化は十分ではなかったと考えています. また, 過度にNPSが低下することを恐れており, 機械学習モデルのレイヤ数を増やすことができませんでした. 一般にレイヤ数が増えれば識別精度は向上する傾向にあるので試してみてもよかったのかもしれません.

今後の展望とか感想とか

今大会では目標としていた二次予選シード入りを果たすことができ, 十分な成果を得られました. しかしマシントラブルにより決勝進出のチャンスを逃したのが非常に痛かったです. 今回の反省を活かし, さらなる識別精度の向上や排熱性能の良いマシンの錬成, そしてクラウド利用に手を出してみようと思います.

また, 今回良い成績を収めることができたため, やったことをGPWで発表しようと思います.

大会後でモチベーションが上がっているためやる気があるうちに進めるところまでやろうと思います.

今年もponkotsuを応援してくださりありがとうございました. 来年は決勝進出を目標に頑張りたいと思います.

メイカー〆切祭に出展したオセロソフトとの対戦システムについて

web コンピュータ プログラミング

お久しぶりです. メリクリ!今年もぼっちだぜ(ヤケクソ)!!!

この記事はesys Advent Calendar 5日目(12/25分)の記事です.

adventar.org

ぼくはesys17で現在はimis21のM2です. *1

本記事では11月に行われた学祭の中のいち展示企画であるメイカー〆切祭に出展したオセロソフト dekunobouとの対戦コーナーの実装について解説しようと思います. メイカー〆切祭ってなんぞやって方は本アドカレ1日目で@skmmmpさんが書いてくれていますのでこちらをご覧ください.

note.com

概要

メイカー〆切祭でぼくは来場者の方々に自作のオセロAI dekunobouと対戦してもらう対戦コーナーを出展することになりました. オセロAIとの対戦コーナーは新型コロナウイルス流行前の学園祭でも出展しており, その際は人力で人間の着手をPCに入力し, 返ってきたAIからの着手を人間がオセロ盤に打つといういわゆる代指しを行うことで実現していました. しかしながら, 昨今の感染症拡大予防の風潮的に今回もこのような方法を取るのはよくなく, かつ実現方法に技術的進歩が見られないのはちょっとダサいと思ったので, 展示会場内でオセロソフトとの対戦用のWebサーバーを建てて来場者のスマートフォンからdekunobou と対戦できるようにしました. 本記事ではこの対戦システムについての解説を書きます.

実装したコードはこちらに上がっているので合わせてご覧下さい.

github.com

システム構成

オセロAIとの対戦システムのシステム構成は以下のとおりです.

オセロAIとの対戦システムのシステム構成
Raspberry PiをWiFiアクセスポイント兼Webサーバーとして, 来場者の方々にはここにアクセスしてもらうようにしました. そして, 別途AIの着手を生成するAPIサーバーをノートPCの方に建てて, Raspberry Pi に建てたWiFiアクセスポイントに接続しておき, クライアントが着手するたびに着手の生成をリクエストするようにしました. これは, Raspberry PiのCPUよりノートPCのCPUのほうが性能がよく, より速くそしてより強い着手を生成してくれるはずだと考えていたためです. また, このAPIサーバーにはデータベースを搭載し, ここにAIの戦績を記録するようにしました.

やりたかったこと

対戦システムでやりたかったことは以下のとおりです.

  • レスポンシブ対応
  • AIの戦績の記録と表示
  • 先後選択機能の実装
  • Captive Portal上への対戦ページの表示
  • AIの強化(後日別の記事で解説する予定です)

これを, 昨年にWebで公開したオセロAI dekunobouとの対戦ページでの実装をベースにすることにしました. この実装はこちらに上がっています.

github.com

ここからはやりたかったことについて個別にどうやったかなど書いていこうと思います.

レスポンシブ対応

現在Webで公開中のオセロAIとの対戦ページではレスポンシブ対応を全くしていないため, スマートフォンからアクセスする場合は一度ユーザーが拡大しないとプレイできないという非常にユーザーアクセシビリティが悪い仕様になっています. そのため, 来場者の方に気持ちよくプレイしていただくため, レスポンシブ対応を行うことにしました. 学園祭本番までに実装する時間が限られていたこと, そして来場者のほとんど方はプレイする際スマートフォンを使用されるだろうということでモバイルのみレスポンシブ対応を行うことにしました. 実装はこちらをご覧ください.

github.com こちらに関しては後日PCのレスポンシブ対応も行った上でWebの方にも公開する予定です.

AIの戦績の記録と表示

来場者の方に自分のAIの強さを知っていただくには今のAIの戦績を表示するのが1番だと考えていました. そのため, コロナ前の学園祭でも黒板にAIの戦績を書いていました.

コロナ前のオセロソフトとの対戦コーナーの戦績表示
今回は対戦システムを通じて来場者の方に対戦してもらうため, 同時に複数の対局が行われることが予想され, 手動での集計は厳しいと考えていました. そのため, 戦績の記録と集計を自動で行うことにしました. 実現方法としてはよくある方法で, 対局が終了するごとにクライアントからリクエストを飛ばして勝敗と取った石の枚数を記録していくようにしました. データベースは今後自分のWebサイトでも戦績の表示を行いたいと考えていたため, Postgres SQLを使用しました. というのも公開しているWebページではAIの着手の生成にherokuを使用しており, herokuではPostgres SQLがサポートされているためです. この実装はこちらをご覧ください.

github.com

github.com

こちらも今後Webの方に公開予定ですが今の実装だと脆弱性がありそうなので対策が必要だと考えています*2

先後選択機能の実装

Webに公開しているものだと人間は先手しか選べない仕様で, この仕様のままだと来場者の方に楽しんでいただけないと思っていました. そのため, こちらも実装することにしました. これは開発段階では優先度が低く(手番を選択できるかに関わらず動くものを出せるかのほうが重要なため)学園祭当日までの日数が限られていることを考えるとかなり優先度が低かったのですが, 時間が余ったため実装しました.

この実装はこちらをご覧ください.

github.com

Captive Portal上での対戦ページの表示

これが1番やりたかったことです. 今回, 純粋に来場者の方とAIの戦績を表示したかったため, 対戦システムはオンプレミスで設置するべきだと考えていました. そうすると取れる選択肢は来場者の方に対戦システムのローカルネットワーク上にアクセスしてもらうことしかありませんでした.

一般のユーザーからするとローカルネットワーク上にアクセスしてもらうのはこちらがWiFiアクセスポイントを建てておき, それに繋いでもらうことで簡単にできますが, そこからさらにもう1ステップ踏んでローカルネットワーク上のWebサイトにアクセスしてもらうのは難しいと考えていました. そのため, WiFiに接続時にブラウザが立ち上がって認証画面を表示するCaptive Portalを使用するのが最適だという結論になりました.

Raspberry PiにCaptive Portralを設定する記事があったのでこれを参考に設定を行いました.

しかしながら手元で動かしてみた結果Raspberry Piがインターネットに接続されていないとどうもCaptive Portalがうまく起動しないようだったので諦めてローカルネットワーク上に設置したWebサーバーにアクセスしてもらうことにしました. そして来場者の方にもわかりやすいように以下の写真のようにWebサーバーへのリンクをQRコードで表示しました.

実際に表示していたスライド

実際の運用

当日, 来場者の方のスマートフォンでうまくアクセスできないときのための対策としてあらかじめ自分のiPadで接続しておき, これを常時対戦コーナーに設置しておくようにしました. これが功を奏し, 多くの来場者の方に対戦してもらえたと感じています.

反省点

今回の対戦システムの開発にあたって, iPhoneのテストはできていたのですがAndoroid端末が手元になくAndoroid端末でのテストができていませんでした. そのため, 結果としてAndoroid端末を使用されている方がうまく対戦システムに接続できないという問題が多発しました. ここは開発段階でAndoroid端末を持っている知り合いに声をかけてテストしてもらえばよかったなあと思っています. よくテストは大事だと言われていますが改めてテストの重要さを思い知りました.

最後に

今回初めてインフラ?周りからバックエンドそしてフロントエンドまで幅広い領域の開発を体験しました. 特にネットワーク周りの知識がなく, 本番当日までに間に合うかかなり不安でしたがなんとか間に合わせることができて良かったです. 開発中はなんか自分がつよつよになった感じがして気持ちよかったです.

今後就職したときとかに今回の経験を活かせるといいなあと思います.

*1:修論書きたくないでござる

*2:有識者の方いたら教えてください

WCSC32参加記

コンピュータ プログラミング

第32回世界コンピュータ将棋選手権(WCSC32)に参加しました.

大会の概要

WCSCは最も強い将棋ソフトを決める, 1990年から開催されている伝統ある大会です. 大きな特徴としてはマシンスペックに一切の制限がないところで, 上位勢はAWSのインスタンスを大量に借りたり, 会社で自由に使うことのできるNVIDIA A100を大量に使用していたりします. 大会自体は3日かけて行われ, 1日目に1次予選を, 2日目に2次予選を, 3日目に決勝リーグを行い優勝者を決定するようになっています. 1次予選から決勝リーグまですべてリーグ戦で行われます. 対局は持ち時間15分, 1手5秒加算のフィッシャルール, 320手の時点で勝敗が決定しない場合は引き分けというルールになっています. また, 対局相手はスイス式により決定します.

具体的なルールや概要はこちらをご覧ください.

ja.wikipedia.org

一昨年, 昨年とオンラインのみの開催*1でしたが今年は現地及びオンラインのハイブリット開催となりました. この参加記は1次予選に参加した参加記となります.

ソフトの概要

ソフト名は去年から引き続きponkotsuというソフト名で出場しました. 今年は, DeepLearning系ソフトに定跡を積まずに振り飛車を指させることを目標に開発しました.

手法としては, 振り飛車専用のネットワークと局面評価専用のネットワークを用意し, それぞれPolicy NetworkとValue Networkに割り当ててMCTSを行うようになっています.

振り飛車専用のネットワークは振り飛車を指す将棋ソフトとして有名なHoneyWaffleを手元で自己対局させて生成した棋譜(約2万局分)を教師データとして学習させています. 局面評価専用のネットワークはfloodgateの2015年～2021年の棋譜(数えていないので局数は不明. 恐らく50万局程度)を教師データとして学習させています. いずれのネットワークも学習時にはPolicyと勝敗の双方を学習するマルチタスク学習を行っています.

結果として主に四間飛車を目指して自分から飛車を振るソフトが完成しました.

今年の成績

今年は1次予選で4勝4敗と指し分け, 参加した33チーム中19位の成績となり, 二次予選に進むことは叶わなかったものの昨年から大きく成績を上げることができました. 順位表はこちらをご覧ください.

対局の様子とか

※筆者は将棋が弱いため将棋の内容は将棋が強い人からしたら見当違いなことを書いている可能性が高いです. その点ご了承下さい.

1回戦(対きふわらべ)

1回戦は昨年頭金で詰まされたきふわらべとの対戦となりました.

先手番の将棋で初手5六歩と指したので中飛車にするかと思われましたが, なぜか居飛車のまま指し始めました… 今年はしっかりと詰まして無事勝利することができました.

棋譜はこちら

tsec-shogi.com

2回戦(対TMOQ)

後手番の将棋で, 4手目に角道を空けたまま4二銀と上がる大悪手により角をただ取りされて負けました. ただ意外にも70手まで生き永らえることができました…

棋譜はこちら

tsec-shogi.com

3回戦(対こまあそび)

2回戦までの結果を踏まえ, ここで評価関数のパラメータを差し替えました(2回戦まで前日に学習させたパラメータを使用していた). 最初の方に対局サーバとの接続トラブルでなかなか対局が始まらず, やきもきしてました*2.

今度は先手番となり, こちらの三間飛車にたいしてこまあそびが中飛車という相振り飛車の将棋になりました. 素人目には序盤から5段目に角が出てくる激しい将棋となりましたが, ponkotsuの玉頭の攻めがうまく刺さってくれたおかげで勝つことができました.

棋譜はこちら

tsec-shogi.com

昼休憩

3回戦終わってここで昼食休憩となりました. 昼食は会場にいた開発者の方々と川崎家に行きました. 川崎家は将棋ファンの間では永瀬王座のご実家として有名です. 現地参加できることが決まってからずっと行きたいと思っていたので行くことができて嬉しかったです. ラーメンは豚骨ベースでとてもおいしかったです.

4回戦(対Easy Shogi)

後手番の将棋で飛車を振ってくれるか不安でしたが2手目5四歩に続いて4手目に5二飛と振ってくれ, なんと中飛車の将棋になりました. いままでponkotsuくんが中飛車に振ってくれたことがなかったので驚きでした.

この将棋は詰まし切ることができ, 昨年の成績を超える3勝目を挙げることができました. Easy Shogiには昨年も勝っていたのですが, そのときは連続王手の千日手をかけられての反則勝ちというなんとも言えない結果だったので詰まし切ることができてよかったです.

棋譜はこちら

tsec-shogi.com

5回戦(対prelude)

ここまで3勝1敗という成績だったのでそろそろ上位勢と当たる気がしていたところに上位勢と当たることになりました.

preludeはプロ棋士の谷合四段が開発されているソフトで, 初戦にAobaZero*3に勝っていました. そのため, 対局がつくとわかったときにはボコボコにされると覚悟しました.

将棋の方は先手番で, 相向かい飛車というソフト同士の対局にしては珍しい戦型になりました. 自陣に角の打ち込む隙があるにも関わらず29手目で角道を開けて角交換を仕掛けに行くなど疑問手や細かいミスが相次ぎ, 見事に詰まされました. 谷合四段も会場にいらっしゃっていて, 対局を見ながら隣で解説していただいて貴重な時間でした.

棋譜はこちら

tsec-shogi.com

6回戦(対Argo)

またまた強いソフトと当たることになりました… 今度は後手番の将棋で, こちらの四間飛車銀冠に対して先手の居飛車穴熊になりました. こちらは評価値的にはじわじわと差を広げられて負けました.

棋譜はこちら

tsec-shogi.com

7回戦(対なのは)

ここら辺で欲が出てきて指し分けに持っていきたいと考えていたところまた強いソフトと当たることになりました… 先手番の将棋で, こちらが三間飛車となる対抗形になりました. よくわかってはいないのですが, 序盤の方でなのはの定跡にない展開になったのか時間を使わせる展開になってワンチャンスあるのではと思ったのですが, 無事詰まされました…

棋譜はこちら

tsec-shogi.com

8回戦(対wizodds 2022)

いよいよ指し分けまで後がなくなり, ただひたすらお祈りしてました. 後手番の将棋となり, こちらの四間飛車の急戦っぽい対抗形となりました. 序盤から角を交換し合う激しい展開な上にponkotsuがなぜか飛車先の歩を突こうとしない謎挙動がありヒヤヒヤしていましたが, 40手目で桂を丸得することができ, 見事勝つことができました. これで4勝4敗と指し分けることができました！

棋譜はこちら

tsec-shogi.com

課題

今回の大会に参加して次のような課題が見つかりました.

  • 振り飛車は指せるが振り飛車の大きな特徴である捌きをしない(らしい)
  • NPS(1秒に読むことのできる局面数)が低い
  • 要所要所でミスをする

いずれも決定的な解決策が見えていないのでおいおい解決していきたいです.

今後の展望

感想

昨年と比較してかなり強くなり, 研究室で先生に指してもらったときにも勝つことができたため去年の成績を超えられそうな気はしていました. それが結果的には指し分けという結果になり, 非常に嬉しかったです. しかし, 一方で上位陣に対してはまだまだ勝つことができず, 4勝と5勝の間には大きな壁があることがわかりました. 今大会を通じて多くの課題が見えたため, これらを修正して7月に開催されるTSEC*4に備えたいと思います(なお研究の進捗…)

ちなみに8回戦終了後先生からお祝いのメッセージをもらった上に褒められが発生して気分が良かったです.

最後に

初めて現地参加してみて思ったのですが, 若い人が少なかったです... 現地参加した人が少なかったのもあると思うのですが現地勢だとぼくが1番年下で, オンライン参加含めても多分ぼくより年下の人が2人だけというような状態でした.

ここ数年で将棋ソフトの作り方を詳細に解説した本が出版されていたり強い将棋ソフトのコードやそのソフトが使用した大量の質の良い教師データがオープンソースで公開されていたりと新規勢が参入しやすい土壌が急激に整ってきています. また, 将棋ソフトを作成して大会に出たことを就活時にESに書いたり面接で話したりすると仮に大会での成績が芳しくなかったとしてもものすごく受けがいいです. 個人的には将棋ソフト開発は競プロより就活の役に立つと思います.*5 まだ将棋ソフトを開発していないそこのあなた！これを読んでぜひ開発して大会に出場しましょう！！！

*1:一昨年は大会自体は中止で, 代替のオンライン大会が開催された

*2:運営の皆さん, お疲れ様です…

*3:AlphaZero追試で開発が始められたソフト. 平手でも駒落ちでも強い

*4:指定された局面から指し始める将棋ソフトの大会

*5:競プロはあくまでも基礎体力しか測ることができないことを考えると比較するのはあまり良くないかもしれません…

就活エントリ

TL上の人々がよく書いている就活エントリなるものを書いてみます.

最初に

先日某社から内定をいただいて卒業後の就職先が決まりました！ やったね！
Web系？のエンジニアになる予定です.

このエントリではまず就活開始してから内定をいただくまでの流れを書いて, その後でESに書いたこととか面接で聞かれたこととか感想とかを書いていこうと思います.

就活中の基本スペック

内定をいただくまで

4月くらい

就活の存在は知っていたもののやり方が分からなかったので研究室の先輩にやり方を聞いてみる. 理系専用の某就活サイトを勧められたのでとりあえず登録した. あと先輩からpaizaでSランクまで上げとけって言われたのでちょっと頑張ってAランクまで上げた. そこから先は少しモチベーションが下がったので諦めた.

中旬くらいに弊学生限定の企業とのミートアップイベント？的なものに誘われ, 参加する. みんな強そうな見た目をしていた上に来てくださった企業もどこもいかつくてこれ厳しくないか？というお気持ちになる. インターンの宣伝が主体だったものの自分が合格できるビジョンが見えなかったので結局応募しなかった. ちなみに確かアマギフを頂いたのでお得だった.

5月

なんとか間に合ってWCSC(将棋AIの世界大会)に出場できたのでそのことを就活サイトに書いていく.

6月

大手SIerからスカウトが来たので話を聞いてみる. AI系の職種でしっかりと僕の持つスキルなどを見てくださっていて印象が良かったのでインターンに申し込んだ.

7月

この時期くらいに申し込んだインターンの合否結果がきた気がする. なんだかんだで合格し安心する.

中旬くらいにゲームだったりインターネット関連だったりを幅広く取り扱っている某大手からスカウトがきたのでカジュアル面談をしてみる. あまり自分と合わなさそうだったので結局何もしなかった.

8月

お盆の期間中に夏休みの自由工作&インターンでのネタ作りのため開発していたオセロソフトをブラウザ上で対戦できるWebアプリを開発する. Webアプリの開発経験があまりなく, 右も左もわからなかったのでつよつよの友人に聞きながら完成させた. これがきっかけでWeb系も面白そうだなというお気持ちになった.

下旬にインターンがあったので参加. 主にコンサル系の上流工程の内容でしかもあまり時間がない&コーディングをする機会がほとんどなくかなりきつかった. あと, 他のインターン生の中で強い人だったりプログラミングとかが好きな人を観測することができず, 仮に入社できたとしても楽しくなさそうだなと感じて少し志望度が下がった.

このインターンをきっかけに実装メインのインターンがないか探し始める.

9月

1社実装メインのインターンを応募してみるもののコーディング試験で無事お祈りされる. かなり業プロ経験がないと気づけないような要素で落とされたのでつらかった.

途方に暮れていたところに現内定先からスカウトがきて, しかも実装メインのインターンにお誘いいただいたので迷わずエントリーする.

10月

この時期くらいからpaiza経由でスカウトくださった会社と徐々にカジュアル面談を行う.

上旬に8月にインターンに参加した某社からインターンで優秀だった人向けの早期選考説明会兼イベント的なものに招待されたので参加を申し込む.

中旬に現内定先のインターンの選考に合格したので参加する.

11月

10月にカジュアル面談を行った会社の選考を受け始める.

上旬に10月に申し込んでいた早期選考説明会兼イベント的なものに参加. 選考がかなりつらそうだったので選考は見送った.

中旬に現内定先のインターン(2回目)に参加する. インターンで参加者特典としていくつか選考をスキップできるとのことだったので選考を受けてみるかというお気持ちになる.

下旬くらいに選考を受けた1社からお祈りされて悲しくなる.

12月

何してたっけ…？ 年末に1社最終面接があったので受けに行ったことだけ覚えてる.

1月

中旬くらいに年末に最終面接受けた某社からお祈りされて悲しくなる. この時期くらいからかなり焦っていて将来の不安を感じていて夜もあまり眠れなかった. ひとまず現内定先の選考にエントリーする.

paizaでスカウトをくださった某社の選考にエントリーし, ESでFortranへの愛を叫ぶ. これのおかげかわからないが1つ選考をスキップして3次選考を受ける.

2月

再びpaizaでスカウトをくださった企業とカジュアル面談をしたり選考にエントリーしたりする.

上旬くらいに現内定先の一次面接を受ける. 最初に自分が使っていた仮想背景に触れてくれたり, 面接自体かなり盛り上がったりしてものすごく手応えを感じた.

翌日に一次面接合格だよって連絡きて流石に早すぎないか…？というお気持ちになる(めちゃくちゃ嬉しかったです)

下旬に二次面接を受ける. 個人的にあまり上手に受け答えできず, 落ちたかもしれない…というお気持ちになる.

この翌日に別の企業の4次面接を受ける. 面接中にうちより研究職のほうが向いているんじゃない？とか, 結構好奇心だけで突っ走ってる印象だけど本当にそれで大丈夫？とか言われて心が折れる.

3月

さすがにどこも受かる気がしないというお気持ちになり, もう1社エントリーする. その直後くらいに現内定先から内定の連絡を頂いて就活が終了.

ESに書いたこと

エンジニア職の選考だったため, 好きな言語・得意な言語だったり今まで自分が開発したものだったりという設問がメインだったので正直にやってきたことをかきました. 好きな言語・得意な言語では他の人と被るのが嫌だったのでPythonとかC++とは回答せず, あえてFortranと回答していました. 自分が受けた企業がWeb系が多かったため, 主に数値計算の用途で使用されているFortranを他の応募者は触ったこともなく, 人事の目に留まりやすいのではという読みも若干ありました. ちなみにこれが効果があったかどうかは知らないです.

面接で聞かれたこと

4社ほど受けた中で共通して聞かれる質問もいくつかあったため, これから就活に望まれる皆さんはこれらの質問の回答を考えておくと幸せになれるかもです.

  • 入社したらどのようなことをしたいですか？
  • 現所属に入学したのはなぜですか？
  • なぜ博士課程に進学しないのですか？
  • 大学ではどのような授業をとっていましたか?+そこから突っ込んだ質問(どんなことを頑張ったかなど)
  • 競技プログラミングを始めたきっかけ
  • 就活の軸はなんですか？
  • 他にどのようなところを受けましたか？
  • 御社のどこに魅力を感じましたか？
  • 今までの人生で価値観が変わったエピソードを教えて下さい
  • 大学・大学院で履修した授業のうち, 御社の業務で役に立ちそうな科目は何だと思いますか?

感想(ポエム)

とりあえず就活, 辛かったです. 選考を受けてみた感じ, 技術力に関しては受けた企業の基準を満たしており, 面接の非技術的な質問で答えた内容で落とされまくっていました. そのため, 上で書いた質問には一通りしっかりと答えられるように対策をしておくべきだと思います.

次に, よく議論になりがちな競プロが就活にどのくらい役に立つのか問題ですが, 選考を受けた感じ, アルゴリズム力の面よりも自発的に行動を起こす能力だったり継続的に勉強をする能力を高く評価してくださっている印象でした. そのため, アルゴリズム強者を探している会社以外を受けるのであれば緑色でも技術力面では問題なくかなり高く評価をしてくれるため, 面接対策や作品制作を頑張ってエピソードづくりをするとレートを上げるよりも効果が高いと思います. ただ, あくまで個人的見解にすぎないため実際のところどうなのかはわからないです.

最後に, 卒業がんばります. あと僕のこと落とした某社の人たちにこいつ落とさなきゃよかったって後悔させたいです.

ABC232 をFortranで解く(A問題~D問題)

競技プログラミング プログラミング コンピュータ

コンテスト中のFortranでの提出がぼくのB問題だけだったのでD問題までFortranで解き直しました.
ちなみにE問題から後ろは筆者の実力がないので解いていないです…

A問題 - QQ solver

コンテスト中はPythonで通しました. Pythonだと楽勝なのですがFortranだとかなりめんどくさいです.
Fortranを日常的に使わない茶色以上の人たちはPythonとかC++とかもっと書きやすい言語に逃げるのが得策だと思います. 解説にもある通りcharacter型の"0"から引き算をして"0"よりいくつ大きいかを計算してあげるといいと思います.
Fortranの場合cをchar型の変数とした時, C++みたいにc-'0'と書くとおこられるのでichar()を使いましょう.
実装

program main
    implicit none
    integer::i=ichar("0")
    character(3) S
    read*,S
    print'(i0)',(ichar(S(1:1))-i)*(ichar(S(3:3))-i)
end program main

提出

atcoder.jp

B問題 - Caesar Cipher

まあまあ典型です. Kは0~26のいずれかなので全探索して一致するか見てしまえば終わりです.
FortranだとアルファベットをK個後ろにずらすという操作がまあまあ面倒です. cをcharacter(1)型の変数としたときに愚直にchar(ichar(c)+K)とすると例えばc="z"でK=1だったときに"a"ではなく"{"になってしまい, 大変なことになってしまいます.
そこで, まずcが"a"から何文字後ろの文字なのかを見て, そこからKだけ後ろにしてあげるという処理を行います. これに26で割ったあまりを取ってあげることで必ず0~26のいずれかの値になり, 必ず"a"~"z"のいずれかになってくれます.
下の実装のうちref=mod(ichar(S(j:j))-97+i,26)でichar(S(j:j))から97を引いているのはichar("a")が97だからです.

実装

program main
    implicit none
    integer i,j,ref
    character(100000)S,T
    logical flg
    
    read*,S,T
    do i=0,26
        flg=.true.
        do j=1,len_trim(S)
            ref=mod(ichar(S(j:j))-97+i,26)
            if(char(97+ref)/=T(j:j))then
                flg=.false.
                exit
            end if
        end do
        if(flg)exit
    end do

    if(flg)then
        print'(A)',"Yes"
    else
        print'(A)',"No"
    end if
end program main

提出

atcoder.jp

C問題 - Graph Isomorphism

考察パートは特に難しくなく, 一瞬で全探索が浮かぶのですがFortranでの実装がかなり面倒です. コンテスト中は素直にC++とかPythonのように順列を生成するライブラリが実装されている言語を使用しましょう() ぼくもコンテスト中はPythonで書きました. 当然Fortranには順列を生成するライブラリはないので自分で実装しました.

!pythonのitertools.permutationsのFortran版のようなもの
module permutations_values
    implicit none
    integer(8)::cnt=1,l_len=10**8
end module permutations_values
program main
    use permutations_values
    implicit none
    integer(8)N,i
    integer(8),allocatable::L(:,:),A(:)
    read*,N
    allocate(A(N))
    allocate(L(l_len,N))
    do i=1,N
        A(i)=i
    end do
    !第2引数に生成したい順列の長さ,
    !第3引数に順列を生成したい配列(1~Nまでの順列なら1~Nの配列),
    !第4引数に結果を格納する配列を入れる
    call permutations(1_8,N,A,L)
    print'(i0)',cnt
    do i=1,cnt
        print*,L(i,1:N)
    end do
end program main

recursive subroutine permutations(k,n,a,L)
    use permutations_values
    implicit none
    integer(8),intent(inout)::n,a(1:n),L(1:l_len,1:n)
    integer(8) i,tmp,k

    if(k==n)then
        L(cnt,:)=a
        cnt=cnt+1
    else
        do i=k,n
            tmp=a(k)
            a(k)=a(i)
            a(i)=tmp
            call permutations(k+1_8,n,a,L)
            tmp=a(k)
            a(k)=a(i)
            a(i)=tmp
        end do    
    end if
    return
end subroutine permutations

これが完成すればもう8割は解けたようなもので, グラフを隣接行列で管理して, 高橋くんのグラフと青木くんのグラフが完全に一致するか判定してあげれば終わりです.

実装

module permutations_values
    implicit none
    integer(8)::cnt=0,l_len=10**5
end module permutations_values
program main
    use permutations_values
    implicit none
    integer(8)N,i,M,a,b,j,k
    integer(8),allocatable::P(:,:),ref(:)
    integer(8),allocatable::L1(:,:),L2(:,:),E(:,:)
    logical flg,ans
    read*,N,M
    allocate(L1(N,N))
    allocate(L2(N,N))
    allocate(E(M,2))
    L1=0

    do i=1,M
        !高橋くんが持っているグラフの隣接行列を作る
        read*,a,b
        L1(a,b)=1
        L1(b,a)=1
    end do

    do i=1,M
        read*,E(i,:)
    end do

    !順列を生成する
    allocate(ref(N))
    allocate(P(l_len,N))
    do i=1,N
        ref(i)=i
    end do
    !第2引数に生成したい順列の長さ,
    !第3引数に順列を生成したい配列(1~Nまでの順列なら1~Nの配列),
    !第4引数に結果を格納する配列を入れる
    call permutations(1_8,N,ref,P)

    do i=1,cnt
        !数列Pを順番に変えて青木くんの隣接行列を作り, 高橋くんのグラフと一致するか見る
        ans=.false.
        !青木くんの隣接行列を構成する
        L2=0
        do j=1,M
            L2(P(i,E(j,1)),P(i,E(j,2)))=1
            L2(P(i,E(j,2)),P(i,E(j,1)))=1
        end do

        !青木くんの隣接行列が高橋くんの隣接行列と一致するか見る
        flg=.true.
        do j=1,N
            do k=1,N
                if(L1(j,k)/=L2(j,k))then
                    flg=.false.
                    exit
                end if
            end do
            if(.not.flg)exit
        end do

        !完全に一致したならループから抜ける
        if(flg)then
            ans=.true.
            exit
        end if
    end do

    if(flg)then
        print'(A)',"Yes"
    else
        print'(A)',"No"
    end if
end program main

recursive subroutine permutations(k,n,a,L)
    use permutations_values
    implicit none
    integer(8),intent(inout)::n,a(1:n),L(1:l_len,1:n)
    integer(8) i,tmp,k

    if(k==n)then
        cnt=cnt+1
        L(cnt,:)=a
    else
        do i=k,n
            tmp=a(k)
            a(k)=a(i)
            a(i)=tmp
            call permutations(k+1_8,n,a,L)
            tmp=a(k)
            a(k)=a(i)
            a(i)=tmp
        end do    
    end if
    return
end subroutine permutations

3行目のl_lenを小さくしているのは, メモリ確保に失敗してREになったからです.

提出

atcoder.jp

D問題 - Weak Takahashi

これも考察は難しくなくて, とりあえずBFSしてスタートから最も遠い距離を出力してしまえばいいです. コンテスト中はqueueのライブラリ確か持ってないな～って思ってPythonに逃げたのですが, 自分のライブラリ見たらちゃんとFortranでqueueを実装したライブラリがありました… しかもご丁寧にBFSも実装してた…(なおコメントアウトが全く無くて解読するのが辛かった)

実装

!queueとBFS
program main
    implicit none
    type::auto
        integer(8)::y,x !xが行, yが列に対応
    end type auto
    integer(8)::elements=10**8
    integer(8)::top=1,tail=1,len=0
    type(auto),allocatable::que(:)

    integer(8)::dy(2)=(/0,1/)
    integer(8)::dx(2)=(/1,0/)
    type(auto) cn,nn
    integer(8)::H,W,ans=0
    integer(8)i
    integer(8),allocatable::dist(:,:)
    character(100),allocatable::S(:)
    allocate(que(elements))
    
    read*,H,W
    allocate(dist(H,W))
    dist=-1
    allocate(S(H))

    do i=1,H
        read*,S(i)
    end do
    dist(1,1)=1
    cn%x=1
    cn%y=1
    call push(que,cn)

    do while(len>0)
        cn=pop(que)
        do i=1,2
            nn%x=cn%x+dx(i)
            nn%y=cn%y+dy(i)
            if(nn%x>=1.and.nn%x<=H.and.nn%y>=1.and.nn%y<=W.and.S(nn%x)(nn%y:nn%y)==".".and.dist(nn%x,nn%y)==-1)then
                dist(nn%x,nn%y)=dist(cn%x,cn%y)+1
                call push(que,nn)
            end if
        end do
    end do

    do i=1,H
        ans=max(ans,maxval(dist(i,:)))
    end do
    print'(i0)',ans
contains
subroutine push(L,a)
    implicit none
    type(auto),intent(inout)::L(:)
    type(auto),intent(in)::a
    L(tail)=a
    tail=tail+1
    if(tail>elements)tail=tail-elements
    len=len+1
end subroutine push

type(auto) function pop(L)
    implicit none
    type(auto),intent(inout)::L(:)
    pop=L(top)
    top=top+1
    if(top>elements)top=top-elements
    len=len-1
    return
end function pop
end program main

提出

atcoder.jp

最後に

久しぶりにABC出たんですが, Fortranユーザーに優しくない問題が多すぎないか…？*1*2
あといい加減Fortran版APG4b完成させなさい

*1:そもそもAtCoderのFortranユーザー少ないから仕方ない

*2:もともとFortranユーザーに優しくない問題が多い説はある