jj1gujのブログ

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

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の場合cchar型の変数とした時, 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個後ろにずらすという操作がまあまあ面倒です. ccharacter(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:そもそもAtCoderFortranユーザー少ないから仕方ない

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

遺伝的アルゴリズムを使用したオセロAIの作成

遺伝的アルゴリズムを使ってオセロAIを作ったお.

この記事は筑波大学アドベントカレンダー13日目の記事です.

adventar.org

ぼくはesys17で現在はimis修士1年です.

最初に

今回作成したオセロAIとはここから遊べます. 遊びながらこの記事を読んでくれると嬉しいです.

jj1guj.net

概要

この記事では盤面の評価のパラメータ調整において遺伝的アルゴリズムを適用したオセロAIでくのぼうの詳細な解説記事となります. この記事では最初に遺伝的アルゴリズムを適用しやすいようにした評価関数の仕様を解説し, 次にその仕様に基づいた遺伝的アルゴリズムの適用方法を一般的な遺伝的アルゴリズムの方法と合わせ解説します. 最後に, Webで公開した際の構成を解説します.(あとで追記する) この記事では一般的なオセロAIと同様の機能(探索や盤面管理など)についての詳細な解説は行わないつもりです. こちらについての詳細な手法を知りたい方はにゃにゃん氏(@Nyanyan_Cube)が書かれているオセロAIの教科書を一読されることをおすすめします.

note.com

また, AIのソースコードはこちらで公開しています. この記事と合わせてお読みいただけると幸せになれるかもしれません.

github.com

評価関数の仕様

一般にオセロや将棋のような対戦型のゲームAIは以下の手順で指し手を生成し, 1ターンプレイします.

  1. ルールに基づいて次にプレイすることのできる手を生成する(合法手の生成).
  2. 生成した合法手からn手進める(探索, nは自然数).
  3. n手進めた先の局面に得点をつける(評価).
  4. 得点が最も高くなる手を着手する

このうち, 3.における局面への得点の付け方のことを評価関数と呼んでいます. 評価関数は最も工夫がしやすく, 開発者によって個性がでて面白いところです. 今回作成したオセロAIの評価関数は以下の式で定義しています.
\begin{align} L _ {i} & :\ 盤面の辺の石の並びの評価値\\ M _ {i} & :\ 盤面の斜め方向の石の並びの評価値\\ R & :\ 盤上の石のうち自石の占める割合\\ \alpha & :\ 定数(20手ごとに値が変わる)\\ 評価値& = \sum_ {i=1} ^8 L _ {i} + \sum _ {i=1} ^4 M _ {i} + 12\alpha R \end{align}

ここで定義されている$L _ {i}$, $M _ {i}$, $\alpha$はすべて正確な値を計算することができないため, これらの値を調整する必要があります.

辺の石の並びの評価

辺の石の並びは, 図1のように角から行方向, または列方向に4マス分抽出して評価します. ここでは, 例として縦方向の辺を抽出します.

f:id:jj1guj:20211212123807p:plain
図1: 辺の石の並びの取り出し方
縦方向の辺を抽出し, 角が1番右になるように回転させると図2のようになります.
f:id:jj1guj:20211212124506p:plain
図2: 抽出した石の並び

ここで, オセロの盤面の各マスの状態を考えると以下の3通りのみであることがわかります.

  • 何も石が置かれていない
  • 先手の石(黒石)が置かれている
  • 後手の石(白石)が置かれている

この事実から, 何も置かれていないマスを0, 先手の石(黒石)を1, 後手の石(白石)を2と表現すると辺の石の並びは3進数として表現できることがわかります. これをもとに, 図2を3進数で表すと$1200_ {(3)}$となります. ここでそれぞれの石の並びのパラメータを配列で保持しておき, 石の並びの評価値を前に示した3進数に対応するインデックスに格納されている値とすることで辺の石の並びの評価ができることになります. これを図3に示す8箇所全てに対して行い, 総和を取ります.

f:id:jj1guj:20211213140058p:plain
図3: 評価値を計算する場所

斜め方向の石の並びの評価

こちらは手法自体は辺の石の並びの評価方法と変わりません. ただし, 辺の石の並びの評価値とは別のインデックスから評価値を取ってくるようにしています. こちらは図4に示す4箇所について行い, 総和を求めます.

f:id:jj1guj:20211213140413p:plain
図4: 斜め方向の評価値を計算する場所
詳細な実装はこちらをご覧ください.

github.com

遺伝的アルゴリズムの適用

今回, 先に述べた評価関数で必要なパラメータ数は, \begin{align} & 81(辺の石の並びのパターン数)+\\ & 81(斜め方向の石の並びのパターン数)+\\ & 3(盤上に占める自石の割合)=165個 \end{align} となります. この全てを最適(AIが最も強くなるよう)に調整することはほぼ不可能です. そのため, これらのパラメータをAIが強くなるように調整するために遺伝的アルゴリズムを使用します.

遺伝的アルゴリズムとは

遺伝的アルゴリズムとは, 確率的探索アルゴリズムのひとつであり, 組み合わせ問題に対する最適解を求めることが計算量的に困難であるときに有効な手法です. 最適解が求められる保証はありませんが, ある程度の時間を費やせばそこそこの解が得られることで知られています. 「遺伝」というワードが入っているところから想像がつくかもしれませんが, 生物の進化から着想を得ています.

遺伝的アルゴリズムは以下の手順により行われます.

  1. 集団を構成する個体群を生成する.
  2. 交叉(個体群から2個体を取り出し親として, 子孫を生成する)
  3. 突然変異
  4. 選択

ここからはこれらの手順を今回作成したオセロAIでの手法をもとに具体的に説明していきます. 詳細な実装はこちらをご覧ください.

github.com

1. 集団を構成する個体群の生成

今回定義した評価関数では全部で165個のパラメータが必要なので, 1つの個体は長さが165の配列とします. また, 評価値計算時に発生するであろうオーバーフローを防止するため, 各パラメータは-1以上1以下の浮動小数点数を取ることにします. 個体群の数は今回は1024個とし, 最初に生成するときはすべて-1以上1以下の乱数で初期化します.

2. 交叉

交叉では最初に1.で生成した個体群からランダムに2個体選び出します(それぞれ便宜的に親A, 親Bと呼びます). その後, 図5のように任意の2点で個体を切断し, その間の値を入れ替えて子を生成します(親Aをベースにした子孫を子A, 親Bをベースにした子孫を子Bと呼びます). この2点はランダムに決定します.

f:id:jj1guj:20211213142449p:plain
図5: 交叉の様子

3. 突然変異

突然変異では2.で生成した子A, 子Bそれぞれに対して, すべての配列の要素を1%の確率でランダムな値に書き換えています.

f:id:jj1guj:20211213142737p:plain
図6: 突然変異の様子

4. 選択

選択では親A, 親Bと子A, 子Bのどちらを淘汰するかを決定します. 今回は強いオセロAIを作ることが目的なので, 弱い方を淘汰する必要があります. どちらが強いかを判定するためには直接戦わせてみるのが1番簡単です. そのため, 選択では親Aと子A, そして親Bと子Bでそれぞれ手番を入れ替えながら何回か対戦させます. そして, 子の方が親に対し一定以上の勝率があるのであれば親を淘汰し, ないようであれば子を淘汰します. 今回は全部で30回対戦させ, 55%以上の確率を基準に淘汰するかどうか判定しています. 対戦回数を多くすると交叉に時間がかかってしまう一方で対戦回数が少なすぎると偶然の要素が強くなってしまうため, 実際に測定してみて偶然の要素が少なくなるであろうギリギリのラインとして対戦回数を30回にしています. また, 勝率の基準を55%にしているのは, 例えば勝率51%は本当に実力に差があるのかというと疑問が出てくるため, 体感的に実力の差が出そうな基準が勝率55%であろうと考えたからです.

ここで紹介した2. 交叉~4. 選択を100回繰り返し, これを1回のループとして長い時間をかけて何度もこのループを回し, 評価関数のパラメータ調整を行っています. 短くても7時間はかかっています.

結果・課題

生成した評価関数をもとに, 先読みの機能等を実装し, webで遊べるようにしました. 開発者が対戦してみたところ, ぼこぼこにされるまで強くなりました.

一方で, 他のAIに対してはまだまだ勝率が低いことが課題となっており, まだまだ改善の余地があります. 勝率が低い原因として以下の事が挙げられます.

  • 先読みの性能が低い(一定時間で読める局面の数が少ない)
  • 序盤の精度が悪い

先読みの性能の低さはより高速な探索アルゴリズムを実装することで, 序盤の精度の低さはあらかじめ定石を用意しておき, 最初はその定石に載っている手を打つようにすることで改善できると考えられます. 尚, 今回作成したAIは序盤は弱いものの中盤は強いという評価を聞いていたりするので評価関数が弱いことが原因とは言い切れないと思っています.

今後の展望

今後は, 課題点を改善していき, 余裕があったら評価関数の仕様も少し変えてみようと思います. また, オセロAI以外にコンピュータ将棋のfloodgateのようなオセロAI用の連続対局場所を作り, 大会を開きたいと思っています.

最後に

現在, オセロAI開発者用のDiscordサーバーを運営しています. オセロAIの開発やオセロAI用の連続対局場所の開発に興味がある方は@jj1gujにDMを送ってくだされば招待します.

WCSC31参加記

第31回世界コンピュータ将棋選手権(WCSC31)に参加したよ!!

世界コンピュータ将棋選手権って何?

毎年ゴールデンウィークに行われる最強の将棋ソフトを決める大会. 特徴としてはマシン構成に制限がないこと.(過去に行われていた電王戦ではマシンスペックはすべて統一されていた) 例年川崎産業振興会館で開催されているけど今年はコロナのせいでオンラインになった. 今年で31回目(第30回はアイツのせいで中止)の由緒ある大きい大会. わかんなかったらとりあえずググればいいと思うの.

どんなソフトで出たの?

名前はponkotsu(色々準備できたらgithubのURL貼る)

ソフト名の由来はもし勝てたら負けたソフトor人はぽんこつに負けたってことになって悔しくなるだろうなあ笑って思ったからです(邪悪)
どんな技術突っ込(みたかった)んだかはアピール文書見てください.

さあ, こっから本文です!!

11月

電竜戦をやると聞き, 出てみたいなあと思いつつ色々調べて開発しようとするも間に合わなくて断念する. というかそもそもどのライブラリ使うかとか仕様が固まってなかった.

12月

学会発表で無事死亡

1月

卒論で無事死亡

2月

卒論発表終わってから嬉々として本格的に開発を始めるもlibtorchとcshogiの仕様にあまり詳しくないため開発が難航し大泣きする. てかこれ愚痴なんですけどlibtorchのことググるとpytorch出てくるのあれ何なんすか?pytorchとかいじって自称AIやってるいけいけエンジニアたちちゃんとlibtorchの記事も書けや*1 まあおかげで英語のドキュメント読むの苦にならなくなったりわかんなくなったらgithubのissueとかソースコード読んだりする習慣がついたのでね… クソ記事がでてこないというのもね…おっと, 誰かきたようだ…

3月

帰省したり諸事情で若干メンタルやられたりするものの一応進捗は生む.
AHC001に時間を吸われて進捗が虚無になる.

4月

4月末まで一切進捗を産まない*2*3.
4/18 に作業通話しながら一応動くものを完成させる.

4月末

弊研のボスにWCSC31出るんすよ~笑って言ったらめちゃくちゃ応援されたのでがんばって進捗を生む.
もともと探索機能を入れる予定はなかったけどABCで培った早解き力()*4MCTSを実装する.

4/25

AHC002に出る.
ギリギリで提出した解で順位が上がったのでいいコンテストだった.

4/29~5/2

盤面を特徴量ベクトルに変換するところでバグり散らかしてることに気づき格闘する.
5/2とか徹夜状態でバグと格闘して椅子の上で1時間寝たためか腰を痛める*5

当日朝4時

前日20時とかに寝たので4時くらいに目が冷めてバグがないか確認する.

当日朝5時

MCTS周りでバグを見つける. 全俺が泣いた.

当日朝9時

ローカルでできる限りロールバックしてとりあえず動く状態(でいるつもり)のバイナリを生成する.

1回戦(対ねね将棋)

生成しておいたバイナリがクラッシュして負ける. かなしい… 残った時間で朝発見したバグと格闘する.

2回戦(対こまあそび)

朝発見したバグと格闘しつつあっけなく負ける.

3回戦(対Aoba Zero)

開発者の方とお話しつつバグと格闘する*6 ponkotsuの飛車が単振動してるのみて「やっぱバグってますね~」って言われる.

4回戦(対きふわらべ)

たしかここらへんでお昼ごはんに納豆ご飯食べてたと思う. 史上初めてきふわらべが頭金打って勝つという歴史的快挙を達成する.

敗者コメントだぞっ☆

5回戦(対Easy Shogi)

デバッグしながら見てたら千日手になったのでとりあえず全敗は免れて安心するが棋譜中継だとわいの反則負けになっててまじいい?ってお気持ちになる. 後でEasy Shogi側の連続王手による千日手ということで反則勝ちに. 初勝利!やったね!

なおこれでバグと格闘するモチベーションが消え諦める.

6回戦(対BFP)

バグつぶしを諦めて落ち着いてうちのぽんこつポンコツっぷりを発揮して瞬殺されるところを見届ける.

7回戦(対A.I. AN shogi ver.1)

今度はちゃんと詰まして2勝目を上げる. やったね!

ちなみに親に詰まして勝ったって報告したときの親からのコメントです.f:id:jj1guj:20210505023734p:plain

ちくちく言葉は, やめようね笑

8回戦前

おなか空いたのでご飯を勝ってくる.

8回戦(対山田将棋)

あっけなく順当に負ける.

終結

なんかソルコフ?の関係で28位フィニッシュ, 2勝勢ではトップの成績だった.

感想

正直全敗かな~って思ってたし1勝できれば御の字だと思ってたのでまさか2勝できるとは思ってもいませんでした!!某2冠の言葉を借りれば望外の結果, 僥倖ってやつですね!今回はとりあえず動いたから就活のネタにする*7&世界ランクをもらうっていうかなり軽くて薄いモチベーション*8で本当にやりたいことの1割もできてなかったので来年はやりたいことを全部出しきった状態で出ます!!

今後の展望

とりあえず探索がバグってるのでそこを潰して強くしたいです!あと, 今日やってた2次予選の棋譜とかみてここに追いつきたいってなったのでがんばりたいです!!
うっ…院の課題…
うっ…就活…
うっ…学会発表…

*1:書かれたら書かれたでくっっっっっっっっっそよみにくいクソ記事しかでなさそう

*2:大学院入学とか春アニメチェックするので忙しかったのでね… ところで今期は86とスライム倒して300年とVivyが好きです!!

*3:完全な愚痴なんですが弊所属, めちゃくちゃ名前長いしコンピテンス?とかいう変なやつを考えながら履修組まなきゃいけなくてむちゃくちゃめんどくさくてまじでクソ

*4:月刊競技プログラミングは役に立つ案件

*5:腰痛めたの人生で初めてだった

*6:なんか2080Ti 6台くらいつなげてたらしい. すげ~

*7:将棋AI作って世界大会でて2勝しました!!って言ったらちやほやしてくんねえかなあ

*8:本当は自分より強い状態で出したかったが無理だとわかった途端こんなに軽く薄く…ウッウ…

Chokudai Contest 005参加

お久しぶりです.
9月は研究したり風邪引いたり闇落ちしたり闇堕ちしたりものすごく忙しかったです…
それはそうとChokudaiContest005に参加しました.
NyanyanHonazoの3人でOpenEsysっていうチームを組んで参加したよ.
結果は49,985,585点の141位でした!!

前日

コンテスト開催が発表されたのでSlackで参加者募集してNyanyanをつかまえる.
Chokudai Contest 003を解いてマラソンの復習をする.

当日

Honazoをつかまえる.
Chokudai Contest003で焼きなましのお勉強してめちゃくちゃ点数を上げた.

コンテスト本番

開始直後

Honazoに入力部を, Nyanyanに貪欲解の生成を書いてもらい, ぼくは得点計算を書く.
得点計算書き終わったあたりで入出力チェッカーとテストケースの存在に気づく…
問題文は最後までしっかり読みましょう.
貪欲書き上がったところで提出して17172700点ゲットする

1回目の提出直後

Nyanyanが新しい方針で貪欲実装して49985585点を獲得する.
Nyanyanすごすぎる… †貪欲のプロ† 貪欲解のtourist!!

コンテスト終了まで

いよいよ局所探索のお仕事を始める.
とりあえず初期解のうち適当に場所を選んでそこの色を適当に変え , 変えた次の場所から再度貪欲をとき直していくって方針でやろうとしたけどバグらせたままなぜか初期解から点数を落としておわっちゃった…
かなしいね…

よかったこと

・めちゃくちゃいい点取れた!!すごい!!
・今回VSCodeのlive shareっていう拡張使ったんですけど一斉に編集できてめちゃくちゃ便利だった

反省

・局所探索がうまくいかなかった.
・入出力チェッカーを使いこなすことができなかった.
・ビジュアライザほしかった.

感想

問題見たときからちょっと局所探索難しそうだなぁとは思っていたけど実際難しかった…
貪欲書いてもらっている間に自分で局所探索の実験するとかもうちょっと時間を有効活用すればよかった…
時間があるときに今回の問題使って局所探索を書いてみます

Windows10でメモ帳が使えなくなったときの対処法

メモ帳が使えなくなったので使えるように直したよ

あらましと概要

txtファイルをメモ帳で開けなくなったので調べてみたらなぜかメモ帳がアンインストールされてたので再インストール&スタートメニューに登録するところまでやりました.
なんでアンインストールされたんだろうね…

環境

Windows10 バージョン2004

解決方法

  1. 設定>アプリと機能>オプション機能にアクセスし, インストールされている機能にメモ帳があるか確認する. ある場合は3. に進む.
  2. 機能の追加をクリックし, メモ帳と書いてあるところのチェックボックスをクリックしてインストールして再起動する(再起動はひょっとしたらいらないかも…).
  3. エクスプローラーでCドライブ>Windows>System32にアクセスし, notepad.exeを探し, ショートカットを作成する.
  4. ショートカットの名前をメモ帳に変更し, Cドライブ>ProgramData>Microsoft>Windows>スタート メニュー>プログラム>Windowsアクセサリに移動させる. ProgramDataが見つからない場合, エクスプローラーの表示タブをクリックし, 隠しファイルのチェックボックスにチェックを入れると見つかるはず.

ここまでやると下のようにメモ帳が追加されます.
f:id:jj1guj:20200802163636p:plain

最後に

他にもっといい解決方法あったら教えて下さい…

参考文献

www.atmarkit.co.jp

dekiru.net