| Start | Super Packer | Atari Graphics Studio / AGS | Graph2Font / G2F | Mads |   http://madteam.atari8.info  
SKŁAD GRUPY
PRODUKCJE
scena
gry
użytki
vbxe
SPRZĘT
Sio2SD/Pajero
Sio2SD/Rocky
Stereo/Pajero
GTIA/Psychol
ARTYKUŁY
DEMO EFFECTS
LINKI
   

Zajec/Sword
Świat algorytmów #1
Megatazin #2

Każdy z Was na pewno choć raz grał w grę w której przeciwnikiem jest komputer. Czy kiedykolwiek ktoś z Was zastanawiał się w jaki sposób komputer potrafi "myśleć"? Czy ktokolwiek z Was próbował sam napisać program który by symulował sztuczną inteligencję? Jeśli nie to polecam każdemu programiście ten temat. W przeciągu kilku lat napisałem dwie gry które symulują sztuczną inteligencję a do trzeciej jedynie wymyśliłem założenia. Tymi grami jest jako taki "Banzai" i syfny "Sexquix" oraz gra którą niedawno ukończyłem (nie ma jej jeszcze w sprzedaży) "StecMen". Wszystkie z w/w gier symulują sztuczną inteligencję. W jaki sposób one to robią opiszę w niniejszym artykule.

Podstawą do napisania programu który będzie symulował "sztuczną inteligencję" jest napisanie dobrego algorytmu. Co to takiego jest ten algorytm postaram się na prostym przykładzie wytłumaczyć.

Algorytm to ciąg instrukcji i poleceń napisanych w dowolnym języku programowania (i na dowolnym komputerze) które w oparciu na danych wejściowych (podanych przez użytkownika programu ) obliczają przy pomocy mniej lub bardziej złożonych obliczeń czysto matematycznych dane wyjściowe, które dają odbiorcy złudzenie że ma do czynienia z istotą rozumną.

Żeby bardziej przybliżyć czytelnikowi problem podam zasadę działania algorytmu użytego w grze "Sexquix" i wytłumaczę dlaczego nie można z nim wygrać (prawie!).

Pisząc tą grę nie miałem jeszcze pojęcia o algorytmach (i dziś wcale nie uważam się za eksperta, lecz na pewno dziś więcej wiem na temat niż wtedy). Problem przed którym stanąłem pisząc tą grę potraktowałem dość pochopnie i dlatego gra wyszła tak a nie inaczej. Komputer w tej grze ma za zadanie udawać inteligentną istotę która potrafi dobrze grać w "kółko i krzyżyk".

Inteligencja w tej grze symulowana jest w następujący sposób:

W pamięci komputera jest 9 bajtów (tu pod adresem $0600-$0609), które przed każdą rozgrywką są zerowane. Każdemu bajtowi przyporządkowane jest odpowiednie miejsce w "kratce". Każdy ruch gracza jak również komputera odhaczany jest w pamięci. Ruch komputera oznaczany jest 1 a gracza 2, wolne pole 0. I tak poniższe pole...

     X |  |
     --------
     X |  | O
     --------
     O |  |

będzie wyglądać w pamięci 1,0,0,1,0,2,2,0,0

Cyfry czytamy kolejno od lewego górnego rogu w prawo aż do dolnego lewego rogu. W przypadku gry w "kółko i krzyżyk" problem jest dosyć prosty bo wystarczy zapisać w programie wszystkie możliwości i podać oczekiwane odpowiedzi (ta metoda jest w tym przypadku najprostsza lecz nie ma wiele wspólnego z algorytmem).

Problem się o wiele bardziej skomplikował podczas pisania gry "Banzai". Tutaj zasady gry są takie same jak w "kółku i krzyżyku" lecz pole jest o rozmiarach 20x20 oczek. Tutaj zapisanie wszystkich możliwości jest nonsensem z trzech podstawowych przyczyn:

  • Nie przewidzimy wszystkich możliwości
  • Zabraknie nam pamięci do ich zapisania
  • Czas odpowiedzi byłby dość długi


  • I co w takim przypadku? Oczywiście rozwiązań tego problemu jest wiele lecz ja opiszę tylko ten który sam wymyśliłem lecz jego realizacją programową zajął się 2obert Szurała (ROBUŚ). Przyjmijmy identyczne oznaczenia jak w poprzednim przykładzie (tj. 0-puste oczko, 1-kółko, 2-krzyżyk).

    W pamięci mamy wygospodarowany obszar 400 bajtów jako "bufor" pola gry (400 dlatego że pole gry ma 20x20 oczek a 20*20=400). Zaczyna grę gracz. Wprowadza on dane wejściowe w postaci współ. (X,Y), w które umieszczamy kółko (symbol ruchu gracza). Kółko zostaje pokazane na ekranie i odznaczone w pamięci. Adres w który go odznaczam wyliczam z prostego wzoru:

    Adres=Adres_Bufora+Y*20+X
    

    dlatego, że maksymalna ilość wierszy (pionowo) jest 20. Gdy mam wyliczony adres sprawdzam najpierw czy nie ma tam wartości różnej od 0. Jeśli jest, nie zezwalam wstawić tam graczowi kółka. Jeśli nie ma wstawiam tam symbol kółka (czyli 1).

    Następnie wyliczam adresy pól położonych nad, pod, obok i pod kątem. Sposób obliczeń jest prosty... dla pola nad adr=adr-20, dla pola pod adr=adr+20, dla pola z lewej adr=adr-1, pola z prawej adr+1 i pod kątem odpowiedni +19, +21, -19, -21. Po wyliczeniu adresu sprawdzam wartość która jest przetrzymywana pod wskazanym adresem. Jeśli jest to 0 (puste oczko) lub 2 (krzyżyk, czyli oznaczenie komputera) anuluję. Natomiast gdy pod wyliczonym adresem znajduje się wartość 1, zapamiętuję w tablicy (adres oraz kierunek). Gdy tak "rozejrzę się w około" patrzę do tablicy z adresami i zapamiętuję adres który tam jest jako pierwszy po czym go "wywalam" z tablicy. W bajcie o zapamiętanym adresie "rozglądam" się lecz tylko we wcześniej zapamiętanym kierunku. Sprawdzam czy tam nie występuje wartość 1. Jeśli tak do zmiennej KROK dodaję 1 i czynność powtarzam ponownie tzn. wyliczam ponowny adres który mieści się dalej w zapamiętanym kierunku; sprawdzam wartość; jeśli jest 1 to liczę nowy adres itd., aż do momentu gdy wartość zmiennej KROK nie wyniesie 6 (takie są akurat założenia gry "Banzai", wartość KROK oznacza ile już gracz postawił kółek obok siebie w jednym kierunku. Tu liczba 6 oznacza wygraną gracza). Jeśli wartość jest już wysoka tj.4 czyli graczowi wystarczy postawić po jednym kółku z jednej i drugiej strony należy natychmiast się zastawiać i wstawiać w tym miejscu krzyżyk w przypadku wartości 5, w zmiennej KROK zastawianie się nie ma już w prawdzie jakiegokolwiek sensu gdyż gracza od wygranej dzieli jeden ruch lecz daje to złudzenie rozpaczliwej obrony bardzo charakterystycznej dla istot rozumnych. Wartość 6 w zmiennej KROK oznacza niewątpliwą wygraną gracza.

    Opisany algorytm został przedstawiony w dość schematyczny sposób jeśli ktoś jest zainteresowany powyższym tematem polecam mu książkę napisaną przez pana Piotra Wróblewskiego pt:"ALGORYTMY struktury danych i techniki programowania" - wydawnictwa "Helion" (cena około 30zł).

    Książka ta opisuje problemy algorytmiki z przytoczeniem przykładowych rozwiązań w języku C++ na komputer PC. Pomimo tego temat ten jest ogólny dla wszystkich komputerów i pomysły na rozwiązanie wielu problemów przedstawione w tej książce można przetłumaczyć na każdy język programowania "może oprócz logo !!!".

    Zajec/Sword

     

    madteam.atari8.info © MadTeam, hosted: www.atari8.info