すごいニュースが飛び込んできた。オセロの必勝法が見つかったのだ。正確に言うとオセロが弱解決された。まずはその論文を紹介する。 Othello is Solved : https://arxiv.org/abs/2310.19387 「弱解決(weakly solved)」を簡単に言うと、初期局面からの双方最善手を打つ時の結論(勝敗)がわかったと言う意味である。8×8のオセロの結論は引き分けなのだそうだ。「必勝法が見つかった」と本記事のタイトルで書いたが、その結果として双方最善を尽くした時のオセロの結論が引き分けだったことが判明したので正しくは「必勝法(必ず勝てる方法)が存在しないことが証明された」とでも言うべきか。 今回は、初期局面から到達できるあらゆる局面についての結論(勝敗)がわかったわけではない。こちらは「強解決(strongly solved)」と呼ばれる。 弱解決と強解決とでは、

WCSC30(第30回 世界コンピュータ将棋選手権)がコロナのために中止となり、代わりにWCSO1(世界コンピュータ将棋オンライン大会)が有志によって開催された。そこで優勝したのは水匠であったが、この水匠の思考エンジンは、探索部やねうら王、ｍブランチであった。ｍブランチとは何なのか。ｍブランチは何故強いのかについて軽く書いてみたい。 ｍブランチとは？ やねうら王のGitHubにあるソースコードに、有志がStockfishの最新の探索部のコードを反映させたものである。 ｍブランチ強いのか？ ロタさんの計測によると以下のようである。まあ、R100以上は対局回数が多くないと誤差が大きいので信頼度は低めなのだが、R100以上は強そうである。 #RRate #WCSOC2020 後の計測で分かったことを図解してみました Qhapaq from Neo-Saitamaのｍブランチの有無での勝率差がとて

AlphaZeroの再現実験として、YSSの山下さん、Bonanzaの保木さん、Ray(囲碁ソフト)の小林祐樹さんのゴールデンコンビがタッグを組んだAobaZeroというソフトがあるのですが、ここ最近は棋力が停滞気味であります。 http://www.yss-aya.com/aobazero/ 対して、AlphaZeroのようにDeep Learningを用いている将棋ソフトではあるものの、山岡忠夫さんのdlshogiのほうは、AlphaZeroの再現にはこだわってないようで、C++で高速化したり、終盤用にdf-pnによる詰将棋ルーチンを搭載したり、LeelaChessZero(AlphaZero型のオープンソースのChessのソフト)の改良点を取り込んだり、TensorRTを用いた高速化を行うなど、様々な改良を意欲的にされていて、ずいぶん強くなっているようです。 将棋AIの進捗 その42

昨日の記事で、やねうら王miniのサンプルコードとして、将棋の初期局面から決まった深さまでの全合法手の組み合わせがいくつあるかを数えるプログラムを書きました。 以前、Stockfishのperft、ちらっと見て、「パフォーマンステスト？何やってるかよくわからん、探索と関係ないからまあいいや」と思って放置してたんですけど、、私は自力で同じ概念を発明して、「これを使えば簡単に合法手生成のテストが出来るな！このアイデア、すげーや！さすが俺や！」と思っていたら、それこそがperftであったという、アハ体験というかアホ(阿呆)体験というか、なんかそういう体験を昨日まさにしました。 そしてすでにaki.さんが将棋におけるperftをされてて記事までありました。 将棋でPerftしてみたまとめ http://qiita.com/ak11/items/8bd5f2bb0f5b014143c8 やねうら王m

今回のWCSC29(第29回世界コンピュータ将棋選手権)では、AWSを利用するチームが目立った。ハイスペックなPCを持ち込んで戦うよりは、軽量なノートPCだけ持ち込んでAWSを使ったほうが機材の搬入が楽だし、スペックも悪くない。しかし、普段sshを使うこともないような人にとっては知らないことだらけでどうやって良いのか戸惑うことも多かった。かくいう私もその一人であった。そういう人の助けとなるように記事にまとめておく。 WCSC28でelmoが反則負けした件 まず、この原因を書いておくところから。この原因を知らないと怖くてsshが使えない。 elmoの瀧澤さんにWCSC29で尋ねたところ、「あれはMicrosoft製のsshを使っていて、1年以上更新していなかったもので、そのバージョンが古く、1行のバッファが1024文字までだったのが原因です。」とのことであった。 1行が1024文字までなので

だいたいにおいて、やねうら王ほどメジャーな将棋ソフトの探索部に大きなバグを埋め込むことは常識的に考えると不可能である。多くの人が改良に参加している＆参考にしているので、誰かの目に止まるはずではある。ところが、公開後、数年も誰も気づかなかったbugがつい先日見つかった。Aperyの平岡さんが、AperyをRustで書き直している時にRustのコンパイラが警告を出したので気づいたと言うのだ。(WCSC29の会場で平岡さんから直接教えてもらった。) bugの詳しい内容 ここから少し専門的な話が出てくる。プログラマでない人は次の見出しまで読み飛ばすこと推奨。 – Position::move16_to_move()のbug fix。thx.平岡さん https://github.com/yaneurao/YaneuraOu/commit/9e6ba09029839838e10cd928456935

WCSC29(第29回 世界コンピュータ将棋選手権)まであと1ヶ月を切りました。今年の見どころをざっと確認しておきましょう。 ※　WCSC29 公式URL : http://www2.computer-shogi.org/wcsc29/ まずは、何と言ってもガチDeep Learning勢。(以下DL勢と略す)　tanuki-チームのNNUE評価関数もDeep Learning勢と言えなくもないですが、GPUを用いていないこと、そして、AlphaZeroが採用していたResNetからはかけ離れているので、「ガチDeep Learning勢」からは除外しておきます。 注目は、Team Aoba Zeroチーム。このチームは、Bonanzaの保木さん、YSSの山下さん、囲碁のRayの作者でもある小林さんの3名によるタッグチームで、保木さんのコンピュータ将棋方面への復帰に古参の開発者からは歓迎の

コンピュータ囲碁の世界では、長きに亘り良い評価関数を設計できずに苦心していました。評価関数というのは、人間で言うと大局観に当たる部分です。この部分をうまく設計するのが強い囲碁ソフトを作る上で必要不可欠なのですが、それは職人のような作業だと言われていました。 そのあとAlphaZeroが現れたことにより、評価関数は人間が設計したものより、ニューラルネットワーク(以下NNと記す)のほうがうまく表現できることが証明されました。このことは、コンピュータ囲碁プログラマの敗北であると同時に新たな時代の幕開けでした。 一方、コンピュータ将棋の世界は少し様相が異なりました。コンピュータ将棋では、2005年にBonanza6が取り入れた、王様とそれ以外の任意2駒といういわゆる三駒関係(KPP)を10年以上使ってきました。途中でNDF[2014]が手番を入れてKPPT(Tは手番ではなくTurnのT)型に進化し

電王トーナメント直前ですが、AWSを使って機械学習で使う教師局面を生成してみようと思い、昨日実際にやってみたので、そのノウハウを書いておきます。ノウハウというか、たぶんLinuxに慣れているような人なら誰でも知っているはずのことで、誰得記事ではあるのですが、私は大いに躓いたので記録として残しておきます。 Linuxのspot instanceが使えるようにしろ AWSを借りる上で大きな違いになるのがOSの種別です。WindowsとLinuxとではお値段が3倍ぐらい異なります。オンデマンドインスタンスとスポットインスタンスとでもお値段が3倍ぐらい異なります。つまり、将棋ソフト向けの機械学習で使うなら普通はLinuxのスポットインスタンス一択です。(Deep Learningは使わないものとします。) 自分の書いた将棋ソフトのソースコードがLinuxでコンパイルが通るようにしろ そこでLinu

今回のやねうら王は、学習時に人間の棋譜を用いていない。いわゆるリゼロ系である。学習時に人間の定跡も用いていない。初期局面から何手かランダムムーブさせた局面からdepth 10で対局させたものを教師局面として用いている。 だから、今回、定跡を作るときも、人間の棋譜を使うのではなく、完全に自力で(自ら探索して)生成することにした。人間の対局に一切左右されたくないからである。 定跡を作った詳しい手法については別の記事で書くが、こうして作った定跡が不思議なことにプロ棋戦でよく現れる形をたくさん包含していた。プロ棋士の遠山先生にこのことを話したところ「いまさらそんなことでは驚きませんけども」と軽く言われたのだが、以前作成した定跡(真やねうら定跡)ではプロ棋戦に出現するような指し手は指さない(指せない)ので、私にとっては意外であった。 プロの定跡は、江戸時代から連綿と続く試行錯誤の結果到達した人類の叡

今年のSDT(将棋電王トーナメント)の開催日が発表になりましたね。11月の11,12日だそうです。参加予定の皆さんの開発は捗っているでしょうか？やねうら王はまだ1㍉も強くなってませんが。 将棋ソフトに興味のあるプログラマの方から「将棋ソフトばっかりずっといじってて飽きないのか」という質問があったのでこの場でお答えしますが、毎年トレンドって変わるんですよね。 SDT1(第一回将棋電王トーナメント)からやねうら王の変遷をざっと振り返ってみましょう。 SDT1 .. Bonanzaの高速化 高速化と言っても並列化もさほどする余地がないので、SSE2/4の命令でガシガシ書いて速くなるわけでもなく、アルゴリズム的に等価な変換を利用して計算量を減らすとという感じでした。コメントがほとんど書かれていないBonanzaのソースコードを解読する作業とパズルを解くような作業の繰り返しでした。ずいぶん頭の体操に

今回、新たに評価関数をゼロベクトルから学習させた。elmo絞りを使うと意外と簡単にApery(WCSC26)相当の棋力を持つ評価関数にまで出来るようだ。追試できるように記事の前半に手順を記しておく。また、記事の後半には何回目のelmo絞りでどの程度の強さであったかも示す。 elmo絞りを知らない人のために簡単に説明すると、今回、将棋ソフトが人間の棋譜を用いずに勝率の高い形を強化学習でソフト自らが自動的に覚えたということである。今回、1回に生成している教師の数は5億局面。対局回数で言うと400万局程度であろうか。それだけの対局を終局までこなすことで、どういう駒の位置関係だと勝ちやすいのかを学習したということだ。 私は以前、elmo絞りを用いずにある程度の強さまでは到達出来たのだが、計算資源を湯水の如く消費するので途中で断念してしまった。今回はそのリベンジである。題して「Re : ゼロから始め

機械学習で使う用にhalf float(16-bit float)の演算ライブラリ作りました。と言ってもfloat型がIEEE 754の形式であることを仮定して、符号bitと指数部、小数部をそのままとってきてuint16_tに変換する、みたいな感じのお手軽実装ですが。 このライブラリの必要性 コンピューター将棋の評価関数の機械学習では、KPPT型の評価関数が主流で、その配列の大きさが1GB(次元数で言うと5億次元)程度になっています。今後、評価関数の次元数を増やそうと思ったときに、省メモリ化がどうしても必須になるので、half floatで計算してくれるライブラリを製作しました。 世の中にはすでにhalf floatのライブラリはいくつかあるのですが、わかりやすくシンプルに実装してあって、お手軽に使えそうなものがなかったので自作しました。 注意点 ちなみにソースコード中に出てくるs16,s

ボンクラーズの伊藤さんの記事が非常に興味深いです。 「浅い評価値を深い評価値に近づける学習法」誕生の背景 http://aleag.cocolog-nifty.com/blog/2016/10/post-00f4.html NDFのこの学習手法は、伊藤さんの発言がきっかけで誕生したということのようです。 まあ、この学習手法自体はTD-leafとかRootStrapとか呼ばれている手法で(亜種多数)、Seleneやひまわり、GA将なども、比較的昔から取り組んでいたと思います。私もTD-leaf自体は早い段階で知っていましたが、これが将棋でうまくいくアイデアだとは思わなかったというのもあります。 あと、当時のPC環境や、学習手法では、学習に非常に時間がかかるので、おいそれと試せなかったという背景もあります。 いずれにしましても、最初に試した人して成功させた人は偉いと思いますし、「成功するかどう

本日も大会の様子を実況していきます。 道に迷ってた くそー。道に迷った。GPS効かない。何故だ？ここは樹海か？ — やねうら王 (@yaneuraou) October 9, 2016 マジで会場入り、遅れるかも知れん。タクシー？俺にXeon×2搭載PCを5台買う金はあっても、タクシーに乗る金はねぇんだよ！ — やねうら王 (@yaneuraou) October 9, 2016 もうかれこれ一時間以上歩いてるのだが、さすがに喉もからからだ。しかし、会場に無料ドリンクがあるというのに、こんなところで飲み物を買うわけにはいかん。この地獄の業火に焼かれるような辛苦、ponanzaにこそ味合わせてやる…！ — やねうら王 (@yaneuraou) October 9, 2016 この煉獄の饗宴で俺の魂を揺さぶるライジングサンは天国への道標か。（訳:喉が乾いて死にそうなのに太陽が照りつけてきて、マ

今日も実況していきます。 やねうら王ライブラリ使用チーム 当初13チームかと思っていたのですが、PR文書に書いてないけど使っているよと教えていただいたチームが何チームかあり、また会場で、「学習部参考にさせていただいてます」と言っていただけたチームも何チームかあったので、2/3近くのチームがやねうら王を何らか参考にしているようです。バグ報告もいただけたりして助かります。 やねうら王の学習部で雑巾が絞りにくかった理由 理由がある程度わかったので、気が向いたら書きます。 真やねうら王、強くなったよ？ とりあえず、なんやかんやして今日のやねうら王は昨日のやねうら王からR40程度上がりました。これで浮かむ瀬は超えた…はず。それでもponanzaとはR200程度の差がある計算になりますが。まあ、R200差ならponanzaと当たれば2割強ぐらいの確率で一発入るかもということで。 本戦の組み合わせ 将棋

一つ目は言うまでもなくLazySMP。従来、並列探索は、YBWC(Young Brothers Wait Concept)という方法を採っていた。 YBWCについて詳しい説明はググレカスなのだが、「Wait」という文字があることからわかる通り、あるスレッドが他のスレッドの終了を待機する必要がある。スレッド間の相互干渉がわりとあって実装するのが難しいし、many core(8コア以上)ぐらいから効率があまりよろしくなく、10コア動作時と20コア動作時とでほとんど強くなってなかった。(むしろ弱くなることすらあった。) LazySMPは、それぞれのスレッドが独立して探索するだけの並列探索である。置換表を共有しているので、探索した結果がさほど無駄にはならないということなのだ。 LazySMPによってmany core時の強さが飛躍的に向上した。 もう一つの探索部の大きな進歩として、follow u

この記事で実況していきます。 今回の技巧は？ 公開している技巧から+R150ぐらいとのこと。 やね「電王トーナメントが終わったらまたソースコード公開するんですか？」 出村「する…かも…」 今回のApery(浮かむ瀬)は？ 探索はStockfish7に合わせたとのこと。探索パラメーターの調整はあまりしてない様子。 会場の写真公開禁止の件 スタッフより、「放送が始まるまで、会場(の全体が写っているもの)の写真をSNS等にアップしてはいけません」とのこと。 ※　放送が開始になったので写真を追加。 会場の写真解禁っ！！(>_<) #電王トーナメント pic.twitter.com/SH3oc8yYAe — 香上 智＠Labyrinthus＋＃ (@kagami_tomo) October 8, 2016 SkylakeのHTが遅い件 今回のPC、HT時のnpsがあまり出ないようです。並列化効率の良