Algorytm Minimax

0

Witam, to moja kolejna próba do tego algorytmu. Rozumiem jego mniej więcej przesłania. Ale niestety nie rozumiem jak go napisać. Czy są tutaj osoby mądre, które umieją to napisać? Lub wytłumaczyć tak, żebym sam to napisał?

1

http://wazniak.mimuw.edu.pl/i[...]na_inteligencja/SI_Modu%C5%828-_Gry_dwuosobowe#Strategie_minimaksowe

0

Mimo, że widzę dalej nie rozumiem. Mniej więcej rozumiem idee tego algorytmu. Ale nie wiem jak zapisać raz wygenerowany minimax i przeglądać dane odnogi do odnalezienia najlepszej drogi.

0

Z tego co zrozumiałem, miałem ten algorytm raz wykonać. A później podczas dalszej akcji w kółko i krzyżyk, przeglądać tylko te odnogi.
Mój problem polega na tym, że nie wiem jak skojarzyć tablicę dwuelementową do tego algorytmu oraz jak przeglądać dane odnogi, względem obecnej gry.

1

Nie zdefiniowałeś nawet konkretnego problemu, który chcesz rozwiązać.
Zazwyczaj algorytm Mimimax stosuje się w sytuacji, gdy np. mamy 2 macierze zysków i strat dla dwóch graczy i zakładamy, że gracze nie znają nawzajem swoich macierzy i strategii.
Zyski i straty mogą być zdefiniowane jako liczby całkowite. Im większa liczba, tym większy zysk. Liczby mogą być też ujemne. Są to wtedy straty.
Algorym Mimimax jest strategią bezpieczną i wykorzystuje się go po to, żeby uzyskać jak najlepszy wynik w przypadku wystąpienia najgorszej sytuacji (gdy przeciwnik wykona najbardziej niekorzystny dla nas ruch).

Załóżmy, że mamy dwie macierze: A i B (dla dwóch graczy: A i B). Zamiast liczb podam zmienne, ponieważ liczby musiałyby być sensowne, aby uzyskać sensowny wynik.
Jeśli chcesz, możesz sobie tam powstawiać jakieś liczby i przeprowadzić symulację. Mogę ewentualnie poszukać jakiegoś konkretnego przykładu i go tu zamieścić.

macierz A:

a | b | c
d | d | e
f | g | h

macierz B:

i | j | k
l | m | n
o | p | q

Algorytm przebiega w sposób następujący:

  1. Sprawdzamy macierz A
    1. Znajdujemy najmniejsze wartości w każdym wierszu macierzy A
    2. Z wartości znalezionych w poprzednim punkcie wybieramy największą wartość i zapamiętujemy numer wiersza (zapiszmy go w zmiennej: row)
  2. Sprawdzamy macierz B
    1. Znajdujemy najmniejsze wartości w każdej kolumnie macierzy B
    2. Z wartości znalezionych w poprzednim punkcie wybieramy największą wartość i zapamiętujemy numer kolumny (zapiszmy go w zmiennej: column)
  3. Wypisujemy znalezione wartości minimax
    1. Wartość minimax dla gracza A, to wartość w komórce: A(row, column)
    2. Wartość minimax dla gracza B, to wartość w komórce: B(row, column)
  4. Koniec algorytmu.
0

@wiciu Przepraszam. Próbuje napisać sztuczną inteligencje dla Kołka i krzyżyka. I za pomocą algorytmu Minimax, próbuje to zrobić żeby działało lepiej niż na ifach.
Tzn. zrobiłem wersje ifową, tzn sprawdza każdy warunek w tablicy 3x3 i sprawdza czy gdzieś użytkownik ma postawione 2 znaki. Jeśli tak to ma postawić na tym trzecim, jeśli nie ma to zrandomizować sobie pole, gdzie ma postawić.
Mam nadzieję, że tym razem lepiej napisałem. Próbowałem sam zaimplementować ten algorytm, ale moje próby wyszły na marne. To jest to co próbowałem stworzyć: http://ideone.com/wJV8Du
Jak widać, w programie mam problem z dalszą implementacją a tzn rekurencją, która by symulowała dalsze możliwości na przedstawionej tablicy.

0

Wprowadzenie algorytmu minimax do gomoku

tutaj był dyskutowany podobny problem ale dla gomoku.

0

Witam, dziękuje za odpowiedź. Ale szczerze mówiąc moje rozumowanie Javy, nie jest na tyle wysokie, żeby coś wynieść z tego wątku chociaż walczyłem.
Między czasie zdążyłem napisać funkcję, która oblicza wszystkie możliwe ruchy dla danego chara, który przedstawia ogólną sytuację na planszy i zwraca klawisz, który powinien wcisnąć. Dla osiągnięcia najszybszego zwycięstwa, tylko gdzieś się zgubiłem.
Mam ogólne takie wrażenie, że straciłem ogólny sens tego algorytmu. Czy ktoś może wskazać błędy gdzie robię? O czym zapomniałem?
Ogólnie tutaj jest kod, ale wydaje mi się, ze jest źle. http://ideone.com/3l9bl3

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0