詰将棋アルゴリズムdf-pnのすべて | やねうら王 公式サイト
将棋AIで用いている詰将棋ルーチンにdf-pnというアルゴリズムがある。 これは、proof number(証明数)、disproof number(非証明数)を用いて効率的に探索を行い、その局面が詰むか、詰まないかを判定できるとても強力なアルゴリズムである。 将棋ファンなら『脊尾詰』と言う「ミクロコスモス」(1525手詰)を解く詰将棋専用ソフトについて一度ぐらいは聞いたことぐらいあるだろう。これは、脊尾さんが大学時代に作成されたプログラムである。そこに使われていたのが脊尾さんが考案されたdf-pnというアルゴリズムである。 df-pnに関しては、脊尾さん自身の論文(1998年)があるものの、要点しか書かれておらず、いまのようにGitHubにソースコードがあるわけでもなく、その詳細については長らく謎に包まれたままであった。(この脊尾さんの論文では、証明数のみを用いており、非証明数は陽には出
SIMDによる将棋Bitboard計算の高速化 - すぎゃーんメモ
自作Rust製将棋合法手生成ライブラリ、計算の高速化のためBitboardの128bit計算をSIMDで行うようx86_64のAVX2、AArch64のNEON、wasm32のsimd128で動くようにそれぞれ実装して 各環境で多少速く探索できるようになった。https://t.co/h7Dz3X6BhT— すぎゃーん💯 (@sugyan) July 2, 2022 ということでSIMDでの高速化のメモ。 SIMDとは 実装 x86_64 基本演算 飛び利き計算 AArch64 同値判定、ゼロ値判定 飛び利き計算 Iterator WebAssembly Benchmark x86_64 AArch64 WebAssembly 感想 SIMDとは ja.wikipedia.org の通り、複数のデータを1命令で同時に演算する、というもの。 将棋Bitboardは81マスのデータを表現する
人間にうまく負けるためのゲームＡＩはいかに開発されているのか。将棋、囲碁、麻雀などの定番系ゲームを手掛ける開発会社に聞いてみた
どんどん強くなる将棋ＡＩ。 あの藤井聡太二冠ですら「ソフトと対戦することはありません」と発言し、人類ＶＳコンピューターという構図は過去のものとなった観があります。 ですが一方で、人間と戦い、そして負けることを目的とした将棋ＡＩもあります。 それはゲームソフトとしての将棋ＡＩです。 弱すぎてもダメだし、強すぎてもクリアできないから面白くない……そんなユーザーの要望に応え、家庭用ゲームソフトとしての将棋ＡＩを２０年以上作り続けている会社が、なんと岐阜にありました。私の実家から車で４０分くらいの場所に……。 『超速３七銀戦法』で升田幸三賞を受賞したプロ棋士の星野良生五段を正社員として登用した会社と言えば、ピンとくる方もいらっしゃるのではないでしょうか？ しかもその会社は……１２月１７日に発売となる『りゅうおうのおしごと！』のゲームにも将棋エンジンを提供してくれているというではありませんか！ これ
ソフトウェア工学的には羽生善治の「5二銀」は最善手ではない!? 東工大入試問題をプログラムで解く
ソフトウェア工学的には羽生善治の「5二銀」は最善手ではない!? 東工大入試問題をプログラムで解く：組み込みエンジニアの現場力養成ドリル（32）（1/4 ページ） 今回は、東工大の2012年度入試問題（数学）を取り上げます。これをプログラミングで解いていただきますが、今回のテーマは単に「難解な入試問題をC言語で解く」という「10分間ミステリーのような意外性を楽しむ頭脳ゲーム」ではありません。その一歩先の「誰にでも簡単に理解できるアルゴリズムとはどういうものか」という「ソフトウェア開発の永遠の課題」を考えることにあります。 第27回目の本コラムでは、東大の伝説の入試問題、「π＞3.05を証明せよ」を取り上げました。大学の入試問題として、おそらく世界で最少文字数でしょう。この問題は、余弦定理を応用して解くのが受験での王道ですが、同コラムでは、ピタゴラスの定理だけで解く方法と、C言語によるプログラ
異形の盤面が「毎ターン詰め将棋」な展開を生み出す「エクストリーム将棋」をプレイしてみた
「エクストリーム将棋」は日本の古典的なボードゲームである将棋を独自にアレンジしたボードゲームです。将棋の重要な要素である「盤面」「駒」の2つに手を加えることで、ハラハラドキドキの超短期決戦なゲームになっているとのことなので、実際にプレイしてどんなゲームなのかを確かめてみました。 エクストリーム将棋（新版） / ボードゲーム通販「JELLY」 https://shop.jellyjellycafe.com/products/detail/1918 これがエクストリーム将棋です。 エクストリーム将棋は、日本の古典的なボードゲームである将棋に、カードを引いて盤をつなげて駒を配置するという一風変わったアレンジを施したもの。 1プレイあたりの時間は15分で対象年齢は6歳以上、プレイ人数は2人。 同梱物は、カード、将棋駒、ライフマーカー、ついたて、将棋盤、説明書。 エクストリーム将棋の特徴は、「盤」と
高速な詰将棋アルゴリズムを完全に理解したい（完成版） - コンピュータ将棋 Qhapaq
Qhapaq アドベント将棋記事10日目 今の詰将棋アルゴリズムで最強と言われているハッシュテーブル+df-pn探索(depth first - proof number)による詰将棋アルゴリズムの完全理解を目指していきます。 参考文献： memo.sugyan.com 【proof numberとは】 proof numberとは平たく言えば詰将棋専用の盤面評価値みたいなものです。通常の盤面評価値と違って、詰み証明のための評価値(pn)と不詰証明のための評価値(dn)があります。pn、dnは「この局面の詰み(proof number)/不詰(disproof number)を証明する為に調べなければならない局面の数」であり、値が小さいほど詰み/不詰に近いという扱いになります。そして、詰み /不詰が証明された局面についてはpn、dnは0になります。局面のpn、dn（厳密には非0のpn、dn
機械学習エンジニアのための将棋AI開発入門その2 | やねうら王 公式サイト
前回の続き。将棋AIで最初に大規模機械学習に成功させたBonanzaの開発者である保木さんのインタビューがちょうどYahoo!ニュースのトップ記事として掲載されたところなので、今回はBonanzaの機械学習について数学的な観点から解説してみたいと思います。 Bonanzaの保木さんのインタビュー記事 プロ棋士に迫ったAI「Bonanza」 保木邦仁「将棋を知らないから作れた」 https://news.yahoo.co.jp/feature/1712 BonanzaのGPW発表スライド とは言え、Bonanzaで使われている機械学習の技法は、いまどきの機械学習とは少し毛色が異なるので心の準備が必要です。 まず、保木さんのGPW(ゲームプログラミングワークショップ)での発表スライド、以前はBonanzaの公式サイトからダウンロードできたのですが、Bonanzaの公式サイトがジオシティーズにあ
研究会レポート Vol.1 ゲスト：羽生善治（棋士） | 未来の人類研究センター
未来の人類研究センターの研究活動の主軸となる研究会、最初のゲストは棋士の羽生善治さん。センターメンバーである磯﨑憲一郎先生からのご紹介で、この日はまず羽生さんからのお話をみんなでうかがったのち、質疑応答を含む雑談へと発展していきました。 羽生善治さんは、1985年に中学生でプロ棋士になり（史上３人目）、1989年に初タイトルである竜王を獲得、1994年に24歳で六冠王になり、その２年後には、史上初の七冠（竜王・名人・王位・王座・棋王・王将・棋聖）を独占という偉業を達成。将棋の好き嫌いにかかわらず、その名は、終盤にくり出す逆転劇を表す「羽生マジック」とともに、広く知れ渡ることとなります。これまでのタイトル獲得数は、名人９期・竜王７期・王位18期・王座24期・棋王13期・王将12期・棋聖16期という合計99期で歴代１位、通算優勝回数は152回。若くしてデビューして以来、将棋の歴史を塗り替え続け
機械学習エンジニアのための将棋AI開発入門その1 | やねうら王 公式サイト
最近、機械学習を勉強している人が増えてきたので、簡単な機械学習ならわかるよといった人たち向けに将棋AIの開発、特に評価関数の設計について数学的な側面から書いていこうかと思います。線形代数と偏微分、連鎖律程度は知っているものとします。 3駒関係 3駒関係はBonanzaで初めて導入された、玉と任意の2駒との関係です。この線形和を評価関数の値として用います。評価関数とは、形勢を数値化して返す数学的な関数だと思ってください。 この3駒関係を俗にKPPと呼びます。King-Piece-Pieceの意味です。将棋の駒は40駒ありますので、{先手玉,後手玉}×残り39駒×残り38駒/2 通りの組み合わせがあります。この組み合わせは1482通りあります。Cをコンビネーション記号とすると、次のようになります。 $$ 2 \times {}_{39}C_{2}= 2 \times \frac{39 \tim
dlshogi強すぎクソワロタ | やねうら王 公式サイト
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
藤井聡太七段の強さをアマチュア初段クラスの人にもわかるように解説する - コンピュータ将棋研究Blog
はじめに 藤井聡太七段は現役の高校生棋士ながら、プロデビュー後は圧巻の成績を収めている。 その強さは将棋に詳しい人であれば棋譜を見ればわかるが、将棋歴がまだ浅い人にとっては「藤井聡太七段は具体的にどこが強いのか」という疑問があるかもしれない。 今回の記事ではアマチュア初段クラスの人にでも藤井聡太七段の強さがわかるように説明していきたい。 はじめに 序盤編～ソフト研究の影響と発想の自由さ～ 中盤編～意表さと正確さ 終盤編～的確さとあきらめない心～ まとめ 序盤編～ソフト研究の影響と発想の自由さ～ まずは序盤編。 藤井聡太七段はコンピュータ将棋ソフトでの検討を普段の研究に取り入れているという話は有名だ。 公式戦での対局においてもその影響を感じされるものは多い。 2018/11/20 持ち時間：6時間 棋戦：順位戦 戦型：中飛車 場所：東京・将棋会館 先手：増田康宏六段 後手：藤井聡太七段 手数
ゲームを解く！Educational DP Contest K, L 問題の解説 - Qiita
0. ゲームを解くとは 世の中には将棋や、囲碁や、オセロのような複雑で難しいゲームから、マルバツゲームや、割りばしゲームや、立体三目並べのような比較的単純なゲームまで、たくさんの種類のゲームがあります。 この種の二人プレイのボードゲームにはある共通の特徴があります。それは 双方が最善を尽くした場合において、「先手必勝」か「後手必勝」か「引き分け」かが予め決まっている。 そして無限の計算時間と計算機資源さえあれば、それを容易に解析できる。 という点です。このように 「先手必勝」か「後手必勝」か「引き分け」なのかを解析する その必勝手順を求める できれば + α として初期盤面だけでなく、すべての局面について「先手勝ち」か「後手勝ち」か「引き分け」かも特定して最善手も求める という営みが「ゲームを解く」ということであり1、それができたならばそのゲームを「完全に理解した」ということができます。本
ポジショナルプレーの特異性生む「枝葉」から「幹」へという着想 - footballista | フットボリスタ
TACTICAL FRONTIER サッカー戦術の最前線は近年急激なスピードで進化している。インターネットの発達で国境を越えた情報にアクセスできるようになり、指導者のキャリア形成や目指すサッカースタイルに明らかな変化が生まれた。国籍・プロアマ問わず最先端の理論が共有されるボーダーレス化の先に待つのは、どんな未来なのか？ すでに世界各国で起こり始めている“戦術革命”にフォーカスし、複雑化した現代サッカーの新しい楽しみ方を提案したい。 ポジショナルプレー――現代サッカーを読み解く、重要なキーワードとなる概念は、その複雑性ゆえに単純化されてしまいやすい。昨季はペップ・グアルディオラのマンチェスター・シティがプレミアリーグを制覇し、今季はナポリで魅力的なフットボールを実現したマウリツィオ・サッリがチェルシーの監督に。同時に、日本でも徳島のリカルド・ロドリゲス、ヴィッセル神戸のファンマ・リージョ、
フロッピーディスクに収まる評価関数バイナリ公開しました | やねうら王 公式サイト
NNUE評価関数は、ネットワーク構成を簡単にカスタマイズできるようになっている。 そこで、入力をK(玉のいる升)とP(どの升にどの駒がいるかに対応する値)だけにして(81升 + 1629通り = 1710)、hidden層の1層目を256×2、2層目・3層目を32にして学習させた。(K-P-256-32-32) NNUEを知らない人のために書くと、各層は全結合。 ※ 補足 : ニューラルネットの入力は、駒が存在するところを1、存在しないところを0とした1710次元のベクトル。 教師はdepth 8で生成した10億局面から学習させてみたところ、elmo – R30程度になった。 ファイルサイズは873KB。(zipで圧縮して400KB程度) 教師をもう少し深いdepthで生成すれば、まだ強くなるはず。 とりあえず公開しておいた。 https://github.com/yaneurao/Yan
用意した画像は一枚だけ！？物体検出で将棋駒の認識 - Qiita
※こちらはPythonデータ分析勉強会#02の発表資料です。 前回は、YOLOv3でパトライトの監視を行いました。 今回は、YOLOv3で「将棋駒」を認識させます。 そして、用意する画像は一枚だけという、無謀な挑戦をしてみます。 前回から、内容がガラリと変わっておりますが、まずはそのモチベーションを説明します。 なぜ、用意した画像は一枚なのか？ よくディープラーニングのサービスなんかを見ていると、用意する画像は1000枚とか 平気で書いてあります。 しかし、個人事業主や中小企業は、そんなに労力をかけて画像は用意できませんし、 1000枚用意しても、バリエーション豊かな画像じゃないと、意味がないことが多くあります。 用意する画像が一枚だけなら、労力は最小限ですし、バリエーションも気にしなくて良いです。 従って、「用意する画像が一枚」で精度が出るなら、世の中のディープラーニングの サービスがよ
【決定版】コンピュータ将棋のHASHの概念について詳しく | やねうら王 公式サイト
いまどきの将棋ソフトを使っていると、「HASH 50%」などと表示されている。これはHASH利用率と呼ばれる。この数字が大きくなってくると探索の効率が悪くなる。要するに潤沢にメモリがある場合に比べると弱くなる。これは、どれくらいの値までであるなら適切なのか？HASH利用率が99%にならない限りHASHには余裕があるものなのか？HASHはどういう仕組みになっているのか？HASH利用率が50%の状況で、ハッシュ衝突はしているのか？など、わりとソフトを長年使っていても知らない人が多いのでここに原理から詳しく説明した決定版的な記事を書く。 ShogiGUIや将棋神やねうら王に表示されている「HASH」とは何ですか？ 一度探索した局面を保存しておく表です。 この表に登録するときにハッシュ(hash)という値を使って登録するため、ハッシュテーブル(hash table)と呼ばれます。これを略して(値と
技術書典５でコンピュータ将棋本を頒布します in 池袋 - コンピュータ将棋 Qhapaq
来週月曜日の技術書典５にQhapaq開発チームも参加します。 イベントのページ： https://techbookfest.org/event/tbf05 https://techbookfest.org/event/tbf05/circle/53170003 以下、頒布物について簡単に紹介をさせていただきます。 頒布物は全て電子書籍です。ＱＲコード入りの紙を頒布する形式です 【科学するコンピュータ将棋ＬＴＳ板（７００円・８５ページ）】 技術書典４で科学するコンピュータ将棋を購入された方は無料でアップデートできます 盤面の高精度評価や、高速な探索アルゴリズム、盤面評価関数の技術的進化やトレンドといった、コンピュータ将棋を支える技術に関する解説を行います。 Bonanza時代から、2018年のState of the ArtのNNUE関数まで幅広く扱った、コンピュータ将棋の教科書的な一品です
「将棋プログラムをどう作ればいいですか？」という質問への返答｜山本一成🚗TURING
Twitterのダイレクトメッセージで「将棋プログラムをどう作ればいいですか？」という質問をいただいた。色々考えさせられる質問だったのでnoteにも共有してみたいと思う。 Alpha Zeroのお話はこちらから読めます。私個人の予想としてはDeep Learningを駆使したプログラムが今後どんどん強くなると思っています。 職業柄、若い人達にしばしば、どうやって将棋プログラムを勉強すればいいですかと聞かれます。私の20代はすべて将棋プログラムに費やしてきたし、その過程はとてつもなく知的好奇心に満ちた素晴らしい旅路でした。ただ、すでに将棋プログラムは十分成熟した段階を迎えています。 時代の変化は確実にあります。以前、熱かった分野が今後も熱い分野になるとは限りません。将棋プログラミングも題材としては相変わらずとても面白いものですが、2018年現在では、多くの人にお勧めできる研究テーマとはなりに
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
将棋ソフトをAWSで動かす方法を解説！！ノートPCでも毎秒2000万局面の検討が可能に！！ - みくにまるのブログ
将棋用語を描いてみた vol.1
