Minimax algoritmus v teorii her | Sada 1 (úvod)
Minimax je druh backtrackingového algoritmu, který se používá při rozhodování a teorii her k nalezení optimálního pohybu pro hráče za předpokladu, že váš soupeř také hraje optimálně. Je široce používán v tahových hrách pro dva hráče, jako jsou Tic-Tac-Toe, Backgammon, Mancala, šachy atd.
V Minimax se tito dva hráči nazývají maximalizér a minimalizátor. The maximalizátor se snaží získat co nejvyšší možné skóre minimalizátor se snaží udělat opak a získat co nejnižší skóre.
Každý stav desky má spojenou hodnotu. V daném stavu, pokud má maximalizér navrch, bude mít skóre na desce tendenci mít nějakou kladnou hodnotu. Pokud má minimalizátor v tomto stavu desky navrch, bude mít tendenci mít nějakou zápornou hodnotu. Hodnoty herního plánu se počítají pomocí nějaké heuristiky, která je jedinečná pro každý typ hry.
Příklad:
Představte si hru, která má 4 konečné stavy a cesty k dosažení konečného stavu jsou od kořene po 4 listy dokonalého binárního stromu, jak je ukázáno níže. Předpokládejme, že jste maximalizující hráč a máte první šanci se pohnout, tedy že jste u kořene a váš protivník na další úrovni. Jaký tah byste jako maximalizující hráč udělal s ohledem na to, že i váš soupeř hraje optimálně?
Vzhledem k tomu, že se jedná o algoritmus založený na backtrackingu, zkouší všechny možné pohyby, poté ustoupí a rozhodne se.
- Maximizer jde DOLEVA: Nyní jsou na řadě minimalizátory. Minimalizátor má nyní na výběr mezi 3 a 5. Jako minimalizátor si určitě vybere nejméně z obou, tedy 3
- Maximalizátor jde VPRAVO: Nyní jsou na řadě minimalizátory. Minimalizátor má nyní na výběr mezi 2 a 9. Zvolí 2, protože je to nejmenší ze dvou hodnot.
Jako maximalizér byste zvolili větší hodnotu, která je 3. Optimální pohyb pro maximalizér je tedy jít DOLEVA a optimální hodnota je 3.
Nyní strom hry vypadá takto:
Výše uvedený strom ukazuje dvě možná skóre, když maximalizér provádí pohyby doleva a doprava.
Poznámka: I když je v pravém podstromu hodnota 9, minimalizátor ji nikdy nevybere. Vždy musíme vycházet z toho, že soupeř hraje optimálně.
Níže je implementace pro totéž.
C++
// A simple C++ program to find> // maximum score that> // maximizing player can get.> #include> using> namespace> std;> // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is> // of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> int> minimax(> int> depth,> int> nodeIndex,> bool> isMax,> > int> scores[],> int> h)> {> > // Terminating condition. i.e> > // leaf node is reached> > if> (depth == h)> > return> scores[nodeIndex];> > // If current move is maximizer,> > // find the maximum attainable> > // value> > if> (isMax)> > return> max(minimax(depth+1, nodeIndex*2,> false> , scores, h),> > minimax(depth+1, nodeIndex*2 + 1,> false> , scores, h));> > // Else (If current move is Minimizer), find the minimum> > // attainable value> > else> > return> min(minimax(depth+1, nodeIndex*2,> true> , scores, h),> > minimax(depth+1, nodeIndex*2 + 1,> true> , scores, h));> }> // A utility function to find Log n in base 2> int> log2(> int> n)> {> > return> (n==1)? 0 : 1 + log2(n/2);> }> // Driver code> int> main()> {> > // The number of elements in scores must be> > // a power of 2.> > int> scores[] = {3, 5, 2, 9, 12, 5, 23, 23};> > int> n => sizeof> (scores)/> sizeof> (scores[0]);> > int> h = log2(n);> > int> res = minimax(0, 0,> true> , scores, h);> > cout < <> 'The optimal value is : '> < < res < < endl;> > return> 0;> }> |
Jáva
// A simple java program to find maximum score that> // maximizing player can get.> import> java.io.*;> class> GFG {> > // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> > static> int> minimax(> int> depth,> int> nodeIndex,> boolean> isMax,> > int> scores[],> int> h)> {> > // Terminating condition. i.e leaf node is reached> > if> (depth == h)> > return> scores[nodeIndex];> > // If current move is maximizer, find the maximum attainable> > // value> > if> (isMax)> > return> Math.max(minimax(depth+> 1> , nodeIndex*> 2> ,> false> , scores, h),> > minimax(depth+> 1> , nodeIndex*> 2> +> 1> ,> false> , scores, h));> > // Else (If current move is Minimizer), find the minimum> > // attainable value> > else> > return> Math.min(minimax(depth+> 1> , nodeIndex*> 2> ,> true> , scores, h),> > minimax(depth+> 1> , nodeIndex*> 2> +> 1> ,> true> , scores, h));> }> // A utility function to find Log n in base 2> > static> int> log2(> int> n)> {> return> (n==> 1> )?> 0> :> 1> + log2(n/> 2> );> }> // Driver code> > public> static> void> main (String[] args) {> > // The number of elements in scores must be> > // a power of 2.> > int> scores[] = {> 3> ,> 5> ,> 2> ,> 9> ,> 12> ,> 5> ,> 23> ,> 23> };> > int> n = scores.length;> > int> h = log2(n);> > int> res = minimax(> 0> ,> 0> ,> true> , scores, h);> > System.out.println(> 'The optimal value is : '> +res);> > > }> }> // This code is contributed by vt_m> |
C#
// A simple C# program to find maximum score that> // maximizing player can get.> using> System;> public> class> GFG> {> > // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> static> int> minimax(> int> depth,> int> nodeIndex,> bool> isMax,> > int> []scores,> int> h)> {> > // Terminating condition. i.e leaf node is reached> > if> (depth == h)> > return> scores[nodeIndex];> > // If current move is maximizer, find the maximum attainable> > // value> > if> (isMax)> > return> Math.Max(minimax(depth+1, nodeIndex*2,> false> , scores, h),> > minimax(depth+1, nodeIndex*2 + 1,> false> , scores, h));> > // Else (If current move is Minimizer), find the minimum> > // attainable value> > else> > return> Math.Min(minimax(depth+1, nodeIndex*2,> true> , scores, h),> > minimax(depth+1, nodeIndex*2 + 1,> true> , scores, h));> }> // A utility function to find Log n in base 2> static> int> log2(> int> n)> {> > return> (n==1)? 0 : 1 + log2(n/2);> }> // Driver code> static> public> void> Main ()> {> > // The number of elements in scores must be> > // a power of 2.> > int> []scores = {3, 5, 2, 9, 12, 5, 23, 23};> > int> n = scores.Length;> > int> h = log2(n);> > int> res = minimax(0, 0,> true> , scores, h);> > Console.WriteLine(> 'The optimal value is : '> +res);> > }> }> // This code is contributed by ajit.> |
Python3
# A simple Python3 program to find> # maximum score that> # maximizing player can get> import> math> def> minimax (curDepth, nodeIndex,> > maxTurn, scores,> > targetDepth):> > # base case : targetDepth reached> > if> (curDepth> => => targetDepth):> > return> scores[nodeIndex]> > > if> (maxTurn):> > return> max> (minimax(curDepth> +> 1> , nodeIndex> *> 2> ,> > False> , scores, targetDepth),> > minimax(curDepth> +> 1> , nodeIndex> *> 2> +> 1> ,> > False> , scores, targetDepth))> > > else> :> > return> min> (minimax(curDepth> +> 1> , nodeIndex> *> 2> ,> > True> , scores, targetDepth),> > minimax(curDepth> +> 1> , nodeIndex> *> 2> +> 1> ,> > True> , scores, targetDepth))> > # Driver code> scores> => [> 3> ,> 5> ,> 2> ,> 9> ,> 12> ,> 5> ,> 23> ,> 23> ]> treeDepth> => math.log(> len> (scores),> 2> )> print> (> 'The optimal value is : '> , end> => '')> print> (minimax(> 0> ,> 0> ,> True> , scores, treeDepth))> # This code is contributed> # by rootshadow> |
Javascript
> // Javascript program to find maximum score that> // maximizing player can get.> // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> > function> minimax(depth, nodeIndex, isMax,> > scores, h)> {> > // Terminating condition. i.e leaf node is reached> > if> (depth == h)> > return> scores[nodeIndex];> > > // If current move is maximizer, find the maximum attainable> > // value> > if> (isMax)> > return> Math.max(minimax(depth+1, nodeIndex*2,> false> , scores, h),> > minimax(depth+1, nodeIndex*2 + 1,> false> , scores, h));> > > // Else (If current move is Minimizer), find the minimum> > // attainable value> > else> > return> Math.min(minimax(depth+1, nodeIndex*2,> true> , scores, h),> > minimax(depth+1, nodeIndex*2 + 1,> true> , scores, h));> }> > // A utility function to find Log n in base 2> > function> log2(n)> {> return> (n==1)? 0 : 1 + log2(n/2);> }> > // Driver Code> > // The number of elements in scores must be> > // a power of 2.> > let scores = [3, 5, 2, 9, 12, 5, 23, 23];> > let n = scores.length;> > let h = log2(n);> > let res = minimax(0, 0,> true> , scores, h);> > document.write(> 'The optimal value is : '> +res);> > > > |
Výstup:
The optimal value is: 12
Časová složitost: O(b^d) b je faktor větvení a d je počet hloubky nebo vrstvy grafu nebo stromu.
Prostorová složitost: O(bd) kde b je faktor větvení do d je maximální hloubka stromu podobná DFS.
Myšlenkou tohoto článku je představit Minimax na jednoduchém příkladu.
- Ve výše uvedeném příkladu má hráč pouze dvě možnosti. Obecně může být více možností. V takovém případě musíme opakovat všechny možné tahy a najít maximum/minimum. Například v Tic-Tac-Toe může první hráč provést 9 možných tahů.
- Ve výše uvedeném příkladu jsou nám přidělena skóre (listy stromu hry). Pro typickou hru musíme tyto hodnoty odvodit
Brzy pokryjeme Tic Tac Toe algoritmem Minimax.
K tomuto článku přispěl Akshay L. Aradhya.
