home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Amiga MA Magazine 1997 #3
/
amigamamagazinepolishissue03-1
/
ma_1995
/
05
/
ami038.txt
< prev
next >
Wrap
Text File
|
1997-04-07
|
13KB
|
578 lines
KOMPUTEROWE MYÔLENIE
<lead>Na czym polegajâ algorytmy myôlowe komputera? Jak to sië
dzieje, ûe grajâc w najprzeróûniejsze strategie z komputerem,
mamy przed sobâ peînoprawnego partnera, umiejâcego ze swoistym
wyrachowaniem poruszaê swoimi wojskami tak, aby doprowadziê do
naszej przegranej? W jaki sposób komputer potrafi analizowaê
sytuacjë na polu bitwy? To, oczywiôcie, temat-rzeka. Jednak mimo
to postaram sië choê w maîym stopniu przybliûyê Czytelnikom
zagadkë "sztucznej inteligencji".
<a>Krzysztof Prusik
<txt>Wszyscy wiemy, ûe komputer bez programu to kupa zîomu (tak,
nawet Amiga). Program to ciâg rozkazów i danych napisanych przez
czîowieka. Jaki z tego wniosek? To nie komputer myôli, tylko
programy sâ tak skonstruowane, ûe na kaûde nasze posuniëcie, np.
podczas gry w szachy, majâ przygotowanâ odpowiedniâ ripostë (a
przynajmniej tak sië wydaje).
Jak dziaîajâ takie programy? Po prostu analizujâ wszystkie
moûliwe posuniëcia (lub przynajmniej wiëkszoôê), czyli zwykle
dziaîajâ wedîug zasady:
<l>Wykonaj pierwsze posuniëcie (jedno z moûliwych)
Jeôli trzeba
wykonaj nastëpne posuniëcie (jedno z moûliwych)
Jeôli trzeba
wykonaj nastëpne posuniëcie (jedno z moûliwych)
Jeôli trzeba
...
Inaczej
Daj wynik analizy
Inaczej
Daj wynik analizy
Inaczej
Daj wynik analizy
<txt>Oczywiôcie bardziej elegancka byîaby odpowiednia procedura
rekurencyjna (w AMOS-ie):
<l>Procedure ANALIZA[KROK]
' Na wejôciu procedury mamy KROK, czyli numer posuniëcia
For I=1 TO OSTANIE_POSUNIECIE
' obliczenie warunku KONIEC_OBLICZEN w kroku KROK
If Not KONIEC_OBLICZEN
ANALIZA[KROK+1] : KONIEC=Param
Else
' Wypisz wynik analizy
KONIEC=True
End If
' wyjdú z pëtli jeôli juû otrzymaliômy wynik
Exit If KONIEC
Next
End Proc
<txt>Gwoli wyjaônienia: >Not< -- neguje warunek KONIEC_OBLICZEN,
czyli jeôli KONIEC_OBLICZEN=>True< (prawda), to >Not<
KONIEC_OBLICZEN=>False< (faîsz) i na odwrót. >Exit If< --
powoduje wyjôcie z pëtli >For..Next<, jeôli speîniony bëdzie
warunek KONIEC.
<sr>Labirynt
<txt>Proponujë poanalizowaê teraz trochë ten algorytm, aby go
zrozumieê, bo za chwilë postawimy przed sobâ o wiele trudniejsze
zadanie. Napiszemy prostâ gierkë, która przetestuje myôlenie
komputera. Po prostu zaprojektujemy labirynt i umieôcimy gdzieô w
jego ôrodku myszkë oraz serek, a nastëpnie nakaûemy myszce
znaleúê drogë do serka. Ok?
Zaczynamy od spraw technicznych: labirynt bëdzie reprezentowany w
pamiëci komputera przez dwuwymiarowâ tablicë liczb. I tak:
1 bëdzie oznaczaê puste pole (PUSTY)
2 bëdzie oznaczaê ôcianë (SCIANA)
3 bëdzie oznaczaê serek (SEREK)
4 bëdzie oznaczaê miejsca juû odwiedzone (ODWIEDZONY). Gdybyômy
juû odwiedzonych pól w ûaden sposób nie zaznaczali, myszka
mogîaby krâûyê "w nieskoïczonoôê" i nie wiedziaîaby, na których
polach juû byîa, a na których jeszcze nie.
--------------!Rys.1: Przykîadowy labirynt z liczb!--------------------
Warto wiëc na poczâtku programu poczyniê odpowiednie deklaracje:
<l>PUSTY=1 : Rem----- pole puste
SCIANA=2 : Rem------- sciana
SEREK=3 : Rem-------- serek!
ODWIEDZONY=4 : Rem--- miejsce juû odwiedzione
X_MAX=10 : Rem------- liczba pol w x
Y_MAX=10 : Rem------- liczba pol w y
X_DELTA=10 : Rem----- szerokoôê pola
Y_DELTA=10 : Rem----- wysokosc pola
Dim POLE(X_MAX,Y_MAX)
Global PUSTY,SCIANA,SEREK,ODWIEDZONY
Global X_MAX,Y_MAX,POLE(),X_DELTA,Y_DELTA
<txt>Proszë zwróciê uwagë, ûe dziëki dodaniu nowych zmiennych:
PUSTY, SCIANA, SEREK i ODWIEDZONY, w programie, zamiast nic nie
mówiâcych liczb 1, 2, 3 i 4, bëdziemy mogli zamiennie uûywaê nazw
tych zmiennych.
<sr>Projektowanie labiryntu
<txt>Ogólnie nasz program bëdzie wyglâdaî nastëpujâco:
1. Projektowanie labiryntu przez uûytkownika.
2. Szukanie drogi wyjôcia przez myszkë.
Zaczynamy od zaprojektowania labiryntu: naciskajâc klawisze kursora,
bëdziemy przemieszczaê sië po naszym labiryncie, wciôniëcie zaô
"1" -- spowoduje wpisanie pustego pola do tablicy POLE()
"2" -- spowoduje wpisanie ôciany
"3" -- wpisanie serka
"K" lub klawisza [Enter] -- koniec projektowania.
<l>Procedure PROJEKTUJ_LABIRYNT
ZERUJ_TABLICE
WYSWIETL_LABIRYNT
X=0 : Y=0
Repeat
POKAZ_KURSOR[X,Y]
Repeat
KLAWISZ$=Inkey$
Until KLAWISZ$<>""
If (KLAWISZ$=Cup$)and(Y>0) Then Dec Y
If (KLAWISZ$=Cdown$)and(Y<Y_MAX) Then Inc Y
If (KLAWISZ$=Cleft$)and(X>0) Then Dec X
If (KLAWISZ$=Cright$)and(X<X_MAX) Then Inc X
If KLAWISZ$="1" Then POLE(X,Y)=PUSTY
If KLAWISZ$="2" Then POLE(X,Y)=SCIANA
If KLAWISZ$="3" Then POLE(X,Y)=SEREK
POKAZ_POLE[X,Y,POLE(X,Y)]
Until (KLAWISZ$="K")or(KLAWISZ$="k")or(KLAWISZ$=Chr$(13)
End Proc
Procedure POKAZ_KURSOR[X,Y]
'ta procedurka ustawia kursor myszki
'w punkcie tablicy POLE()
'o wspolrzednych X,Y
X Mouse=X Hard(X*X_DELTA)
Y Mouse=Y Hard(Y*Y_DELTA)
End Proc
<txt>>Chr$(13)< -- to kod, jaki odpowiada naciôniëciu klawisza
[Enter]. Dziaîanie procedury PROJEKTUJ_LABIRYNT chyba nie wymaga
komentarza. Trzeba tylko jeszcze stworzyê dwie pomocnicze
procedurki: ZERUJ_TABLICE (sîuûy do zainicjalizowania tablicy
POLE(), czyli po prostu wypeînia caîâ tablicë wartoôciami PUSTY),
oraz wyswietl labirynt (do pokazania zawartosci tablicy na
ekranie monitora).
<l>Procedure ZERUJ_TABLICE
For X=0 To X_MAX
For Y=0 To Y_MAX
POLE(X,Y)=PUSTY
Next
Next
End Proc
Procedure WYSWIETL_LABIRYNT
For X=0 To X_MAX
For Y=0 To Y_MAX
POKAZ_POLE[X,Y,POLE(X,Y)]
Next
Next
End Proc
<txt>Uwaûni Czytelnicy zauwaûyli zapewne, ûe jeszcze nie zostaîa
zdefiniowana procedura POKAZ_POLE. W wyniku jej dziaîania, na
ekranie zostanie wyôwietlona zawartoôê pojedynczego pola
labiryntu (albo SCIANA, albo PUSTY, albo SEREK). Proszë
zauwaûyê, ûe dziëki takiemu podziaîowi programu gîównego na
procedury, bezproblemowo, w kaûdej chwili, moûemy zmieniê sposób
pokazywania zawartoôci tablicy z zakodowanym w niej labiryntem,
zmieniajâc jedynie zawartoôê procedurki POKAZ_POLE. Oto pierwsza
metoda, w trybie tekstowym (uwaga! X_DELTA musi byê równe 8
oraz: Y_DELTA=8, bo taki jest rozmiar systemowego fontu):
<l>Procedure POKAZ_POLE[X,Y,TYP_POLA]
If TYP_POLA=PUSTY
Print At(X,Y);"O";
End If
If TYP_POLA=SCIANA
Print At(X,Y);"*";
End If
If TYP_POLA=SEREK
Print At(X,Y);"S";
End if
End Proc
<txt>No pewnie, ûe to by dziaîaîo, ale... czy to nie jest dziwne? Amiga
pracujâca w trybie tekstowym? No tak. Trzeba to zrobiê lepiej,
wykorzystujâc tryb graficzny. Oto druga wersja procedury:
<l>Procedure POKAZ_POLE[X,Y,TYP_POLA]
If TYP_POLA=SCIANA Then Ink 2
If TYP_POLA=PUSTY Then Ink 0
If TYP_POLA=SEREK Then Ink 1
X_POCZ=X*X_DELTA
Y_POCZ=Y*Y_DELTA
X_KON=X_POCZ+X_DELTA-1
Y_KON=Y_POCZ+Y_DELTA-1
Bar X_POCZ,Y_POCZ To X_KON,Y_KON
If TYP_POLA=SEREK Then Text X_POCZ+1,Y_POCZ+7,"S"
End Proc
<txt>Proste? Uruchom procedurkë PROJEKTUJ_LABIRYNT i zobacz, jak
dziaîa. I co? Wszystko w porzâdku? No lecimy dalej!
<sr>Szukanie drogi do serka
<txt>Sprawy techniczne mamy za sobâ, teraz pozostaîy problemy
abstrakcyjne. No wîaônie, jak to zrobiê, ûeby komputer potrafiî
znaleúê wyjôcie z labiryntu, a jeszcze na dodatek nam je pokazaî?
Trudne? Tak sië tylko wydaje. Generalna zasada dotyczâca sposobu
rozwiâzywania tego typu problemów jest nastëpujâca: "nie
myôleê...o wszystkim naraz". Tak wiëc, jeûeli kiedykolwiek (jak
np. teraz) bëdziemy musieli napisaê jakiô skomplikowany algorytm,
starajmy sië go podzieliê na jak najmniejsze kawaîeczki.
Wracajâc do naszego labiryntu. Wyobraúmy sobie, ûe jesteômy
myszkâ. Juû? W kaûdej chwili moûemy pójôê albo w lewo, albo w
prawo, albo w górë, albo w dóî. Oczywiôcie jeûeli nie wyjdziemy
poza labirynt, jeûeli mamy przejôcie (czyli tam, gdzie chcemy
iôê, nie ma ôciany) oraz jeûeli danego pola jeszcze nie
odwiedziliômy (bo nie ma sensu dwa razy chodziê w to samo
miejsce). Cóû nam wiëc pozostaje innego, jak tylko napisaê
odpowiedniâ procedurë rekurencyjnâ? Ûeby jednak wszystko byîo
jasne, wypiszmy warunki, jakie bëdziemy musieli sprawdzaê w tej
procedurce:
<l>Czy jesteômy w labiryncie?
TAK:
Czy to pole jest wolne (PUSTY)?
TAK:
Pokazujemy myszkë (np. kursor myszki).
Zaznaczamy to pole jako odwiedzone (ODWIEDZONY) i szukamy
dalej, czyli wywoîujemy të procedurë rekurencyjnâ dla czterech
sâsiednich pól (lewego, prawego, górnego i dolnego).
Czy którakolwiek z wywoîanych procedur znalazîa serek?
TAK: Jako wynik zwracamy prawdë i ewentualnie
w sprawdzanym punkcie rysujemy drogë.
NIE: Jako wynik procedury zwracamy faîsz.
NIE:
Czy juû znaleúliômy serek?
TAK:
Jako wynik dziaîania procedury zwracamy prawdë (bo
znaleúliômy serek) i wracamy do procedury, która
wywoîaîa nas rekurencyjnie i kazaîa przyjôê w to
miejsce.
NIE:
Jako wynik zwracamy faîsz i jak wyûej.
NIE:
Jako wynik zwracamy faîsz i wracamy do procedury, ktora nas wywoîaîa
rekurencyjnie.
<txt>Ha! I oto jedna jedyna procedura rekurencyjna zaîatwia caîy
problem. Dlaczego? Bo jest wywoîywana dla (prawie) wszystkich
punktów labiryntu (tablicy POLE()). Radzë zgîëbiê tajniki jej
dziaîania, bo za chwilë przystâpimy do jej implementacji w
AMOS-ie.
Juû? No to piszemy:
<l>Procedure SZUKAJ_SERKA
' Zaîóûmy, ûe myszka startuje od punktu 0,0
JEST_DROGA[0,0] : WYNIK=Param
'jeôli WYNIK=True, znaczy to,
'ûe myszka znalazîa serek
If WYNIK
'Jest droga do serka
Print " Jest droga do serka! "
Bell 50
Else
'Niestety takiej nie ma
Print " Nie ma drogi do serka. "
Boom
End If
End Proc
Procedure JEST_DROGA[X,Y]
'sprawdza, czy w polu X,Y jest serek
'i ewentualnie rekurencyjnie sprawdza pola sâsiednie
If (X<=X_MAX)and(X>=0)and(Y<=Y_MAX)and(Y>=0)
'nie wyszliômy poza tablicë
If POLE(X,Y)=PUSTY
'pole puste, wiec pokazujemy sie tutaj
POKAZ_KURSOR[X,Y] : Wait OPOZNIENIE
'jeszcze tu nie byliômy
'wiëc zaznaczamy to pole
POLE(X,Y)=ODWIEDZONY
'sprawdzamy pole po lewej
JEST_DROGA[X-1,Y]
WYNIK=Param
If Not WYNIK
'sprawdzamy pole po prawej
JEST_DROGA[X+1,Y]
WYNIK=Param
End If
If Not WYNIK
'sprawdzamy pole na górze
JEST_DROGA[X,Y-1]
WYNIK=Param
End If
If Not WYNIK
'sprawdzamy pole na dole
JEST_DROGA[X,Y+1]
WYNIK=Param
End If
'podczas powrotu
POKAZ_KURSOR[X,Y] : Wait OPOZNIENIE
Else
If POLE(X,Y)=SEREK
'wreszcie znalezlismy serek!
WYNIK=True
Bell 20
Else
WYNIK=False
End If
End If
Else
WYNIK=False
End If
End Proc[WYNIK]
<txt>Aby procedurka dziaîaîa poprawnie, wôród zmiennych
globalnych powinno sië znaleúê OPOZNIENIE, które bëdzie nam
okreôlaê prëdkoôê poruszania sië myszki. Mam skromnâ nadziejë, ûe
teraz wszystko jest dla Was jasne. Oczywiôcie gîówny moduî
programu bëdzie wyglâdaî tak:
<l>PROJEKTUJ_LABIRYNT
SZUKAJ_SERKA
<txt>I tyle. Stworzyliômy chyba najprostszy model "sztucznej
inteligencji". Gdybyômy teraz wsadzili nasz komputer do choêby
nie wiem jak skomplikowanego labiryntu (ale zawierajâcego
wyjôcie), to za pomocâ takiego programu jak ten (oraz nóg lub
chociaû kóîek), na pewno wydostaîby sië stamtâd. Róûne mutacje
algorytmu, z którym sië zapoznaliômy w artykule, sâ
wykorzystywane we wszystkich grach strategicznych (z nielicznymi
wyjâtkami, które zresztâ potwierdzajâ reguîë).
Hmmm. Z przykroôciâ muszë jednak wyznaê, ûe maîo jest gier
przeprowadzajâcych dogîëbnâ analizë ruchów swoich i przeciwnika
(tak jak np. szachy). Nawet osîawione Battle Isle (spëdziîem
wiele nocy nad tâ gierkâ), nie potrafi "myôleê" naprawdë, a ruchy
wojsk komputera (których jest zwykle dwa lub trzy razy tyle co
naszych), sprowadzajâ sië do znalezienia najkrótszej drogi,
prowadzâcej do naszych oddziaîów. I tyle! No, moûe troszkë
przesadziîem... Szczâtkowa postaê analitycznego myôlenia
przejawia sië tym, ûe zwykle wokóî swojej bazy komputer zostawia
przynajmniej jeden oddziaî, ale to chyba potrafiîby zakodowaê
kaûdy programista. Konkluzja: warto zapoznaê sië z algorytmem
labirynt. Moûe w przyszîoôci zaprojektujemy Battle Isle 2000?
Dygresja: sîyszaîem, ûe nastëpnâ czëôê tej gry przygotowuje Union
Software.
Na tym koïczë dzisiejszy odcinek AMOS-a. Moje propozycje
ciekawych problemów:
1. Co sië stanie, gdy zlikwidujemy zaznaczanie pól labiryntu, na
których juû byliômy?
2. Co sië stanie, gdy zaraz po sprawdzeniu danego pola labiryntu
(czyli za 28. liniâ procedury JEST_DROGA[X,Y]) umieôcimy rozkaz
POLE(X,Y)=PUSTY (czyli odmarkujemy, odznaczymy, dane pole)?
3. Jak zaprojektowaê algorytm, który znajdzie najkrótszâ drogë do
serka?
4. Wizualnie uatrakcyjniê rysowany labirynt, czyli np. ôciany
narysowaê za pomocâ ikonek, a myszka niech bëdzie np. BOB-em.
5. Powiëkszyê rozmiar labiryntu, ale uwaga! W takim wypadku
najprawdopodobniej trzeba bëdzie zwiëkszyê rozmiar stosu komendâ
>Set Stack< oraz wielkoôê na dane (>Set Buffer<).
Zainteresowanych odsyîam do mojej ksiâûki "AMOS Professional w
praktyce -- programowaê moûe kaûdy", wydanej przez RaWi sc.
6. Odmienne zadanie: Mamy pole kwiatków o róûnych wysokoôciach.
Na jednym z tych kwiatków wyleguje sië pszczóîka Maja. Gucio
bardzo chce sië z niâ spotkaê, ale jest na tyle leniwy, ûe moûe
jedynie przeskoczyê z wyûszego kwiatka na niûszy. Trzeba napisaê
algorytm, który sprawdzi, czy jest moûliwe, aby skaczâc w ten
sposób, Gucio dotarî w koïcu do pszczóîki.