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