機械学習周りのプログラミング中心。 イベント情報
ポケモンバトルAI本電子書籍通販中

初代ポケモンの図鑑完成やってみた(23時間10分56秒)

背景

初代ポケモンポケットモンスター赤・緑)は3DSバーチャルコンソールで配信されているが、間もなく配信が終了してしまう。初代ポケモンは小学生の時プレイした思い出深いソフトである一方、一度も図鑑完成したことがなかった。そこで、この機会に図鑑完成させて完全クリアすることにした。

プレイ条件とゴール

  • 発売当時のゲーム体験にできるだけ近づけるため、赤と緑バージョンのみを用いる。青・ピカチュウは使用しない。
  • 図鑑完成RTAのチャートは調べない。ポケモン捕獲テクニック等の一般論は事前に調べて、自分でチャートを作る。
  • 最速を目指すものではないが、駆け足でプレイする。
  • 3DS上で赤、2DS LL上で緑をプレイ。今回のために2DS LLを購入した。
  • 自分が初めてプレイしたのは緑なので、緑側のセーブデータで図鑑完成させる。メインロム=緑、サブロム=赤。
  • 裏技について
    • ピッピ人形でのガラガラ成仏OK。ただメインロムの攻略では使わない。
    • 秘伝技を覚えたポケモンを送り込むことはOK。マサキ訪問、サントアンヌ号、サファリをカットできる。
  • 2台同時の操作はOK。実際にはかなり疲れるので、通信交換のときと、最終盤の四天王レベル上げでしかやっていない。

最速ではないが、個人的な思い出のため以下の条件を課す。

  • 緑でのシナリオクリアでは、最初にヒトカゲを選び、ピッピ人形でのシナリオカットはしない。

しんどそうなポイント

  • 伝説系の捕獲
    • ミュウツーLV70など、手持ちのポケモンより圧倒的に強いポケモンを捕獲する必要がある
    • しかし意外と簡単。技はランダムなので、弱い技で隙ができる。ハナダの洞窟で簡単につかまるモルフォンLV49が有効。モルフォンで初手さいみんじゅつ、その後スピーダーとヨクアタールで先制でさいみんじゅつが当たるようにすれば、後はモンスターボール連打でOK。弱らせる必要なし。初代は目覚めたターンに技が出せないので、最初のセットアップさえ成功すれば反撃の可能性はない。
  • サファリゾーンの捕獲
    • 出現しづらくつかまりにくいポケモン:ガルーラ、ケンタロス、ストライク、カイロス
    • ラッキーは、ハナダの洞窟で簡単につかまるのでそちらで。ストライク、カイロスはゲームコーナーの景品でも得られる。ガルーラ・ケンタロスだけはサファリゾーンで粘るしかない。
    • スプレーのために先頭ポケモンのレベルを調整し、サファリゾーンの該当エリアでセーブ。起動したらスプレーを使ってとにかく歩き回って捕獲を試みる。歩数切れになったらリセット。
  • 高レベル進化のポケモン
    • 一番大変なのはカイリューミニリュウLV15を入手し、LV55まで上げる必要がある。他のポケモンのレベル上げに常に帯同させたうえで最後に残る前提で、LV40程度まで上げて不思議な飴を使う。
    • カブト・オムスターもLV30からLV40まで上げる必要あり。
    • 御三家はLV5からLV36まで上げる必要あり。サブロム攻略の最初にメインロムに送り込んで最終進化系まで四天王でレベル上げして、サブロムに返す。
    • 学習装置について
      • セキチク右のゲートで、図鑑登録50匹以上でもらえる。
      • 学習装置が手持ちの道具にある時、ポケモンを倒したときにもらえる経験値Xが、以下の要領で分配される。Xは相手ポケモンの種族やレベルで決まり、こちらのレベルには依存しない。
      • 戦闘要員1匹、非戦闘要員1匹の時、戦闘要員は(3/4)X、非戦闘要員は(1/4)Xもらえる。
      • 戦闘要員1匹、非戦闘要員5匹の時、戦闘要員は(7/12)X、非戦闘要員は(1/12)Xもらえる。
      • 非戦闘要員をできるだけ多く持っていたほうが効率は良いのだが、1匹ずつがもらった経験値がすべて別個のメッセージで表示され、ボタン連打で送る必要があるため面倒な面もある。
      • 非戦闘要員を瀕死にしても、割り算の頭数は減らないので意味なし。
    • 親が自分以外のポケモンは経験値1.5倍。高レベル進化ポケモンのレベル上げはできるだけ通信交換して別のロムで行う。
  • イーブイの取得
    • 3種類の進化先があるので、タマムシシティでイーブイをもらうまでのシナリオを3回攻略する必要がある
    • サブロムを1回タマムシまで攻略したのち、データを消して2回目を攻略。
  • ポリゴンの取得
    • 緑でゲームコーナーのコイン6500枚=13万円。コインは50枚1000円。
    • 四天王一周の賞金は29799円。5週すればOK。
    • 回復薬等に若干コストはかかるものの、四天王周回は5回じゃ済まないのでお金がネックにはならなかった。
  • 四天王周回

事前準備

大まかな進行チャートと、各ポケモンをどこで捕まえるか、どのレベルで進化するかの表を用意。表には捕獲済みかどうかのチェックをつけられるようにした。

攻略チャートの概略(緑=G、赤=R)

やること

以下、緑バージョンで

初期化、ヒトカゲ選択

ヒトカゲコラッタで進める

オニスズメを道中捕まえておき、クチバでカモネギと交換、いあいぎり・そらをとぶ要員にする

11番(クチバ東)でスリープ捕獲、育成

セキチクでいいつりざおもらい、釣りでトサキントなみのり覚えさせる

クチバですごいつりざお、クラブを捕獲していあいぎり・なみのりかいりき要員にする

ふたごじま1Fでヒトデマン捕獲。スターミーに進化させ、なみのりれいとうビーム(デパート屋上おいしいみず交換)覚えさせる

こいつらで殿堂入りを目指す。簡単につかまるポケモンは捕まえる。

タマムシデパートでスピーダー10個、ヨクアタール10個、ハナダでモンスターボール買えるだけ買う

花田の洞窟1Fで、モルフォンLV49捕獲。

ミュウツーを捕獲、初手サイキネさえされなければモルフォンで眠らせられる

サンダー捕獲、技覚えさせる。ドリルくちばし、10まんボルト(マシン)、すてみタックル(マシン10、タマムシアジトB3)、そらをとぶ

簡単に捕まるポケモンを捕まえて50匹まで進めて、学習装置もらう

以下、赤バージョンで

初期化、ゼニガメ選択

ゼニガメをGに送って四天王でレベル上げ(サンダーと2匹なら2周)、なみのりかいりき覚えさせる

カメックスになったらRに戻す、秘伝要員カモネギと一緒に送り込む

かいのかせき取得

イーブイ取得

エビワラー取得

タマムシジム・セキチクジム攻略

モルフォン送り込み。タマムシデパートでスピーダー1個、ヨクアタール1個。ハナダでモンスターボール買えるだけ買う

サンダー捕獲、技覚えさせる。ドリルくちばし、10まんボルト(マシン)、すてみタックル(マシン10、タマムシアジトB3)、そらをとぶ

サンダーに手持ちの飴をつぎこむ

かいのかせき復元

サファリですごいつりざおでミニリュウを釣る

ポケモンをGに転送

初期化、フシギダネ選択

フシギダネをGに送って四天王でレベル上げ(サンダーと2匹で)

フシギバナの技:はっぱカッター、のしかかり(技マシン)

フシギバナになったらRに戻す、秘伝要員カモネギ、クラブと一緒に送り込む

甲羅の化石取得

ハナダでスプレー買って、クチバジム攻略、自転車取得の上イワヤマ攻略

イーブイ取得

Rで取得すべきポケモンを順次捕まえる

Gに送り込む 以下、緑バージョンで

捕獲をどんどん進める、まずサファリから。

最後にレベル上げ

実際の進行

  • 0:00 G攻略開始。
  • 7:12 初回殿堂入り。スターミーにドーピングでごり押しした。シナリオ攻略RTAの倍の4時間ぐらいで済むと思っていたが、行き当たりばったりで進めると大幅に時間がかかった。
  • 7:52 ミュウツー捕獲。
  • 8:05 サンダー捕獲。サブロムを開始しゼニガメをメインロムに送ってレベル上げ開始。
  • 9:15 カメックスへの進化完了。サブロムに送り返してシナリオ攻略開始。サンダーのレベルがまだ低いのと四天王周回に慣れていないため1時間もかかった。
  • 11:05 サブロムでキョウを倒し、サンダー捕獲。
  • 11:44 イーブイミニリュウ等入手し、サブロムからメインロムへの転送完了。以降、サブロムで捕獲したサンダーでメインロムの四天王周回を行う。サブロムのデータを消して二週目(フシギダネ選択)開始。
  • 13:13 フシギバナへの進化完了。サブロムに周目のシナリオ攻略開始。
  • 14:57 サブロムでポケモン屋敷まで攻略。ストライク以外のサブロム(赤)で捕まえるべきポケモンの捕獲完了。メインロムで各地を回って捕獲進める。
  • 16:52 サファリ開始。赤でサファリに1回行っただけでケンタロスが手に入った。
  • 18:04 ガルーラ入手。ガルーラだけで1時間かかった。ストライクはゲームコーナーのコインでとる方針に変更。サブロムで四天王周回するため、シナリオ攻略を再開。サブロムで学習装置を取るため、図鑑埋めポケモンの転送等を行う。
  • 20:02 サブロムでセキエイ高原到着。以後、サブロムでは四天王周回でミニリュウのレベル上げ、メインロムでは四天王周回でその他のポケモンのレベル上げを並行して行う。
  • 21:55 ハクリューがLV43に達する。残りのLV55までは、メインロム、サブロムに残った不思議な飴で行うこととした。
  • 22:15 サブロムのゲーセンでストライクを取得。コイン5500枚を引き換えるだけでボタン連打に8分を要した。
  • 22:32 サブロムからポケモンを転送し、サブロム側作業を終了。
  • 22:54 メインロムのゲーセンでケーシィ、カイロス、ポリゴンを取得。コイン9120枚の引き換えにボタン連打13分。
  • 23:02 自宅でピカチュウライチュウに進化させ、図鑑完成。ここからあえてタマムシシティのゲームフリークまで歩いていく。
  • 23:10 表彰状を表示。ゲーム終了。

記録はストップウォッチ上で23時間10分56秒。休憩中は止めている。

Tips

  • フラッシュ
    • イワヤマトンネルは1回通過するだけでいいので取得不要。攻略サイトのマップを見ながら進めばよい。
  • データ初期化
    • タイトル画面で上+セレクト+B
  • ヤマブキジム
    • 左上、左下、左下
    • 戻るとき左上、右上、右下
  • つきのいし
    • 2番道路(いあいぎり右側)
    • おつきみやま1F左上
    • おつきみやまB2F、化石を選ぶ場所の手前、右側にある行き止まりの壁
    • ポケモン屋敷1F、入口から入ってすぐ、右側の下から5番目のブロック
  • 不思議な飴
    • オツキミ山1F右下
    • ハナダシティ、バッジおじさんの裏庭
    • サントアンヌ2F、左から4番目の部屋
    • タマムシアジトB3F、迷路エリアの右上
    • ポケモンタワー6F道中
    • 無人発電所、右上の部屋の右側
    • シルフビル10F、左下の部屋
    • ポケモンやしき、B1道中1個、秘密の鍵がある部屋の左上隠し1個
    • チャンピオンロード1F、右上で岩を上に押し込む

困った点

  • キクコ戦、最初のゲンガーがあやしいひかり、さいみんじゅつをしてくる。一発で倒せないので混乱自傷で泥沼に陥ることがあった。
  • ポケモンがどのボックスにいるのかわからず、探すのに手間取った。
  • サブロムで学習装置をもらうのに、図鑑登録50匹が必要。送り込むポケモンの選定に手間取った。交換自体も1匹1分+開始終了で時間がかかるので最適化ポイントになる。
    • 時間のかかる交換を行って図鑑埋めをしてまで、サブロムでの四天王周回のついでにレベル上げをするのが合理的かどうか疑問が残る。単純にゲームコーナー用の金稼ぎだけを目的に周回するほうが良かった可能性あり。

より速くクリアするには

  • 初回シナリオ攻略でRTAチャートを用いる。2時間台でクリア可能。
    • ニドキングでつのドリルを連打するチャート。
    • 攻略用ポケモンに飴を使うのはもったいないかも。
    • 伝説ポケモンの消滅など、取り返しのつかないことは起こらない。
    • スプレーが使えないお月見山でピッピが出たときに捕獲するとか、再訪問に手間がかかるポケモンタワー上部でカラカラを探すとかの改変は有用そう。
  • 2台同時攻略。最適化はかなり難しいが。
  • サブロムで殿堂入りする必要はあるか?
    • 赤でしか手に入らないポケモンは、ポケモン屋敷まで行けば十分で、ジムはセキチクジムまで攻略すれば十分。
    • 殿堂入りのメリット
      • 2つのロムで四天王周回をして、ミニリュウ等のレベル上げに活用できる。
      • 赤のサファリゾーン限定のストライクを、ゲームコーナーのコイン5500枚で確定入手できる。(殿堂入りそのものが条件ではないが、金稼ぎの手段が事実上四天王周回しかないので)
    • 殿堂入りのデメリット
      • 時間がかかる。ストライクの入手だけなら、サファリゾーンで粘るほうが速い可能性がある。

青バージョンを使うと?

  • 赤青だけ、緑青だけでは入手できないポケモンがいるので、赤緑青の3つを併用することになる。
  • 赤緑ではサファリで粘るしかなかったガルーラ・ケンタロスがゲーム内交換で入手可能(サイドンペルシアンと交換)。
    • イーブイのためにシナリオを3回プレイする必要があるので、赤を2回よりは、赤と青1回ずつのほうがこの点でメリット。

参考資料

今回自作した、どのポケモンをどこで捕まえるべきかという表はこちら。pokemon_green_zukan_kansei_hokaku_shudan.xlsx

感想

初代ポケモン(緑)を買ったのは1997年11月ごろだが、図鑑完成させたことはなかった。約8950日を経て図鑑完成ができ、未練をなくすことができてほっとしている。 チャートづくりも楽しめた。どこで何を捕まえるのかを決める過程が作戦の立て甲斐があった。 サファリゾーンを除いては捕獲はスムーズだった。作戦の幅が狭い初代だが、ちゃんとテクニックを知ればポケモンシリーズの中でも簡単な部類だった。 本来は2日で完結させるつもりが想定以上の時間がかかり、3日に分割することとなってしまった。RTAテクニックを使わず普通のシナリオ攻略をするという方法をとった結果4時間ほどのロスとなっている。 プレイ途中の作戦ミスとして、サブロムでストライクがつかまらず、四天王周回してお金で買う方針に途中で切り替えたのはよくなかった可能性が高い。 面白かったので、金銀でもやってみたい。

第32回世界コンピュータ将棋選手権の結果(2022/05/04)

2022年5月3日~5日にかけて開催された第32回世界コンピュータ将棋選手権に参加ソフト「ねね将棋」で参加しました。

今回のねね将棋は昨年12月から作り始めた、iPad上で動作する新しいソフトです。しかしながら昨年はdlshogiを改造してPC上で動かしたものを「ねね将棋」として出したのでルール上はその後継として認識されています。昨年の順位の関係で二次予選シードとして出場しました。二次予選の結果は1勝7敗1分け(千日手)で27位(28チーム中)となりました。

ソフトの内容自体はアピール文書の通りです。当日の変更や相手による作戦分岐はありません。工夫点は過去の記事シリーズを参照してください。

select766.hatenablog.com

良かった点

iPad単独で動いて、Neural Engineを使う将棋ソフトというコンセプトを見せることができました。

対局に使うハードウェアはこれだけでした。マシンの軽さや安さに賞があったら受賞できたと思います。

設営風景

悪かった点

実力が均衡するソフトがなく、有意義な棋譜になりませんでした。現代の有力ソフトをPCで動かしたものに棋力が大きく劣っているため、ライブラリ勢には勝ち目がありません。一次予選にしても、レート1000台~4000台の極端な差があるチームが戦うので、強さが同じぐらいのソフトが当たる回数はかなり少ないです。人間の100m走で10秒の選手と20秒の選手が同じ舞台に上がることはまずありませんが、コンピュータ将棋では容易に起こるので難しいですね。

感想

久しぶりのオフライン会場での参加ができて、開発者の方々と会えて楽しかったです。ただ、オンライン参加の方のほうが多く、会場にいながらZoomに参加してそちらとも交流するというのは流石に難しいように感じました。オフライン、Slack、Zoom、公式YouTube、非公式YouTubeとチェックすべき箇所が分散してしまって、YouTube配信を見てたらZoomで呼ばれていることに気づかないなどの不便が生じました。コロナが収束したとしても遠方の参加者にとってオンラインは有力な手段なので、今後も模索が続いていくものと思います。

運営の方々、対局してくださった方々、ありがとうございました。

iPadのNeural Engineで将棋AI part13 細かい話

他の記事で書きそびれた細かいテクニック等をまとめておきます。

CSAプロトコルでの対局テスト

  • shogi-server shogi-server をサーバとして使います。
  • ruby 2.7.5をインストールする必要がありますが、それ以外は最新のMacで問題ありませんでした。
  • 対戦相手は将棋所でサーバ通信対局機能を用いて、lesserkaiなどを投入しました。
  • ponder機能の確認は少々面倒です。lesserkaiはすぐ指すので確かめられず、やねうら王などの著名なソフトは強すぎます。負けるのを承知でやねうら王などでponderが動作することをローカルで確認しつつ、floodgateで動作を確認した形です。
    • 自分のソフトが決定的な挙動をする場合に、lesserkaiを相手にすると全く同じ進行になる場合がよくありますが、たまに違う進行になる場合もあり動作確認の相手としては不便に感じました。決定的に動くモードとあえてランダム要素を入れて様々な状況を試せるモード、ponder確認のためにランダムな時間待ってくれる機能等がついた対戦相手を作ってもいいかもしれません。

DNNモデル

  • 最初は、「強い将棋ソフトの創りかた」のサンプルコードのデフォルトパラメータで学習できる、10ブロック(20層)192チャンネルを試していました。バッチサイズ16で1000samples/sec程度でした。
  • 処理時間でDNN評価に90%程度、それ以外の合法手生成や探索木の処理が10%程度でした。
  • 合法手生成等の高速化に時間を割けないので、DNN側を重くしたほうが強いのではないかと思い、dlshogi本家で使われているといわれる15ブロック(30層)224チャンネルのモデルを学習しなおしました。バッチサイズ16で600samples/sec程度でした。
  • 探索ノード数が少ない状況でバッチサイズを大きくすると変な探索結果になる場合があったため、最終的にバッチサイズ1で動作させることにしました。探索部含めて、およそ330NPS(1秒当たり330局面についてDNNを評価)となりました。

思考時間

10秒に固定して試作し、そのまま変更していません。時間が足りない場合はそれに応じて思考時間が短くなります。10秒経過したら探索を止めて、その後最善手の計算と送信が入るのでサーバには11秒と計測される場合がほとんどでした。

定跡

ソフトウェア実装はSwiftで新規に書きましたが、評価関数・探索アルゴリズムはdlshogiと類似しており、棋風としてはdlshogiやそのライブラリを用いたソフトの探索が浅い状態のものとなることが予想されました。棋譜としてありきたりだとつまらないと思い、初手だけランダムにすることにしました。初手では2六歩、7六歩および悪手を除外した20通りの手からランダムに指すこととしました。悪手を除いた初手のリストは、ponanzaで使われた初手のリストに準拠しています。 「第2期電王戦バージョンのponanzaが指さない初手は ▲8六歩、▲9八香、▲6八金、▲5八金左、▲4八飛、▲3八飛、▲1八飛、▲1八香の8通り。 それ以外の22通りの初手を指す。」 参考: https://twitter.com/floodgate_fan/status/851019316522762240

後手番になった場合も定番の3四歩、8四歩以外にしようと思いましたが、先手の初手によっては悪手となる手があると考えられます。そのため、1手目それぞれに対して、2手目の全候補手を指した場合の評価値を計算しました。

1手目、2手目の組み合わせによる評価値(先手から見たもの)

角頭の歩を突く△2四歩はよくないですが、初手が▲2六歩の場合は特に悪い評価値になるということがわかります。この表に従い、各初手ごとに、3四歩、8四歩以外で評価値上位3手を等確率に選びました。結論は以下の表のようになります。

2手目としてランダムに選ぶ手の候補

3手目以降は定跡なしです。

棋力と今後

floodgateで対局した結果、レート基準となるgikou2_1cとほぼ同等の3300でした。 iPadでDNNを使った場合の棋力を単純に推測するなら、モデルの実行速度だけ検証し、PC上でdlshogiの探索ノード数をそれに合わせて動作させれば十分なのですが、iPadで実際に動くものが作れるかという検証を最後まで行うことができました。有線LANの接続や冷却などの課題はスムーズに解消でき、慣れないSwiftと格闘するのが主に苦労する点でした。

レート3700の"Kristallweizen-Core2Duo-P7450"が文字通りの内容、つまり2019年のNNUE型評価関数Kristallweizenと2009年発売のノートパソコン向けの2コアのCPU、Core2Duo-P7450の組み合わせだとすると2021年発売のiPadのCPUがこれに劣るとは考えにくいです。つまり、CPUで深く探索するタイプのソフトを実装したほうが強いと思われます。dlshogiでは即詰みについては探索が入っていますが、見落としによって形勢が悪化するような状況まではケアできず、300NPS程度では評価関数の精度が少々向上しても見落としを避けられないと考えています。 ハードウェアをiPadに固定した場合で最強を目指すなら、CPUでの探索をメインとして、GPU/Neural Engineを補助的に使うような仕組みが良いと考えられます。合議や、WCSC27のPonanza Chainerのように探索の順序のヒントとして使うということが考えられます。

今回はUI、通信部、探索部それぞれ1スレッドで動作させるという形でしたが、探索内部で複数スレッドを密に連携させるとなるとSwiftはつらいかもしれません。C言語にあるvolatileなどの機能がない C volatile equivalent | Apple Developer Forums ことや、インラインアセンブラが使えないなどの制約があります。デバッグ中にも、複数スレッドから局面データを操作しようとするとSwift言語からは明示的に使っていないmalloc関連のエラーで止まってしまうという事象がありました。現実的にはコア部分はC++で実装し、UI等はSwiftで実装するというのが妥当と思われます。技術的に面白そうな課題としては、AMD64SIMD命令で書かれた探索部をARMの命令に置き換える部分でしょうか。最近のApple端末のマルチコアCPUは、high-performance coreとhigh-efficiency coreという非対称なコアが搭載されているため、うまく連携できるかどうかも検証する必要があります。 Appleの開発環境にはまだまだ慣れないのですが、やねうら王を単純に移植してどの程度強くなるかをいずれ検証してみたいです。

まずは明日の選手権本番を楽しみたいと思います。

iPadのNeural Engineで将棋AI part12 読み筋表示

独自のGUIを開発するため、レイアウトに自由度があります。ただ1行の読み筋を出すのではなく、複数の読み筋やその評価値を表示して、より面白い表示を試みました。

読み筋表示

動画だとこんな感じで動きます。

次のような事項を表示したいと思いました。

  • 自分の候補手だけでなく、相手の応手も複数候補表示する
  • 候補手それぞれの勝率だけでなく、その局面の複雑さを表示する
  • 探索が進むことで候補手が入れ替わる様子を表示する

これを実現する実装は次のようにしました。

  • 相手の応手の表示
    • 自分の候補手を上位3つ、それぞれに対し、相手の応手3つを表示するようにした
    • 十手以上先の候補まで表示するようなソフトも多いが、表示が頻繁に切り替わる状況では読み取れない割に場所を取るため、3手先までとした
  • 局面の複雑さの表示
    • 勝率の横(±の後ろ)に、その標準偏差を表示するようにし、これを複雑さの指標とした
    • MCTSでの探索中に、末端局面の勝率を親ノードにバックアップする。その際に勝率の合計だけでなく、勝率の二乗の合計を保存する変数を追加し、分散を計算する公式によって標準偏差を計算
    • 序盤は標準偏差が小さく、中盤は大きくなる傾向を読み取ることができる
  • 候補手の入れ替わり
    • MCTSにおける指し手の決定は、候補手ごとの探索回数が最大のものとなる(勝率最大とは限らない)
    • 探索回数を棒グラフで表示することで、2番目以降の候補手が伸びていって入れ替わるという視覚化ができるはず
    • 総探索回数が1000, 10000, 100000...に達するたびに横軸のスケールを変えて画面内に収まるようにした。スケールがわかるよう、グラフの色を青、緑、オレンジ、赤と変化させるようにした
    • 実装してみたものの、思考時間10秒程度ではわかりやすい入れ替わりは見られなかった

動かしてみた感触

  • 棒グラフにより、2番目以降の指し手がどの程度有望なのかが一目でわかる。
  • 候補の時系列変化については、思考時間10秒程度ではわかりづらかった。盤上に矢印等で指し手を表示すると、よりわかりやすいかもしれない。

どうにかiPad単独で動く将棋ソフトが実現できました。次回は記事になっていない小さなトピックをまとめた記事を書いて大会前の総括にしたいと思います。

iPadのNeural Engineで将棋AI part11 画面表示の要件

将棋所なしのiPad単独で対局ができるようにするため、CSAプロトコルの実装に引き続き独自のGUIによる局面表示を実装します。

実は大会ルールで画面表示に関する要件が定められており、これに準拠した設計を行う必要があります。

第32回世界コンピュータ将棋選手権

ルールのうち表示に関する部分を抜粋し、対策を示します。

  • 一 任意の局面・手番・残り時間からの将棋の対局の開始と継続。
    • 過去数回の大会で発生事例を見たことがなく、実装が面倒なため将棋所+USIで実現する。
  • 二 任意の時点での対局中断。
    • サーバから中断メッセージ(#CHUDAN)が来れば停止する。発生することが極めて稀であり、同一TCPコネクション上で再開することまでは求められていないと考える。再開は将棋所+USIで実現する。
  • 三 対局中の現在局面の表示。テキストでも良い。
    • 指し手を受信するたびにUI上で局面表示を更新する。
  • 四 第24条の規定による、1手毎の消費時間の計測、及び累計消費時間の画面への表示。
    • 24条で、LAN対戦の場合はサーバが消費時間を計測することになっている。計測された1手の消費時間は指し手とともにクライアントに送られる。1手ごとの消費時間はこれをそのまま表示すれば良い。累積消費時間は送信されないため、クライアント側で合計を計算して表示する。手入力対戦の場合は自分で計測する必要があるが、将棋所+USIに任せる。
  • 五 1手毎の指し手と消費時間の記録。対局中断時も、そこまでのすべての指し手と消費時間を取り出せなければならない。
    • サーバから送られた指し手と1手ごとの消費時間を画面に表示する。中断等でも表示を続けるため、コネクションが切れた際に消去するのではなく、次の対局のAGREEを送る時点で消去する。できれば、ファイルにも保存する(iPadOSのため取り出すインターフェースが別途必要となる)。
  • 六 CSA サーバプロトコル ver.1.2.1 に基づく、LAN による対局。
    • 前回実装した。
  • 七 相手の指し手の手入力による対局。
    • 将棋所+USIで実現。
  • 第9条 参加プログラムは、次の各号に掲げる機能を持つことが推奨される。但し、機能を持たないことによって不利になることはない。
  • 一 LAN による通信で送受信した文字列の必要に応じた表示。

通常の対局では不要な機能は将棋所に任せることにして、以上の機能を実装しました。累積消費時間が必須というのはルールを読まないと気付かないので要注意です。

以下のような画面になりました。

ねね将棋のスクリーンショット

細かいことはソースコードを読んでいただくとして、実装のポイントを示します。

  • UIライブラリはSwift標準のSwiftUI
    • UIの階層構造を構築する手法はReactに似ているのであまり違和感はありませんでした。
    • iPadピクセルサイズ決め打ちで作ってしまいました。画面サイズ変化への対応はCSSとは結構違って習得が大変だったため見送りました。
  • 画面
    • 大きく分けて2つの画面レイアウトがあり、対局前の接続設定と、対局中の局面表示です。接続設定はテキストボックスを並べた最低限のものです。以下では対局中の画面を説明します。
  • 主なUI部品
    • 盤面
    • 評価値バー
      • 対局者名と、その時点で最新の評価値を表示
    • 評価値グラフ
      • 評価値の履歴を表示
    • 読み筋表示
      • 独自の表示を考えたので、次回解説
    • 指し手の履歴
      • 指し手のほかに1手の消費時間、合計消費時間、評価値(自分の手番のみ)
  • 詳細な指し手情報
    • 探索部では、「移動元、移動先、成りかどうか」という情報で指し手を管理していますが、「▲7六歩」のような文字列を表示するには移動する駒の情報が不足しています。
    • 表示のためのDetailedMoveという構造体を定義しました。以下の情報を含んでいます。
      • 特殊な指し手(投了、入玉宣言)
      • 移動元(または駒台)
      • 移動先
      • 手番
      • 移動前の駒の種類
      • 移動後の駒の種類(成りがある場合に移動前と変わる)
      • 成りかどうか
      • 駒打ちかどうか
    • これらの情報で、「▲7六歩(77)」というような移動元をカッコで示す将棋所と同等の表示ができます。「同歩」のような前の指し手に依存する情報や、「5八金左」のような他の駒との関係が絡む情報は含められていません。
  • モジュール間の通信
    • UIから通信部、通信部から思考部を起動する。
    • 局面・指し手履歴情報は通信部からUIへ、読み筋情報は思考部からUIへ送信。
  • 画像アセット
    • 将棋盤や駒の画像も自分で作りました。
    • Photoshopで作成しました。
    • レイアウトで使う画面横幅は1080pxなのでそれで作ってしまったのですが、物理ピクセル数は2160pxあり、それに合わせてアセットは作るべきでした。実際に画面に出してみると、画質が荒い感じになってしまいました。

iPadのNeural Engineで将棋AI part10 CSAプロトコルに対応する

前回まででiPadで動作する将棋エンジンのコアはできましたが、USIプロトコルMac上で動作している将棋所と通信する仕様となっており、iPad単独では世界コンピュータ将棋選手権やfloodgateでの対局がまだできませんでした。選手権等での対局にはCSAプロトコルが用いられているため、これを実装する必要があります。

CSAプロトコルの説明は以下のリンクから参照できます。今回は最新のバージョン1.2.1に対応します。

CSA通信プロトコル

CSAプロトコルは汎用性が高く、駒落ち対局などの特殊な条件にも対応しています。CSAプロトコル全体を実装するのは大変なので、選手権とfloodgateで必要となる最低限の機能だけを実装します。

最低限必要なステップは以下の通りになります。

  • TCPでサーバに接続する
  • LOGIN送る
  • 相手が決まると、対局条件が来る
    • "Your_Turn:+"で自分が先手か後手かを知る
    • "END Game_Summary"を待つ
  • "AGREE"を送る
  • "START"を待つ
    • これが来たら対局開始、時間計測開始
    • 先手番の時、STARTを待たずに初手を送る実装をするとトラブルにつながるケースもあるようで注意
  • 手番なら、思考して手を返す ("+7776FU")
  • サーバからの指し手(自分、相手両方の指し手)を待つ("+7776FU,T12")
    • 相手が投了すれば"%TORYO,T4"など
  • 指し手によって対局が終わる場合、指し手の次の行で、"#SENNICHITE"や"#WIN"などが来る
    • "#ILLEGAL_MOVE"の場合があり、その場合直前の手の表記は間違っている可能性がある(厳格に対処するのは大変なので気にしない)
    • 指し手の行が来た時点で思考に入るが、対局終了のメッセージが来たらそれを打ち切って終了画面に移行することが望ましい(できなくても負けにはならないと思うが)
    • LOGOUTを送るほうがより適切
  • floodgateで連続対局したい場合は、TCP接続が切れたら新しく接続しなおして、LOGINから通信をやり直す実装が必要。
    • floodgateでは、拡張モードを用いることでTCP接続を切らずに連続対局したり読み筋を送ったりすることが可能。しかし選手権のサーバでは対応していないため、拡張モードは実装しない。

CSAプロトコルのちょっと困る・USIより面倒なポイント

  • 千日手が成立する手と、指し手の後に千日手成立のメッセージが分かれて送られてくる
    • 手が来た時点で思考を始めてしまうため、それを止める機構を実装しないと連続対局に支障がある(手動で再起動する分には問題ないが)
  • 指し手の表記("+2726FU")に駒の種類や手番が含まれている
    • USI形式での指し手には「移動元、移動先」が含まれており、思考部でもこれだけの情報で十分であるため指し手を表すオブジェクトに駒の種類は含まない。CSAプロトコル用の指し手文字列を生成するためには、局面情報から移動元にある駒の種類を取り出す必要がある。局面情報の管理手段をUSIと変える必要が生じる。
    • 思考部とは別に、通信部側で現局面を管理し、局面クラスのインスタンスメソッドとして"parseCSA"を実装して指し手表現を変換するようにした。
  • 持ち時間の管理をクライアント側で行う必要がある。
    • 送られてくるのは指し手ごとの消費時間であり、フィッシャールールにおける加算などを加味して残り時間を計算する機能が必要。
    • プロトコルで流れてくる持ち時間に関するルールは解釈せず、大会のルールに準拠した時間(初期持ち時間、1手ごとの加算時間)をGUI上で入力する仕様とした。
  • 通信をkeepaliveする必要がある。
    • CSAプロトコル特有の話ではないのですが、インターネット経由でTCP接続を行う場合、数分間通信がないと接続が切れてしまう場合があります。
    • 対局相手が長考している場合、送受信できるメッセージがないので接続が切れる恐れがあります。
    • CSAプロトコルでは、これに対応するためこちらの手番でない場合でも空行(LF)を送ることは許可されていますが、直前の送信より30秒以内に送ると反則になる場合があります。そのため、タイマーを用いて前回の送信から30秒以上経過したら空行を送るという実装が必要です。

これらの実装をして、CSAプロトコルでfloodgateに接続してiPad単独での対局が可能になりました。ただし、選手権のルールでは画面に最低限表示すべき内容が規定されており、将棋所を使うことで自動的に満たされていた要件を独自に実装する必要があります。次回は画面について記事にします。

iPadのNeural Engineで将棋AI part09 Swiftで将棋エンジンを書く

前回記事から1.5か月空いてしまいましたが地道に対局エンジンのコア部分を開発していました。本記事までの実装をして、選手権の練習を1つの目的として開催された「電竜戦さくらリーグ2022」に参加し、B級で18チーム中7位(ソフト名 ねね将棋)となりました。

Swift言語初心者なので実装手段に悩みつつ、盤面表現、合法手生成から始めてMCTSの実装まで進めました。ソースコードを公開しています。

github.com

実装順序

各ステップの成果が確認しやすいように、次のような順序で実装を進めました。

  • USI通信
    • 盤面は理解せず、初手で76歩を返すだけ。
  • 盤面表現・合法手生成
  • ランダムプレイヤー
    • USI通信で受け取った局面に対して合法手を生成し、そのうちランダムなものを選択して出力する。これで対局が最低限成立する。
  • DNNの実行・入出力の生成
    • 評価関数となるDNNを組み込み、盤面から入力となる特徴量および各合法手に対応する出力ラベルの生成を行う
  • 方策関数だけで指すプレイヤー
    • USI通信で受け取った局面をDNNに与えて、出力の方策が最大となる手を選択して出力する。意味のある指し手が出せるようになる。
  • MCTS実装
    • 探索を行う
    • 一定の回数探索したら終了する(経過時間で探索を打ち切る機能は後回し)
  • 接続先を指定するUI
    • Mac上のシミュレータで動かすときは、将棋所へのTCP接続先が127.0.0.1固定でよかったが、iPad実機で動かすにあたりMacIPアドレスを手入力するUIを追加。
  • 時間制御
    • USIで与えられた残り時間をもとに、デフォルトでは10秒、残り時間が12秒以下の時は残り時間-2秒だけ思考するようにした(2秒は思考を打ち切ってから指し手をネットワークで送信し終えるための予備の時間)
    • タイマー用のスレッドを作成
    • 局面の複雑さに応じた制御は未実装
  • ponder機能
    • 相手の手番中に思考するponder機能を実装する。思考をしながら相手の手が来るのを待機する必要がある。そのため、goコマンドを受け取る通信スレッドでそのまま思考するのではなく、別スレッドで思考する機構を実装。
  • バグ取り

実装方針

  • 合法手生成は、2017年にC++Python複合で自前実装したものを移植。
    • テストケースもあったのでテストを実施。
    • 簡単に書けることを重視しており、速度が遅いため詰み探索などを実装することが困難
    • 経路依存(=千日手)のテストケースはなかったのでテストできていない。
    • 入玉宣言、千日手判定はバグ取りのフェーズで追加した。(数局面確認しただけでまともにテストできていない)
  • MCTSの実装は「強い将棋ソフトの創りかた」を参考にSwiftで実装しやすいようにデータの取り回し方等を変更。
  • 探索とDNN評価は同じスレッドで実行。
    • DNN評価のコストが80~90%程度を占めるため別スレッドにしても得られるメリットはわずか。
    • 詰み探索を搭載しようと思うと分ける必要が生じてくる。
  • 評価関数は、「強い将棋ソフトの創りかた」の学習コードでデフォルトで学習される10ブロック192チャンネルのものを当初利用していたが、本家で使われている15ブロック224チャンネルのものを自前で学習して利用。
    • 探索部の速度があまりよくないので、できるだけ評価関数が重いほうが得と考えた。

Swiftテクニック

defer文で、スコープを抜けるときに局面を戻す

再帰的な探索で、一手進めた後関数の最後で元に戻すという処理が生じる。Swiftでは、defer { position.undoMove() } という記述で、関数などのスコープを抜けるときに特定の処理を実行できる。途中にreturnがあるような場合でも実行されるため便利。

思考と探索スレッドの分離

DispatchQueueにより、クロージャをそのキューに紐づいた特定のスレッドで実行できる。別のスレッドで特定の処理をさせるという記述が容易で、しかも同じDispatchQueueに対する処理は同時に走らないのでデータ構造を壊す恐れがない(同時に走るかどうかはDispatchQueueのオプション次第)。思考用、通信用でそれぞれDispatchQueueを持つことでスレッドの分離を実現。

具体的な実装はこのあたりに。

https://github.com/select766/NeneShogiSwift/blob/c64767b53ca3092297a7f30cbc35a00924753987/NeneShogiSwift/USIClient.swift#L175

ハマったところ

メモリを大量に食う

探索が終了するまで、途中で確保したメモリが解放されず1GB以上消費し、クラッシュするという問題が生じた。Swiftは参照カウント式のGCなので、参照が切れればその場で開放されるはずなのだが、解放されないメモリもある模様。 autoreleasepoolというメソッドを介して1回の探索を呼び出すようにすれば、そのメソッドが終了するときにメモリが解放されることが分かった。 https://github.com/select766/NeneShogiSwift/blob/c64767b53ca3092297a7f30cbc35a00924753987/NeneShogiSwift/MCTSPlayer.swift#L362 入門書にこのメソッドのことは書かれておらず、「CoreML memory leak」などで調べるうちに判明した。

UCB値の計算ミス

探索中に子ノードを選択する際に利用するUCB値の計算で、sqrt(moveCount)/(1+childMoveCount)とすべきところをsqrt(moveCount/(1+childMoveCount))と書いてしまった。 バグっている状態でもそれなりに動作するのが厄介で、floodgateでレート2200程度だった。探索速度が低いしそんなものかと思って気にしていなかったのだが、dlshogiのブログで、dlshogiのモデル(サイズは不明)でたった4ノード読んだだけでレート2556と書かれていた。数千ノード探索しているのにそれより弱いというのはさすがに何か問題があると思い調べることにした。python-dlshogi2を改造し、

  • ねね将棋に組み込んだものと同じ評価関数を使う
  • 探索ノード数を固定
  • 詰み探索、過去の探索ノードの再利用機能を削除し、ねね将棋と同じ探索条件にする
  • ねね将棋側は、DNNの誤差が大きくなるNeural EngineではなくCPUで評価するモードに変更

ことにより、探索結果が同じになるかを検証した。探索結果が一致しない局面があったため、詳しく調べるため、UCB値の計算結果をデバッグプリントしてゲーム木をスキャンする手順を比較した。その結果、UCB値が若干ずれていることに気づき、冒頭のミスが発覚した。

この修正を施したところ、floodgateでレート3300のgikou2_1cに勝利することができた。

wdoor.c.u-tokyo.ac.jp

今後

以上の実装をしたところで、2022年4月2日の電竜戦さくらリーグ2022に臨みました。

今後は、CSAプロトコルを実装してiPad単独でサーバと通信できるようにすることが最優先です。同時に局面の表示なども必要となりますが、その実装にはSwiftでのグラフィックス描画の知識をつける必要があります。 棋力的な向上をする余裕はありませんが、自前学習した15ブロック224チャンネルの評価関数が72エポックではまだ学習の余地が残っているようなので、学習を続けたものに差し替えることで少々改善するかもしれません。