Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2015-12-24

競技プログラマー向け将棋AI開発入門 00:00 競技プログラマー向け将棋AI開発入門 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - 競技プログラマー向け将棋AI開発入門 - nodchipのTopCoder日記 競技プログラマー向け将棋AI開発入門 - nodchipのTopCoder日記 のブックマークコメント

はじめに

この記事はCompetitive Programming Advent Calendar 2015 25日目の記事として書かれたものです。

内容は競技プログラミング経験者であるnodchipが将棋AIの開発を通して得た知識と経験をまとめたものです。

まずは動かしてみましょう

f:id:nodchip:20151224235618p:image

一から将棋プログラムを作るのは難しいと思います。まずは既存の将棋AIを動かしてみて、どんな感じなのか感覚を掴んでみましょう。無料で手に入る主な将棋AIは以下の通りです。

これらのソフトはUSI(Universal Shogi Interface)プロトコルに対応した将棋AIです。

ネット上にはUSIプロトコルに対応したVisualizerがいくつか公開されています。nodchipはVisualizerとして『将棋所』を使用しています。

将棋AIを適切なフォルダに解凍したあと、将棋所→対局→エンジン管理から登録し、対局→対局で対局することができます。AI同士を対戦させるのも良いですし、AIに挑んでボッコボコにされるのも良いかもしれません。

ソースコードコンパイルしてみましょう

次にソースコードダウンロードしてコンパイルしてみましょう。Windowsの場合はVisual Studio 2015 Community EditionやMinGW-w64+MSYS、Linuxの場合はgccがあればコンパイルすることができると思います。

tanuki-の場合

  1. ソースコードgithubよりcloneしてくる
  2. Visual Studio 2015 Community Editionをインストールする
  3. tanuki-/tanuki-.slnを開く
  4. ビルドボタンを押す

これだけです。

将棋ソフトのコンポーネント

将棋AIは主に以下のコンポーネントに分かれています。

  • 盤面データ構造
    • 局面の状況を保持するデータ構造。強いソフトはBitBoardを用いた高速・省メモリなデータ構造を使っていることが多い。BitBoardについては後述。
  • 指し手生成
    • ある局面が与えられた時に、手番のプレイヤーが指すことができる合法手を列挙するルーチン。これが高速だと単位時間に読める局面が多くなる。一方、実際に指されそうな手から生成したほうが、ゲーム木探索で枝刈りが多く起こるようになり、探索効率が上がる。高速化と指し手の生成手順は、多分トレード・オフの関係にあると思う。
  • 盤面評価
    • ある局面が与えられた時に、先手後手のどちらが有利なのか数値評価するルーチン。これが高速だと単位時間に読める局面が多くなる。一方、より正確な数値評価ができたほうが強くなる。これもきっとトレードオフの関係にあると思う。
  • 盤面探索
    • ゲーム木を探索していくルーチン。
  • 置換表
  • 定跡データベース
  • USIプロトコル
    • GUI通信をするための部分。標準入出力にテキストを流していくだけの簡単なお仕事。競技プログラミングで入出力に慣れていれば単なる実装ゲー。ただしI/Oのflushは忘れずに。

ゲームAI独特のアルゴリズムを覚えましょう

コンピュータ将棋では競技プログラミング界隈であまり目にしないアルゴリズムが多いです。以下にそれらの一部を挙げます。

改造してみましょう

気になったところを改造してみましょう。プロファイラを使ってホットスポットを特定し、定数倍の高速化をかけるもよいでしょう。探索ルーチンの枝刈りパラメーターを調整するのも良いでしょう。機械学習ルーチンにナウなヤングにバカウケ最先端の学習アルゴリズムを導入するのも良いと思います。

例えばtanuki-がAperyに対して施した改造は以下のとおりです。

  • 定石データベースを変更し、インターネット上で入手可能なプロの棋譜約4万局と、floodgate上の対戦の中でレーティングGPS Xeon 12コア以上のAIが含まれた対戦の棋譜から作成しなおしました。
  • 定跡選択ルーチンを変更し、データベース作成時は指し手の評価は行わず、本番中に軽い探索を行い、定跡データベースから選択するようにしました。
  • 盤面評価関数のうちKKPをVGATHERDD命令を使って計算するようにしました。
  • volatile変数をstd::atomic<>へ変更しました。
  • static const変数をconstexprへ変更しました。
  • 置換表のEntrySizeを1に変更しました。
  • 置換表・評価キャッシュの使用率・ヒット率・破棄率を出力できるようにしました。
  • コンパイラをclang-3.7に変更しました。
  • Aspiration Window Searchのwindowの広げ方をStockfish6のものに近づけました。
  • 思考時間を変更し、序盤を短め、中盤を長めにしています。
  • KPPの重みを保持する3次元配列に適当なパディングを入れました。

自己対戦をしてみましょう

将棋所には自己対戦機能が実装されています。これを使って、昔のプログラムに比べて今のプログラムがどれくらい強くなったか確認してみましょう。

まず「対局」→「エンジン管理」から対戦させたいAIを登録します。次に「対局」→「対局」から先手と後手のAIを選択しましょう。残りのオプションをお好みで設定したら自己対戦開始です。おすすめの設定は以下のとおりです。

  • 手数が256手に達したら引き分けにする
  • 時間切れを切れ負けにする オン
  • 連続対局 オン
  • 連続対局数 9999
  • 自動棋譜保存 オン

対局数が少ないとランダム要素のせいで誤差が大きくなり、どれくらい強くなったのか正確に測ることができません。以下は「コンピュータ囲碁モンテカルロ法の理論と実践―」に書かれている、対戦数と有意差の関係です。

試合数有意に強くなったといえる勝率(95%)有意に強くなったといえる勝率(99%)
108勝2敗9勝1敗
2014勝6敗16勝4敗
5031勝19敗34勝16敗
10059勝41敗62勝38敗
200112勝88敗117勝83敗
500269勝231敗277勝223敗
1000527勝473敗537勝463敗

他のAIと対戦させてみましょう

AIが十分に強くなったらネット上で他のAIと対戦させてみましょう。コンピュータ将棋対局場「floodgate」は日本で最も有名なコンピュータ将棋ソフト同士の対局場の一つです。プロ棋士の一部も棋譜を参考にしているとのことです。

将棋所からfloodgateに参戦するためには「対局」→「サーバ通信対局(floodgate)」から対戦させたいAIを選び、ログイン名にランキングに表示されるAI名、パスワードに任意の文字列を入力してOKボタンを押せばよいです。

大会に出場してみましょう

現在定期的に開催されている大会は以下のとおりです。

世界コンピュータ将棋選手権は毎年5月のゴールデンウィークに開催されるイベントです。世界と名前が付いている通り、海外からの参加者もいます。

電王トーナメントは株式外社ドワンゴが主催するイベントで、不定期で開催されています。第3回電王トーナメントでは、優勝するとプロ棋士の代表と対戦することができました。

まとめ

競技プログラミング経験者nodchipが将棋AIの開発を行った経験を元に、将棋AIの開発に必要な雑多な知識をまとめました。あまりまとまっていない記事で恐縮です…。

この記事を呼んで将棋AIの開発を始めてくださる競技プログラマーが一人でも増えたら幸いです。

リンク

最後に

これにて競技プログラミングアドベントカレンダー2015は終了となります。それでは良いお年を。

ayquwiqyacayquwiqyac2017/12/21 12:43[url=http://price-of-levitra-20mg.mobi/]price-of-levitra-20mg.mobi.ankor[/url] <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

ekifobajekifobaj2017/12/21 12:45[url=http://price-of-levitra-20mg.mobi/]price-of-levitra-20mg.mobi.ankor[/url] <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

elazoreelazore2017/12/21 12:57[url=http://price-of-levitra-20mg.mobi/]price-of-levitra-20mg.mobi.ankor[/url] <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

eineiiwaqomaeineiiwaqoma2017/12/21 13:00[url=http://price-of-levitra-20mg.mobi/]price-of-levitra-20mg.mobi.ankor[/url] <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

ivohotazoivohotazo2017/12/21 13:24[url=http://price-of-levitra-20mg.mobi/]price-of-levitra-20mg.mobi.ankor[/url] <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

btfadenebtfadene2018/10/24 06:32online loan <a href="http://wwwonlinepaydayloans.com/">check cash</a> application cash fast loan [url=http://wwwonlinepaydayloans.com/]500 cash payday loan[/url]

bsfEmictbsfEmict2018/10/28 01:19bad credit auto loan <a href="http://cashmojoloan.com/">payday loans</a> payday loans direct lender [url=http://cashmojoloan.com/]cash advance online[/url]

snfadenesnfadene2018/10/28 02:51can payday loans garnish your wages <a href="http://perfectbadcreditloans.com/">personal loans bad credit</a> loans now [url=http://perfectbadcreditloans.com/]bad credit loans[/url]

bsflialobsflialo2018/10/28 06:18australian payday loans <a href="http://cash-advances-today.com/">quick cash advance</a> instant personal loan [url=http://cash-advances-today.com/]cash advance[/url]

sfrEmictsfrEmict2018/11/01 16:26personal loan <a href="http://usconstitutionof1777.com/">loans online</a> no credit check [url=http://usconstitutionof1777.com/] cash advance[/url]

vsklialovsklialo2018/11/01 22:52free viagra sample <a href="http://movietrailershd.org/">buy generic viagra online</a> buy viagra on line [url=http://movietrailershd.org/]generic viagra names[/url]

nsfadenensfadene2018/11/06 04:51buy viagra soft <a href="http://www.bitcapblog.com/">buy viagra cheap</a> viagra without prescription [url=http://www.bitcapblog.com/]generic viagra online[/url]

ebglialoebglialo2018/11/06 21:39buy cheap viagra <a href="http://mo-basta.org/">generic viagra buy</a> discount generic viagra [url=http://mo-basta.org/]buy viagra online[/url]

fujadenefujadene2018/11/14 10:13cialis pill <a href="http://joicialisosn.com/">tadalafil</a> tadalafil generic [url=http://joicialisosn.com/]buy cialis online[/url]

bshEmictbshEmict2018/11/14 22:28cheap cialis <a href="http://cialisgeans.com/">cialis buy</a> buy cialis without prescription [url=http://cialisgeans.com/]buy cialis[/url]

vsfEagemvsfEagem2018/11/15 10:37viagra alternative <a href="http://hpviagrajoagin.com/">viagra generic</a> order generic viagra [url=http://hpviagrajoagin.com/]buy viagra online[/url]

ndhEmictndhEmict2018/11/18 07:54tadalafil dosage <a href="http://hitcialisosn.com/">buy cialis online</a> tadalafil 20 mg [url=http://hitcialisosn.com/]cialis buy[/url]

dgjadenedgjadene2018/11/18 09:59viagra on line <a href="http://loviagraosn.com/">generic viagra online</a> pharmacy viagra [url=http://loviagraosn.com/]viagra online[/url]

ClieeCreaxClieeCreax2018/11/21 04:32Now you prefer something new? Open and look at this link. Only here the choice of young girls for every unique guy and completely free! They are good slaves, they will and want implement anything you order !
https://rebrand.ly/governy#A48

bbnadenebbnadene2018/11/21 10:26buy viagra online <a href="http://viagrafolec.com/index.html">generic viagra</a> purchase viagra [url=http://viagrafolec.com/index.html]cheap viagra[/url]

sfnEmictsfnEmict2018/11/22 11:37viagra <a href="http://sexviagen.com/">generic viagra online</a> viagra cheapest [url=http://sexviagen.com/]buy viagra[/url]

bumCyclebumCycle2018/11/27 09:05viagra plus <a href="http://erectiledysfunctionmedicinesus.com/">buy viagra</a> viagra information [url=http://erectiledysfunctionmedicinesus.com/]buy generic viagra online[/url]

RogerLoGRogerLoG2018/11/29 23:26Hello, go to http://xzvswwcvrc.com

btjEmictbtjEmict2018/11/30 05:33free viagra sample pack <a href="http://viagrapfhze.com/">generic viagra online</a> viagra overnight [url=http://viagrapfhze.com/]generic viagra online[/url]

RogerLoGRogerLoG2018/11/30 11:46Hello, go to http://xzvswwcvrc.com

sbgjEmictsbgjEmict2018/12/08 08:04viagra brand name <a href="http://usa77www.com/">viagra generic</a> prescription viagra [url=http://usa77www.com/]what is the generic name for viagra[/url]

vdeadenevdeadene2018/12/11 11:42viagra and alcohol <a href="http://viagravkash.com/">viagra online no prior prescription</a> cost of viagra [url=http://viagravkash.com/]buy viagra online cheapest[/url]

bbjEmictbbjEmict2018/12/11 20:40viagra pharmacy <a href="http://erectionakebd.com/">best place to buy generic viagra</a> generic viagra [url=http://erectionakebd.com/]cheapest viagra online[/url]

vfdadenevfdadene2018/12/15 06:09tadalafil 20 mg <a href="http://qenericcialls.com/">where to buy cheap cialis online</a> cialis without a prescription [url=http://qenericcialls.com/]buy cialis online with prescription[/url]

vcvadenevcvadene2018/12/18 19:27tadalafil cialis <a href="http://cialisgeans.com/">buy cialis canadian pharmacy</a> tadalafil liquid [url=http://cialisgeans.com/]buy cialis over the counter[/url]

bssEmictbssEmict2018/12/20 22:20cheap tadalafil <a href="http://cialisgessa.com/">generic cialis tadalafil best buys</a> cheap tadalafil [url=http://cialisgessa.com/]cialis generic timeline[/url]

FrankdesFrankdes2018/12/23 04:48 Do you want something new? Look at this site. Only here the choice of girls for every taste and completely free! They are obedient slaves, they will do everything you say!
https://governy.shortcm.li/governor#5o

tnlOvapetnlOvape2018/12/23 06:04cialis 20mg <a href="http://valcialisns.com/">cialis online pharmacy</a> cialis no prescription [url=http://valcialisns.com/]generic cialis[/url]

bgvlialobgvlialo2018/12/24 03:46purchase viagra <a href="http://dejviagram.com/">cheap generic viagra</a> low price viagra [url=http://dejviagram.com/]best place to buy viagra online[/url]

mmwlialommwlialo2018/12/26 20:49[url=http://sexviagen.com/]viagra online generic[/url] viagra story <a href="http://sexviagen.com/">best place to buy viagra online</a>

nnradenennradene2018/12/27 09:20[url=http://cialisserfher.com/]buy cialis online canada[/url] cialis canada <a href="http://cialisserfher.com/">buy cialis generic</a>

ikkEagemikkEagem2018/12/29 12:09[url=http://genericjojos.com/]canadian viagra generic[/url] natural alternatives to viagra <a href="http://genericjojos.com/">generic viagra cost</a>

bcfadenebcfadene2018/12/30 08:07[url=http://getaloan.us.org/]advances payday loans[/url] paydayloans chicago <a href="http://getaloan.us.org/">payday loans no fax</a>

ndgBreedndgBreed2019/01/03 11:46[url=http://applygopayday.com/]payday loan company reviews[/url] poor credit loans <a href="http://applygopayday.com/">payday loan affiliate program</a>

hhyEagemhhyEagem2019/01/04 18:20[url=https://onlineloan.icu/]payday loan for military[/url] cash 2u payday loans <a href="https://onlineloan.icu/">payday loan lenders no fax</a>

myhadenemyhadene2019/01/06 09:22[url=http://buyviagrawww.com/]how to buy viagra online[/url] cheap viagra pills <a href="http://buyviagrawww.com/">viagra best buy reviews</a>

nrgBreednrgBreed2019/01/06 12:34[url=http://viagrageneric7k.com/]best place to buy viagra online forum[/url] buy viagra new york <a href="http://viagrageneric7k.com/">where to buy viagra</a>

hhyagicthhyagict2019/01/09 16:22[url=https://almeidacorp.com/]buy real viagra online[/url] viagra sample <a href="https://almeidacorp.com/">safest place to buy viagra online</a>

oolBreedoolBreed2019/01/09 17:17[url=http://usa77www.com/]buy generic viagra online india[/url] viagra pill <a href="http://usa77www.com/">buy viagra cheaply</a>

vveOvapevveOvape2019/01/09 18:01[url=http://canadiannowv.com/]where can i buy viagra online[/url] viagra canada <a href="http://canadiannowv.com/">buy generic viagra online with mastercard</a>

hhtagicthhtagict2019/01/12 16:02[url=http://onlineviagraunes.com/]can i buy viagra online[/url] canadian viagra <a href="http://onlineviagraunes.com/">how to buy viagra</a>

jjyBreedjjyBreed2019/01/12 17:16[url=http://cialisckajrhd.com/]how to get cialis prescription online[/url] cialis without a prescription <a href="http://cialisckajrhd.com/">real cialis online</a>

bfgOvapebfgOvape2019/01/12 17:59[url=http://viagravkash.com/]viagra online usa[/url] viagra pill <a href="http://viagravkash.com/">generic viagra online canadian pharmacy</a>

aaqlialoaaqlialo2019/01/13 05:27[url=http://viagraoahvfn.com/]generic viagra online[/url] free viagra without prescription <a href="http://viagraoahvfn.com/">buy generic viagra</a>

nnfagictnnfagict2019/01/15 12:32[url=http://greengenericjen.com/]best places to buy viagra[/url] generic viagra <a href="http://greengenericjen.com/">viagra best buy reviews</a>

befOvapebefOvape2019/01/16 07:56[url=http://www.forumdemulheres.com/]where to buy cialis online forum[/url] viagra online uk <a href="http://www.forumdemulheres.com/">buying generic cialis online</a>

GeorgeGydayGeorgeGyday2019/01/16 08:03Elton John is my favourite piano musician of all time. Elton fans, let's unite at https://www.facebook.com/Elton-John-Tour-Tickets-Concerts-219000645159063/! Full list of Elton John Concerts in the USA and Canada!

bbtagictbbtagict2019/01/19 06:34[url=http://viagrafa.com/]best places to buy generic viagra[/url] uk viagra <a href="http://viagrafa.com/">is there a generic for viagra</a>

nrhBreednrhBreed2019/01/19 08:40[url=http://cialisfw.com/]buying cialis online usa[/url] cialis tadalafil <a href="http://cialisfw.com/">cialis online pharmacy</a>

nnqOvapennqOvape2019/01/19 09:30[url=http://www.viagraid.com/]buy viagra and cialis online[/url] female viagra pill <a href="http://www.viagraid.com/">best place to buy viagra online</a>

MoviEvifeMoviEvife2019/01/19 14:45Showbox is a famous app for an Android device. It also works for Mac. [url=http://favilla1479.tumblr.com/]http://favilla1479.tumblr.com/[/url]

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20151224
 |