問題タブ [alpha-beta-pruning]

私は最近、Connect 4 のミニマックス アルゴリズムを実装してボットを作成しようとしました。これは、Python を使用してシンプルに保つためです (複雑になる可能性があります)。

これが私がこれまでに持っているものです：

時々、それは一種の作品です。一手一手を正しく評価しているとは思えません。私はしばらくそれをいじってみましたが、どこが間違っているのかわかりません。

どんな助けでも大歓迎です、ありがとう。

こんにちは、次のコードの例としてチェスを使用して、アルファ ベータ プルーニング アルゴリズムを理解しようとしています。

私が入手したブログへのリンクは次のとおりです: LINK (強調表示された構文が好きな場合は、リンクからコードを表示できます)

私が理解していないのは、アルファベータの剪定では、ツリーの上位に移動すると、アルファ変数とベータ変数の値が時々変化する必要があるということです。私の問題を説明する写真を添付し​​ました-手順1）、2）、および3）は理解していますが、4）の手順はわかりません。4) ステップは図のように見えるはずですが、そのステップで値が変化するコードで何が起こっているのかわかりません。私はコードを注意深くたどりましたが、何らかの理由で 4) のステップで a = 5 と b = 5 になってしまいました。

追加のアルファ ベータ プルーニング実装を備えた従来のミニマックス問題ソルバーがあります。

アルファベータ実装のない Minimax は、基本的にツリー全体の深さ優先検索を最大深さまで実行します。alpha-beta でも同じことを行っていますが、いずれにせよ悪い結果につながるいくつかの枝を剪定します。

編集: コードをさらに調べた後、コードの 1 行にバグがあり、プログラムが「チート」していくつかの動きに従わなくなりました。実際のスピードアップ係数は現在 3.6 です。皆さんの時間を無駄にして申し訳ありません.. 今日のコンピューティングにはブレークスルーがありません。:/

チェッカーのようなゲームに AI (人工知能) を実装したい

私は次のメソッドを書きました：

-方法

これは、重みでソートされたすべての有効な動きのリストを返します。重みは、動きの種類と位置に従って計算されます

-方法

移動をボードに適用し、ポーンが殺された場合は 1 を返します

-方法

ボードの以前の状態を復元します。

これはゼロサム ゲームであるため、AI はプレイヤーの色のポーンを最大化し、対戦相手のポーンを最小化する必要があります。

このための最良の方法は、アルファベータ剪定で最小最大を使用するようです。これには次の疑似コードがあります

しかし、これを自分の問題に適応させる方法がわかりません。誰かが私を助けることができますか？

編集

私はこのMinMaxを持っていますが、刈り込みはありません

アルファ ベータ プルーニングを取得するために編集する方法は?

この週末のプログラミングの楽しみは、F# で 300 行のリバーシ プログラムを作成することでした。アルファベット検索を並列化する方法を見つけるには、おそらくあと数週間かかるでしょう。実際、これはこの質問の範囲外です。

しかし、私が見つけたのは、alphabeta 関数を実装するための「純粋に機能的な」方法を思いつくことができなかったことです。つまり、可変状態はありません。

そのための良いアイデアはありますか？

私の頭に浮かんだ唯一のアイデアは、状態の変化を格納するためにアキュムレータ状態が使用される Seq.foldUntil() 関数のようなものを書くことです。そして、渡されたラムダ関数によってキャンセルできます。

多分このように見えます：

ここで、不純なアルファベット関数...

答えを待っている間に、transformWhile のアイデアを試してみることにしました。

いくつかのインタラクティブなテストで、いくつかの些細なことで機能することが示されたので、新しいバージョンの alphabeta を作成することにしました。現在は次のようになっています。

それは、関数型プログラミングのプロが行うようなものですか? または、あなたは何をしますか？

以前のブルート フォース検索は末尾再帰 (コール スタックが構築されない) でしたが、この純粋な機能バージョンは末尾再帰ではなくなりました。誰かが再び末尾再帰にする方法を見つけることができますか?

こんばんは。初めて投稿するので質問の仕方が悪くてすみません。

2 時間近くブレインストーミングを行ったが、適切な解決策が見つからないため、特定の演習に関する支援を探しています。演習は次のとおりです。特定の数のワゴンが与えられた場合、2 人の泥棒が最高の利益を求めて競争します。

最初の泥棒、たとえば A が最初に摘み取りを開始します。泥棒は、リストで現在利用可能な最初または最後のワゴンのいずれかを選択する可能性があります。次に、選択したワゴンがリストから削除され、その値がそれぞれの泥棒のカウンターに追加されます。この演習の目的は、泥棒 A が可能な限り最高の利益を得ると同時に、泥棒 B が同じことをしようとしていることを確認することです。

たとえば、次の入力があるとします。

6
10
150
3
7
9
9

これは、値が 10、150、3、7、9、および 9 のワゴンが 6 台あることを意味します。最適な戦略に従う場合、両方の泥棒が最適な戦略に従うと仮定すると、出力は 166 になります。ただし、これまでのところ、盗賊 B がどのようにプレイしても、盗賊 A が獲得できる最高の結果である 169 しか得られませんでした。

両方の泥棒がコードに関して最適な戦略に従うことを保証する方法がわかりません。考えられるすべての組み合わせをチェックする必要があると思われますが、結果を見て、どちらの泥棒が最適な戦略に従っているかを判断するにはどうすればよいでしょうか? 何か案は？

コード：

私はJavaScriptで三目並べゲームを書いています。GUI などの作業は完了しましたが、AI にはまだ問題があります。私はアルファ・ベータ・プルーンを使用して、勝利の動きを見つけます。しかし、私のコードでは、ゲームに勝てる手はありません。私は多くの調査を行いましたが、コードの何が問題なのかまだわかりません。ここで私のメインの AI 部分を見てください。私の考えは、動きを保存する 2D 配列を作成することです。1 は人間、-1 は AI、0 は空です。初期呼び出し: var test = getBestMove(-1); `

最良の移動関数を取得します。

アルファベータ検索:

私は評価関数を使用しませんでした。それがなくても、アルファ ベータ版は勝利を見つけることができるはずだと思うからです。