sobota, 21 maja 2016

Sztuczna inteligencja

Póki co gra posiada LAN dzięki któremu można grać z drugim graczem, ale pojawia się problem, gdy drugiego gracza nie ma. Trochę głupio byłoby grać samemu ze sobą. Warto jest więc dodać do gry sztuczną inteligencję, tym bardziej że większość gier takową posiada. Samo dodanie sztucznej inteligencji nie powinno być trudne, skoro gra posiada już mechanizmy umożliwiające grę obu graczom.

Na jakiej zasadzie będzie działała sztuczna inteligencja (AI)?

AI będzie sprawdzało, jaki wpływ na przyrost punktacji obu graczy będzie miało postawienie żetonu na wybranym polu planszy, oraz będzie sprawdzało kombinacje każdego dostępnego żetonu z każdym dostępnym polem. Jeśli mamy więc planszę o wymiarach 6x6, oraz 4 żetony na ręce, to AI sprawdzi 144 różnych kombinacji ruchów i na podstawie wyników testu ustali jaki żeton użyć na jakim polu. Mimo tak obszernych danych AI nadal będzie posiadało wiele wad, oto kilka sytuacji, których AI nie będzie sprawdzało:
- jaki wpływ na nasze kolejne tury będzie miał wystawiany żeton,
- czy wykonanie ruchu spowoduje utratę szansy na tymczasową premię (którą zamiast nas otrzymałby przeciwnik wykonując inny ruch),
- czy wykonanie innego ruchu nie doprowadziłoby do natychmiastowej wygranej (jeśli do wygranej brakuje nam niewiele punktów),
- czy wykonanie innego ruchu nie uniemożliwiłoby przeciwnikowi natychmiastowej wygranej (jeśli do wygranej brakuje jemu niewielu punktów),
- jakie ruchy u(nie)możliwi użycie żetonu (przykładowo usunięcie jakiegoś żetonu z planszy może pozwolić przeciwnikowi wykonać bardziej korzystny ruch).

Pełna lista takich sytuacji jest oczywiście większa i dodatkowo będzie rosła wraz z każdym nowym rodzajem żetonu lub umiejętności. Wady AI sprawiają, że żywy gracz jest w stanie wygrać z komputerem, a dostrzegając błędy AI sam będzie mógł szybciej nauczyć się unikać. Oczywiście AI można rozbudowywać w taki sposób, aby popełniało coraz mniej błędów i dzięki temu moglibyśmy stworzyć nawet kilka poziomów AI, dzięki czemu gracz będzie mógł wybrać godnego sobie przeciwnika bez względu na swój poziom.

Warto jednak zauważyć, że im więcej sytuacji będzie sprawdzało AI, tym więcej operacji będzie musiał wykonać serwer. Jeśli założymy, że sprawdzenie ruchu wymaga wykonanie n operacji, to sprawdzenie wszystkich możliwych turów w jednej turze wymagałoby zaledwie 144 * n operacji, co zajmie sprzętowi malutki ułamek sekundy. Problem pojawia się wtedy, gdy chcemy uwzględnić znacznie większą liczbę tur i np. wybrać ruch który byłby najlepszy przewidując jego wpływ na tą turę oraz 3 kolejne, wtedy liczba operacji wzrosłaby do 144^4 * n, co prawdopodobnie zajęłoby przeciętnemu sprzętowi co najmniej kilkadziesiąt minut. Oczywiście są pewne metody, które pozwalają tą liczbę zminimalizować, ale póki co się tym nie zajmujemy - na razie chcemy mieć jakiegokolwiek przeciwnika, czyli jakiekolwiek AI.

Przy programowaniu AI zachodzi jeszcze jeden drobny problem - zawsze działa zgodnie z algorytmem, co prowadzi do dużej przewidywalności. Gdy gramy z jakimś graczem kilka razy pod rząd, to zwykle staramy się unikać błędów które ostatnio wykorzystał przeciwnik. Nasz styl gry zmienia się też w zależności od jego taktyki. Sprawia to, że jeśli gramy z żywym nawet kilka razy pod rząd, to za każdym razem rozgrywka jest na swój sposób unikatowa. Jeśli AI nie będzie posiadało tego typu unikalności, to stanie się zbyt przewidywalne i nudne. Aby tego uniknąć, można zastosować 2 rozwiązania:
- Zaprogramowanie kilku zupełnie innych stylów gry które będą zmieniały się z każdym kolejnym meczem lub w trakcie meczu.
- Zaprogramowanie AI tak, aby jego zachowanie było częściowo losowe.
Postawię na drugą opcję, choć może w przyszłości nawet połączę obie.

Skrypt

W skrypcie AI pierwszą wykonaną rzeczą będzie uporządkowanie pól na planszy i kart w losowej kolejności, co sprawi, że AI będzie zachowywało się nieschematycznie. Jeśli jakaś opcja będzie najbardziej opłacalna, to oczywiście zostanie wybrana, ale jeśli będzie remisowała opłacalnością, to będzie wybierana ta z największym losowym numerem.

Najpierw inicjalizuję zmienne:

 int MaxC = GameData.HandSize;
 int SizeX = GameData.MapSizeX;
 int SizeY = GameData.MapSizeY;
 int SizePow = SizeX * SizeY;
 int [] RNG = new int [SizePow];
 int [,] RNGOrder = new int [SizeX, SizeY];
 int [] RNGCardOrder = new int [MaxC];

Zmienne te będą przechowywać nieco skracać nasze funkcje, oraz będą zawierały informacje o tym w jakiej kolejności mają być przeglądane pola/karty. Przypisanie tablicą losowych wartości z jakiegoś zakresu bez powtórzeń jest proste - wystarczy wszystkim elementom tablicy przypisać kolejne liczby, a następnie wystarczy użyć wbudowanej funkcji sortującej:

 for (int x = 0; x < SizePow; x++) {
  RNG [x] = x;
 }
 Array.Sort (RNG);
 for (int x = 0; x < MaxC; x++) {
  RNGCardOrder [x] = x;
 }

 Array.Sort (RNGCardOrder);

Warto tu jednak zauważyć, że tablica z rozmiarem planszy jest przedstawiona jako tablica jednowymiarowa, a do zapisu planszy wszędzie używałem tablicy dwuwymiarowej. Dlatego uzyskane wartości wystarczy przepisać do dwuwymiarowej tablicy.

 for (int x = 0; x < SizeX; x++) {
  for (int y = 0; y < SizeY; y++) {
   RNGOrder [x, y] = RNG [x * SizeY + y];
  }

 }

Teraz deklarujemy zestaw zmiennych do przechowywania informacji o dotychczas najlepszym ruchu.

 int BestValue = -100;
 int BestC = 0;
 int BestX = 0;

 int BestY = 0;

I przechodzimy do analizy każdej kombinacji pól:

for (int c = 0; c < MaxC; c++) { // Sprawdzenie każdej karty
 int Card = RNGCardOrder [c]; // Aby skrócić zapis
 for (int x = 0; x < SizeX; x++) { // Sprawdzenie każdej kolumny planszy
  for (int y = 0; y < SizeY; y++) { // Sprawdzenie każdego wiersza planszy
   if (!SGetTokenExist (x, y)) { // Sprawdzenie, czy pole jest wolne
    int TempValue = TokenValue (Card, PNumber); // Wartość ruchu
    // Uwzględnienie siły umiejętności
    for (int z = 0; z < AbilitySize (Card, PNumber); z++) { // Sprawdzenie każdego pola na które wpływa umiejętność
     int cx = x + AbilityX (Card, z, PNumber);
     int cy = y + AbilityY (Card, z, PNumber);
     if (CheckWithMap (cx, cy)) { // Sprawdzenie czy nie wyszliśmy poza planszę
      switch (AbilityType (Card, PNumber)) { // Wybranie metody sprawdzania efektu umiejętności na podstawie jej rodzaju
       case 1: // Umiejętność typu 1
        if (SGetTokenExist (cx,cy)) { // Sprawdzenie czy na polu objętym umiejętnością jest jakiś żeton
         if (SGetTokenPlayer (cx, cy) == PNumber) { // Sprawdzenie czy żeton należy do nas
          TempValue -= 1;
         } else {
          TempValue += 1;
         }
        }
       break;
     }
   }
   if (TempValue > BestValue || (TempValue == BestValue && RNGOrder [x, y] > RNGOrder [BestX, BestY])) { // Sprawdzenie, czy jest to opcja z najwyższym numerem spośród najlepszych opcji
     BestValue = TempValue;
     BestC = Card;
     BestX = x;
     BestY = y;
     }
    }
   }
  }

 }

W tej grze będzie wiele rodzai umiejętności, a więc każdy żeton będzie sprawdzany inaczej. Fragment kodu można podzielić na wiele części i do każdej części dodać osobny warunek if, który będzie sprawdzał, czy ten fragment kodu powinien być realizowany w danej chwili. Jednak pisanie wielu niemal identycznych ifów może być z czasem irytujące, więc w takich sytuacjach warto jest korzystać z przełącznika switch, który realizuje inny fragment kodu, w zależności od wprowadzonego parametru.

Na podstawie indeksów które otrzymaliśmy w wyniku testu używamy określonej karty żetonu na określonym polu, do czego posłużyłaby ta sama funkcja, z której normalnie korzysta gracz.

Na co trzeba jeszcze zwrócić uwagę:
- Gra operuje na systemie kont, a więc powinien on być dostosowany w taki sposób, aby mogło z niego korzystać także AI i było ono możliwe do rozpoznania,
- Gra powinna pomijać tworzenie elementów graficznych dla AI (plansza, żetony, efekty itd.),- Podłączenie się AI do gry nie powinno zapisywać na kliencie informacji o jego koncie (co mogłoby spowodować np. uznanie gracza za AI),
- AI powinno wykonać ruch po każdym ruchu gracza - tutaj warto dodać jakiś warunek który sprawi, że AI nie będzie wykonywało ruchu po samym sobie.
- Ruch AI powinien być opóźniony, aby sytuacja na planszy była dla gracza bardziej czytelna.

W przyszłości AI będzie rozbudowywane i będą dodawane nowe poziomy trudności.

Brak komentarzy:

Prześlij komentarz