巨大なゲームツリーを歩く

Question

私はゲームツリー全体が歩くには大きすぎます。

時間制限または深さ制限に達するまでツリーを評価する関数を作成するにはどうすればよいですか？

Answer 1

もう少し詳細があると思います。また、2つの全く別の問題を提起します。両方の制限を同時に適用したいのですか、それぞれを個別に行う方法をお探しですか？それはラフ用語で、言った：

• 制限時間：これは明確で開始する、IOを使用せずには不可能です。あなたのゲームツリーのトラバーサル機能が純粋であると仮定すると、おそらくコントロールフローを決定する一連のタイムトラッキングと絡み合わないほうがいいでしょう。ここで最も簡単なのは、トラバーサルに漸進的に良い結果をもたらすストリームを作成し、それぞれの「最良の結果」をMVarなどに置き、別のスレッドで実行することです。時間制限に達すると、スレッドを強制終了してMVarから現在の値を取得します。

• 深さ制限：これを行うための最も徹底的な方法は、幅優先検索を単純に行うことでしょうか？それが何らかの理由で実行可能でない場合、現在の深度を示すカウンタを保持し、最大に達したときには深く続かないという明らかな解決策よりも優れた解決策はないと私は考えています。これは、それぞれの再帰呼び出しがlocal (subtract 1)のようにラップされているReaderスタイルのモナドを使用して、コードが潜んでいる可能性があることに注意してください。

Answer 2

基本パッケージのtimeout機能を使用すると、一定期間後に計算を終了させることができます。最も最近の結果がMVarに格納されるように、より深い結果のストリームにtimeoutをインターリーブすることは、ハスケルにおける検索問題の比較的一般的なトリックです。

Answer 3

あなたのトラバーサルにレイジーライターモナドを使用して、改善の回答リストを生成することもできます。これで、いくつかの基準でリストから最初の「十分な」または「これまでの」結果を取得するだけで、問題をいくらか簡略化しました。その上に記載されているtimeoutトリック、またはあなたが適切と考える他のアプローチを使用することができます。