将棋AIで用いている詰将棋ルーチンにdf-pnというアルゴリズムがある。 これは、proof number(証明数)、disproof number(非証明数)を用いて効率的に探索を行い、その局面が詰むか、詰まないかを判定できるとても強力なアルゴリズムである。 将棋ファンなら『脊尾詰』と言う「ミクロコスモス」(1525手詰)を解く詰将棋専用ソフトについて一度ぐらいは聞いたことぐらいあるだろう。これは、脊尾さんが大学時代に作成されたプログラムである。そこに使われていたのが脊尾さんが考案されたdf-pnというアルゴリズムである。 df-pnに関しては、脊尾さん自身の論文(1998年)があるものの、要点しか書かれておらず、いまのようにGitHubにソースコードがあるわけでもなく、その詳細については長らく謎に包まれたままであった。(この脊尾さんの論文では、証明数のみを用いており、非証明数は陽には出

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

先月のゴールデンウィークに行われた第33回世界コンピュータ将棋選手権(WCSC33)で弊やねうら王チームが準優勝したあと(この準優勝は本当に準優勝であって、ビールにおつまみで乾杯するという意味ではない)、角換りという戦型について以下のツイートをした。 角交換と言う戦型が終わった。 1886局面の指し手を覚えるだけで先手側は公開されてる水匠（探索局面数は1億までの任意）に対して評価値+300に出来ることが証明された。 大会で上位のソフトは+300から逆転は97%ぐらいありえないので（手数で引分はある）つまりは将棋AIの世界では角交換の後手は必敗。 — やねうら王 (@yaneuraou) May 8, 2023 この前者のツイートにはインプレッションが172万もあり、Yahooニュースや朝日新聞デジタルなど多くのメディアで取り上げられた。 AIで角換わりが終わった？　藤井聡太竜王「こちらの立

渡辺名人が購入した130万円のパソコン、クラウドでそれと同じ性能のもの、1時間50円で使えるよとツイートしたらえらくバズった。 上のツイートは、決して渡辺名人の研究を揶揄するものではなく、書き方次第で最低にも最高にも聞こえるという、そういう物事の二面性みたいなのって面白いよねという意味でツイートしたわけである。 しかし「クラウドの料金そんなに安くねーだろ」「それってGPUだけの値段ですよね？」「値段一桁間違えてない？」「クラウド使ったことない奴の妄想乙」みたいなツッコミをたくさん頂戴している。

WCSC31(第31回世界コンピュータ将棋選手権)、二次予選、やねうら王は予選敗退しました。 やねうら王は、初戦で昨年末の電竜戦で優勝したdlshogiを後手番で下し、次にHEROZの計算資源をふんだんに使えるという噂のPALも同じく後手番で下し、私は気持ちよくお昼寝して起きたら、そのあと連敗してました😅 どうやらAWSのp4インスタンスのメモリ1.1TBを使い切って、コンソールから応答返ってこなくなったらしいです。nps(探索速度)が本家dlshogiより出るように頑張ったのに、それが仇となって、1.1TBのメモリを使い切って死ぬとは。 第2局でも終盤で4秒ぐらいで指すはずのところで大長考をしているので(コンソールからの応答もなし)、よく第2局で勝てたなという感じ。 そのあと私はお昼寝してたんですけど、フリーズすると困るのでオペレーション担当のMizarさんは、やねうら王を以前の探索部

このブログをご覧の方は将棋が二人零和有限確定完全情報ゲームであることはご存知でしょう。これは、ゲーム理論や探索アルゴリズムの教科書にでも載っています。「二人零和有限確定完全情報ゲームって何？」って方は、Wikipediaでも見ていただくことにして話を先に進めます。 零和とは？ この「零和」というのは、和が零。英語で言うとゼロサムです。 零和（「ゼロ和」と読むのが一般的だが「レイワ」とも読む）：プレイヤー間の利害が完全に対立し、一方のプレイヤーが利得を得ると、それと同量の損害が他方のプレイヤーに降りかかる https://ja.wikipedia.org/wiki/二人零和有限確定完全情報ゲーム つまり、自分が勝ちなら、相手は負け。相手が勝ちなら自分は負け。勝ちを+1点、負けを-1点、引き分けを0のように定めるなら、(ゲーム終局後に)自分と相手の点数を足すと0になる。なので、ゼロサムゲームと

第29回世界コンピュータ将棋選手権(WCSC29)で、『やねうら王 with お多福ラボ2019』は優勝しました。応援してくださった皆様、ありがとうございます。 手短にいくつか印象に残った試合と簡単な感想を書いておきます。 Qhapaq戦 Qhapaqはこちらが指し手を思考している最中に相手の指し手を別のPCで予測して、それに対するponderの指し手を探索する『Pre-ponder』という隠し球を実装しているそうでした。 QDMのクラスタはmultiponderベースだったのですが独自実装のpreponderを加えることで相手の持ち時間の120％を使えるという謎の効率化に成功しました。 — Ryoto_Sawada☀Qhapaq (@Qhapaq_49) May 5, 2019 そこで、Qhapaq戦については、SlowMover(序盤重視率)=67にして、序盤の思考時間を減らして終盤に

発端は、橋本崇載八段の次のいささか不可解なツイートから。 ＜電王戦＞将棋ソフトが連勝　１１８手で山崎八段降す（毎日新聞） – Yahoo!ニュース 指さずしてわかってた結果。こういうニュース見て誤解しないでほしいのは、彼は将棋で負けたのではなく将棋に似たゲームで負けただけ、ということです https://t.co/UXlvBKvcC0 — 橋本　崇載 (@shogibar84) May 22, 2016 「将棋に似たゲーム」とは何なのだろうか？私には橋本八段の真意はよくわからない。というか、このツイートだけでは誰にも正確にはわからないのではないかと思う。 コンピューターの将棋は異質だと言いたいのか、それとも機械と人間とでは条件的にフェアではないと言いたいのか、計算機に人間が敵うはずがないと言いたいのか、人と人とやるのが将棋本来の姿でありそれ以外は将棋ではないと言いたいのか、それらをわざとぼ

電王戦第2局においてSeleneが相手の角不成に対して非合法手を指して反則負けになった件ですが、理由は私には想像つくので、以下に書いておきます。 UCIプロトコルでは、思考を開始する局面は、普通、startpos(平手の初期局面)からの指し手を示す文字列が送られてきます。と言うことは、常識的には、UCI表記での指し手文字列を思考エンジンが内部で使っている指し手構造体に変換する必要があります。ところが、Stockfishにはこの変換をダイレクトに行なう関数は存在しません。さて、どうやっているのでしょうか。 実は、現在の局面の合法手すべてを生成して、それをmove_to_uci( )でそれをUCIの指し手文字列に変換し、それが与えられた文字列と一致したら、そのmove_to_uci( )で変換する前の指し手構造体を返すという実装になっています。少し遅いのが気になりますが、思考開始のときに送られ