Въведение в алгоритъма Minimax с внедряване на Java

1. Общ преглед

В тази статия ще обсъдим алгоритъма Minimax и неговите приложения в AI. Тъй като това е алгоритъм за теория на игрите, ще внедрим проста игра, използвайки го.

Също така ще обсъдим предимствата на използването на алгоритъма и ще видим как той може да бъде подобрен.

2. Въведение

Minimax е алгоритъм за вземане на решения, който обикновено се използва в поетапни игри с двама играчи . Целта на алгоритъма е да намери оптималния следващ ход.

В алгоритъма единият играч се нарича максимизатор, а другият играч е минимизатор. Ако присвоим оценка на игралната дъска, единият играч се опитва да избере състояние на играта с максимален резултат, докато другият избира състояние с минимален резултат.

С други думи, на Максимизатор работи, за да получите най-висок резултат, като същевременно изпитва Minimizer получават най-ниската оценка, опитвайки се да контра ходове .

Тя се основава на концепцията за игра с нулева сума. В игра с нулева сума общият резултат на полезността се разделя между играчите. Увеличаването на резултата на един играч води до намаляване на резултата на друг играч. И така, общият резултат винаги е нула. За да спечели единият играч, другият трябва да загуби. Примери за такива игри са шах, покер, пулове, тик-так.

Интересен факт - през 1997 г. компютърът на IBM за игра на шах Deep Blue (построен с Minimax) победи Гари Каспаров (световния шампион по шах).

3. Минимакс алгоритъм

Нашата цел е да намерим най-добрия ход за играча. За целта можем просто да изберем възела с най-добър резултат за оценка. За да направим процеса по-умен, ние също можем да гледаме напред и да оценяваме ходовете на потенциалния противник.

За всеки ход можем да гледаме напред толкова ходове, колкото позволява нашата изчислителна мощ. Алгоритъмът предполага, че противникът играе оптимално.

Технически започваме с коренния възел и избираме възможно най-добрия възел. Ние оценяваме възлите въз основа на техните оценки. В нашия случай функцията за оценка може да присвоява резултати само на възлови точки (оставя). Следователно, ние рекурсивно достигаме листа с резултати и обратно разпространяваме резултатите.

Помислете за дървото на играта по-долу:

Maximizer започва с основния възел и избира хода с максималния резултат. За съжаление само листата имат оценки за оценка с тях и следователно алгоритъмът трябва да достигне рекурсивно до възлите на листата. В даденото дърво на играта в момента е ред на минимизатора да избере ход от листовите възли , така че възлите с минимални резултати (тук, възел 3 и 4) ще бъдат избрани. Той продължава да избира най-добрите възли по подобен начин, докато стигне до основния възел.

Сега нека формално дефинираме стъпките на алгоритъма:

  1. Изградете цялото дърво на играта
  2. Оценете резултатите за листата, като използвате функцията за оценка
  3. Резервни резултати от листа до корен, като се има предвид типа играч:
    • За максимален играч изберете детето с максимален резултат
    • За минимален играч изберете детето с минимален резултат
  4. В основния възел изберете възела с максимална стойност и извършете съответния ход

4. Изпълнение

Сега, нека приложим игра.

В играта имаме купчина с n брой кости . И двамата играчи трябва да вземат 1,2 или 3 кости на свой ред. Играч, който не може да вземе кости, губи играта. Всеки играч играе оптимално. Като се има предвид стойността на n , нека напишем AI.

За да дефинираме правилата на играта, ще внедрим клас GameOfBones :

class GameOfBones { static List getPossibleStates(int noOfBonesInHeap) { return IntStream.rangeClosed(1, 3).boxed() .map(i -> noOfBonesInHeap - i) .filter(newHeapCount -> newHeapCount >= 0) .collect(Collectors.toList()); } }

Освен това се нуждаем и от изпълнение за класовете Node и Tree :

public class Node { int noOfBones; boolean isMaxPlayer; int score; List children; // setters and getters } public class Tree { Node root; // setters and getters }

Сега ще приложим алгоритъма. Това изисква дърво на играта, за да гледате напред и да намерите най-добрия ход. Нека да приложим това:

public class MiniMax { Tree tree; public void constructTree(int noOfBones) { tree = new Tree(); Node root = new Node(noOfBones, true); tree.setRoot(root); constructTree(root); } private void constructTree(Node parentNode) { List listofPossibleHeaps = GameOfBones.getPossibleStates(parentNode.getNoOfBones()); boolean isChildMaxPlayer = !parentNode.isMaxPlayer(); listofPossibleHeaps.forEach(n -> { Node newNode = new Node(n, isChildMaxPlayer); parentNode.addChild(newNode); if (newNode.getNoOfBones() > 0) { constructTree(newNode); } }); } }

Сега ще приложим метода checkWin , който ще симулира разиграване, като изберете оптимални ходове и за двамата играчи. Той определя резултата на:

  • +1, ако максимайзерът спечели
  • -1, ако спечели minimizer

В checkWin ще се върне вярно, ако първият играч (в нашия случай - максимизатор) печели:

public boolean checkWin() { Node root = tree.getRoot(); checkWin(root); return root.getScore() == 1; } private void checkWin(Node node) { List children = node.getChildren(); boolean isMaxPlayer = node.isMaxPlayer(); children.forEach(child -> { if (child.getNoOfBones() == 0) { child.setScore(isMaxPlayer ? 1 : -1); } else { checkWin(child); } }); Node bestChild = findBestChild(isMaxPlayer, children); node.setScore(bestChild.getScore()); }

Тук методът findBestChild намира възела с максимален резултат, ако играчът е максимизатор. В противен случай връща детето с минималния резултат:

private Node findBestChild(boolean isMaxPlayer, List children) { Comparator byScoreComparator = Comparator.comparing(Node::getScore); return children.stream() .max(isMaxPlayer ? byScoreComparator : byScoreComparator.reversed()) .orElseThrow(NoSuchElementException::new); }

И накрая, нека приложим тестов случай с някои стойности на n (броят на костите в купчина):

@Test public void givenMiniMax_whenCheckWin_thenComputeOptimal() { miniMax.constructTree(6); boolean result = miniMax.checkWin(); assertTrue(result); miniMax.constructTree(8); result = miniMax.checkWin(); assertFalse(result); }

5. Подобрение

За повечето от проблемите не е възможно да се изгради цяло дърво на играта. На практика можем да разработим частично дърво (конструирайте дървото само до предварително определен брой нива) .

След това ще трябва да приложим функция за оценка, която трябва да може да реши колко добро е текущото състояние на играча.

Дори и да не изграждаме пълни дървесни игри, изчисляването на ходове за игри с висок фактор на разклоняване може да отнеме много време.

За щастие има опция за намиране на оптималния ход, без да се изследват всички възли на дървото на играта. Можем да пропуснем някои клонове, като следваме някои правила и това няма да повлияе на крайния резултат. Този процес се нарича резитба . Алфа-бета резитбата е преобладаващ вариант на алгоритъма на минимакс.

6. Заключение

Алгоритъмът Minimax е един от най-популярните алгоритми за компютърни настолни игри. Той се прилага широко на свой ред базирани игри. Може да е добър избор, когато играчите имат пълна информация за играта.

Може да не е най-добрият избор за игрите с изключително висок коефициент на разклонение (например игра на GO). Въпреки това, при правилна реализация, това може да бъде доста умен AI.

Както винаги, пълният код на алгоритъма може да бъде намерен в GitHub.