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.