2

動的計画法でドットゲームの変種を解こうとしています。

通常のドットゲームは、ドットのラインでプレイされます。各プレーヤーは、ラインのそれぞれの端で1つまたは2つのドットを取り、ドットがないままになっている人が勝ちます。

このバージョンのゲームでは、各ドットの値が異なります。各プレイヤーは交互にターンし、ラインの両端でいずれかのドットを取ります。動的計画法を使用して、最初のプレーヤーが勝つことが保証されている最大量を見つける方法を考え出したいです。

私はこれについて頭を抱えて、解決策の繰り返しを書き込もうとして問題を抱えています。どんな助けでもありがたいです、ありがとう!

4

1 に答える 1

4

このサイトを見てください:http://people.csail.mit.edu/bdean/6.046/dp/、特に問題番号10:

ゲームの最適な戦略。値v(1)... v(n)のn個のコインの行を考えます。ここでnは偶数です。順番を変えて対戦相手と対戦します。各ターンで、プレイヤーは列から最初または最後のコインを選択し、それを列から永久に取り除き、コインの価値を受け取ります。私たちが最初に移動した場合に確実に勝つことができる最大の可能な金額を決定します。

私があなたの投稿を正しく読んでいるなら、それはまさにあなたが望むものです。解決策は非常に単純で、私の意見では非常によく説明されています。

于 2010-05-04T09:24:55.213 に答える