問題タブ [negamax]

質問する

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

51 問題
Newest
Active
Bountied
318
Unanswered
0 投票する
2 に答える
315 参照

haskell - ゲーム ツリー (潜在的に無限のバラの木) の繰り返されるサブツリーを記憶する方法は?

Haskell でNegamaxアルゴリズムを実装しようとしています。

このために、私はゲームが取り得る将来の可能性をバラの木 ( Data.Tree.Forest (depth, move, position)) で表しています。ただし、多くの場合、2 つの異なる一連の移動で到達できる位置があります。繰り返される位置 (のサブツリー) を再評価するのは無駄です (そしてすぐに非常に遅くなります)。

これが私がこれまでに試したことです：

  • Tying the Knotのバリアントを実装して、共通のサブ結果を共有します。ただし、（潜在的に無限の）リストの結び目を結ぶことについての説明しか見つけることができず、サブツリーの再利用については何も見つかりませんでした。

  • 私が検討した別のアプローチは、Stateモナド内にツリーを構築することでした。保持する状態は、Map (depth, position) (Forest (depth, move, position))明示的なメモ化を実行することですが、これも適切に設定できていません。

どちらのアプローチにも、コアカーシブな方法でしかゲーム ツリーを構築できないという問題があると思います。リーフからルートまでツリーを構築するのではなく、ルートから下に向かって (潜在的に無限の) ツリーを遅延して構築します。

編集:私が現在使用しているコードの例を示すには(遅すぎます):

( TypeFamilies は、各Game実装が独自の a の概念を持つことを可能にするために使用され、その後、 FlexibleContexts は実装するMoveために強制する必要があります。Move sOrd


12345678910