Minimax/Alpha-Beta修剪如何區分較短路徑的優先級？

我正在研究一個簡單的井字遊戲問題，我正在努力理解Minimax算法的工作原理。Minimax/Alpha-Beta修剪如何區分較短路徑的優先級？

如果我使用X win的效用函數1，O win爲-1，遊戲進行中爲0，那麼我不明白該算法如何優先考慮較短的解決方案。據我所知，它首先進入最深的節點，如果事件不是最短路徑，但會導致可能的勝利，那麼它會選擇它。

讓我在示例中解釋。這裏的董事會和X轉的狀態（符號爲https://www.hackerrank.com/challenges/tic-tac-toe）：

OX_ 
_X_ 
__O

如果我們從左上角位置搜索到右向下，則算法會發現，如果我們把X中的位置（ 0，2）因爲它導致了不可避免的贏下一回合：

OXX 
_X_ 
__O

然而，一個更明智的選擇應該是（2,1），並立即中獎位置：

OX_ 
_X_ 
_XO

我沒有看到Minimax o怎麼樣r Alpha-Beta修剪會優先考慮這種行爲。

所以我的問題是如果我正確地理解它，以及如何改善它。

來源

2016-12-07 Soid

更改您的效用函數以考慮圈數。 – Bergi

而不是1爲X贏，使用N爲X贏，其中N是板上留下的空白空間的數量。這樣，選項（2,1）的值爲4，而選項（0,2）的值爲2（因爲只有2個空白空間纔會獲勝）。 – user3386109

Tic Tac Toe的Minimax幾乎沒有可能的數值估價：贏，輸，抽。 Minimax算法分配所有玩家位置可以通過其他玩家的後續移動而最小化的所有方式的最大值。下一步的勝利將被賦予Infinity，這是明確的選擇。否則，在井字遊戲中，除了一些特殊情況，例如在下一步移動中獲勝或者能夠創建一個分支（導致下一步之後的移動取得一定的勝利），它將優先進行抽獎。

Alpha Beta修剪是一種優化方法，它可以避免探索搜索樹的各個部分，因爲可以顯示該部分的任何部分會產生比已經找到的結果更差的結果;例如，一個完整的節點勘探產生潛在的吸引力，另一個節點的葉子表現出損失;在探索後一個節點的其他孩子時是沒有意義的（除非你認爲另一個玩家不會總是發揮最好的作用）。您可能會發現此鏈接有幫助：https://www.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html

來源

2016-12-07 05:34:49

Minimax/Alpha-Beta修剪如何區分較短路徑的優先級？

回答

相關問題