エイリアンはまだ発見されていませんが、Seti @ homeは大規模な分散コンピューティングの可能性を非常にうまく実証しています。 BOINCのようなプロジェクトは、生物学、医学、物理学などの他の分野にも同様の取り組みを広げています。
先週末、 Joshfireチーム（ Thomas 、 Nathan 、 Michael、およびI ）が48時間のNode Knockoutコンテストに参加しました。 ルールは単純でした。週末に最も忙しいものをエンコードし、サーバーサイドJavaScriptを使用します。
JavaScriptは古くて魅力的なテクノロジーであり、 パフォーマンス 、 サーバーエンジン 、およびHTML5 が提供する多くの新 機能により生まれ変わりました。 さらに、 最も一般的な言語です。 Webに接続されたコンピューターは、ブラウザーにアドレスを入力するか、コマンドラインからスクリプトを実行するだけで、JavaScriptコードを簡単に実行できます。
Webページにアクセスするだけで参加できる大規模な分散コンピューティングプロジェクトを構築するために、その普及率と高性能ノードを使用することにしました。 エイリアンの検索はすぐに削除されました。 手元にレーダーシステムはありませんでした。 したがって、問題をより簡単に解決するためにチェスを始めました。
私たちの誰もが優れたチェスプレイヤーではありませんが、ギネスブックでは2070ノードからなる最大のチェスAIについて言及し、彼を倒すことができると決めました。 それでChess @ homeプロジェクトが生まれました。
48時間後、プロトタイプにはまだいくつかのバグがありましたが、完全にプレイ可能な状態で、次のようになりました。
分散チェスAIの問題
調査を開始して、次の問題領域を特定しました。
遅延 標準的なトーナメントルール（ゲームごとに90分）に従うことを望んでいたため、1分あたりの平均移動を計算する必要が生じました。 さらに、ウェブ上のプレイヤーは間違いなく短いレスポンスを好むでしょう。そして、できるだけ短くするという目標を設定しました。
計算の時間枠が小さいため、主に高出力向けに最適化されているほとんどの既存の分散コンピューティングインフラストラクチャでうまくプレイできません。 ほぼリアルタイムの新しいインフラストラクチャを構築する必要がありました。 Websocketはソリューションの一部として頼みます。
並行性 応答時間の最適化とは、各計算機に処理するために少量を送信する必要があることを意味します。 そのため、コード計算を何千もの小さな断片に分割する方法を考え出す必要がありました。
詳細を説明しませんが、ほとんどのチェスAIで使用されるミニマックスアルゴリズムはツリートラバーサルに基づいており、本質的に、 アルファ-ベータクリッピングを使用する場合は一貫しています。 次のことに留意しながら、並列化に適したさまざまなアルゴリズムを検討しました。
- 電卓は一般的な変数に特に依存するべきではありません Webソケットは、クライアントとクライアントのスキームに従って機能しません（サーバーを介してデータを実行すると、スケーリングが妨げられます）。
- 各移動の計算は、数千の小さなタスクに分割する必要があります。
APHID （シンプル、現在のギネス世界記録チャンピオンであるChessBrain.netで使用）とYBWCバリエーション（より難しいがより効率的）の2つの潜在的な候補が見つかりました。 48時間のコーディング制限があるため、APHIDから始めることにしました。
JavaScriptのパフォーマンス 。 最もクールなチェスAIは、最先端の鉄を使用して、1秒間に最大1500万ツリーノード（NPS = 1秒あたりのノード）を移動できます。 JavaScriptをベースにしたオープンソースのチェスAIであるGarboChessを使用しました。そのパフォーマンスは、最新のMacbook ProでのChromeの100k NPSです。 150の係数は、特に48時間後には、1台のコンピューターだけを使用して私たちを打つコードをプロファイリングおよび最適化する時間がないため、あまり私たちを混乱させませんでした。
参考までに、 Deep Blueは200m NPSの速度でKasparovを倒しました。これは一般に、2070ノードのターゲットで理論的に達成可能でした。
フォールトトレランス / セキュリティ 。 サードパーティのコンピューターでJavaScriptを実行すると、 アクセシビリティ （ユーザーはいつでもページを離れることができます）と信頼性 （攻撃者は間違った結果をすり抜けることができ、AIは愚かな動きをする）という2つの理由で結果を信頼できなくなります。
第一の実施形態では信頼性を扱わないことにしましたが、可用性は重要なままであったため、アルゴリズムは決定木の明白な動きを見逃さずに時間通りに完了しました。 MangoDBで計算タスクのFIFOキューを設定し、5秒のタイムアウトを設定して、別の計算機が最初のタスクから応答がない場合にタスクを取得して処理できるようにしました。
48時間でのプロトタイプの実装
プロトタイプの図を次に示します。
主なコンポーネントを分析しましょう。
- dnode 双方向の非同期リモートメソッド呼び出し用のNode.jsライブラリ。 ソケットおよびWebソケット（ socket.ioを使用）のスタイルでトランスポートを提供するため、システムプロセスが相互に通信し、同じインターフェイスを使用してブラウザーで実行されているプロセスと通信できます。 ほとんどすべてのネットワークインタラクションに使用しました。
- Web Workers （Webコンピューター）。 ユーザーインターフェイスがハングしないように、実行を単一のスクリプトに制限するシングルスレッド（シングルスレッド）JavaScript環境。 Web Workersを使用すると、大きなランタイムでスクリプトを実行して、計算が必要なタスクを解決できますが、インターフェイスや他のユーザー操作スクリプトをブロックすることはできません。 サーバー側では、 node-webworker （Node用のWeb Workerの実装）を使用したため、AIと通信するための単一のインターフェイスがありました。
- MongoDB 。 MongoHQはNode Knockoutを後援し、MongoDBの既製のインスタンスを使用して、ゲームの状態と潜在的に大きなポジションキャッシュを保存することにしました。
- ノード アーキテクチャの中心的なリンクであるNodeは、迅速な開発（サーバーとクライアントの両方で同じコード）と高性能（そのノンブロッキングI / Oパラダイムにより、その競争力と速度が確認されています）の両方を備えています。
- サーバー上のローカルAI。 この場所は明らかにスケーリングされていませんが、それにもかかわらず、主にクライアントに作業を分散するためにAPHIDを最初に小さなツリーで構築する必要があるため、サーバーでいくつかのAI呼び出しを行う必要があります。 おそらく将来的には削除するでしょう。
この実装では改善すべき点がありますが、忘れないでください-すべてが48時間で完了しました。 ただし、ブラウザーとサーバーの両方でWeb WorkersでAIを実行することは、引き続き主要なアイデアです。
今後の予定
ウィジェットの倫理 。 通常、他の人のコンピューティングパワーを使用するには、所有者の同意が必要です。人々はSETI @ homeまたはBOINCソフトウェアをインストールして、プロセッサにアクセスできるようにします。 JavaScriptを使用すると、明示的な許可なしに他の人のプロセッサを使用できます。ウィジェットを使用してページに移動するだけでよくありません。
ユーザーの同意を得ることにしましたが、トラフィックの多い他の人のサイトにウィジェットをインストールすることは、2070ノードの目標に対する未解決の主なタスクであり、発生する可能性のある異議や不満に対応するために最善を尽くします。
たとえば、「パブリック」リソースの使用を計画しているため、結果をできるだけオープンにしておく必要があります。 コードはGitHubで開いたままになります。 また、チェスAIのAPIを開く予定です。
AIの改善 。 残っているインターフェースのバグをいくつか見つけた後、次の領域でAIの最適化を続けます。
- 並行性の改善 ：計算機間でタスクをより柔軟に分散するために、APHIDからYBWCに切り替える予定です。 JavaScriptのパフォーマンスが低いため、これは特に重要です。大規模に補正する必要があります。
- 単体テスト ：すでに数百のポジションの単体テストを実行しましたが、ネットワーク上にはまだ多くのものがあり、 STSの方法でそれらを統合します。
- アルゴリズムの改善：GarboChessは既にアルファ-ベータクリッピングを実装し、ゼロウィンドウを決定し、 落ち着いた位置や他のいくつかの機能を見つけてい ますが、評価機能とAIのいくつかの修正を改善することで、より良いプレイが可能になります。
時間Xを計画します。 AIが十分に強くなったら、本物のフランスのグランドマスターおよびギネスの代表者に電話して、最も刺激的なチェスゲームを実施します！
多くの人々を調整して、同時にマトリックスに接続する必要があります。 よくアクセスするいくつかのサイトにウィジェットをインストールすると役立ちます。 また、チェス@ homeでゲームを観て、計算に参加できるようにしたいと考えています。
最大人数の人々をつなぐ方法についてのアイデアがあれば、教えてください！ また、上記のすべてに対処できる有能なJavaScript開発者も探しています。
私たちを助けたいなら、 現在のタスクのリストを見るか、 Chess @ homeで新しいタスクを見つけてください。 マトリックスとの戦いに頑張ってください！
PS 完全性のカテゴリでノードノックアウトを獲得しました。
Habrを使用できない場合：
- 翻訳済み： 未接続
- 作詞家： Sylvain Zimmer
- オリジナル： チェス@ホーム：史上最大のチェスAIを構築