尋找一個更好的回溯系統

我將試着用簡單的術語來解釋這一點，因爲它可能比我發佈代碼要短。我做了遞歸解決方案的一部分，它必須通過選擇正確的「移動順序」來完成遊戲，如果它陷入僵局，那麼它必須回溯。我目前的系統通過設置一個標識符在任何未運行的移動中，以便它在回溯時不能再次使用，直到找到新的路徑/移動順序。尋找一個更好的回溯系統

但是我遇到了一個問題;遊戲可以達到只剩下兩步棋的狀態，他們都不會解決遊戲。我目前的系統基本上會使這兩個步驟不斷互換，因爲解決方案試圖發揮一個動作，發現它不起作用，然後嘗試下一步。我相信我的問題是我重置我的標識符，告訴解決方案在每次移動時都不要使用移動，但我不確定我會如何設置它。

讓我知道你是否需要任何進一步的信息或有任何見解。謝謝！

2012-02-12 Sam

爲什麼你需要重置任何東西？檢查移動是否被標記，如果沒有 - 標記並嘗試。重置位置在哪裏？ – 2012-02-12 04:18:34

@ n.m。目前它在找到移動之後重置，因爲之前移動過的已移動的標記可能需要再次使用（如果許多移動被回溯）。因此，大部分時間內服務它是有目的的，但它不起作用在這個特殊的例子中。 – Sam 2012-02-12 04:34:33

如果同一舉動可能導致兩種不同的結果，取決於你在遊戲中的位置，那麼首先跟蹤移動的點是什麼？尋找具有穩定意義的東西，無論是移動，定位，兩者的結合，無論 - 並追蹤它。 – 2012-02-12 05:40:36

我不確定你所描述的遊戲的性質，還有一些信息可能有助於確定一種更好的方法讓你遵循。我在主題中看到了你的評論，你認爲這個索引在發現新動作後重置。這聽起來不太好。我相信你必須解決這個問題，因爲正如你剛剛看到的那樣，有些情況下它會失敗，我們不能有一個只能有條件地運行的算法。

你描述的問題聽起來像一個遊戲樹？正確？如果是這樣的話，爲什麼不把你對問題的描述改爲遊戲樹，並且假設遊戲是敵對的，就使用一種經過證明的遊戲樹搜索算法，如Alpha-Beta Pruning？

2012-02-12 04:50:36 Lefteris

回答