Szachy-Jak to naprawde dziala.pdf

ladamiKempelena

Przegl¡dprogramówgraj¡cychwszachy

PrzemysławGr¡dalski

kwiecie«2001

Jaktonaprawd¦działa?

Zlogicznegopunktuwidzeniaszachys¡gr¡małoskomplikowan¡–reguły

s¡±ci±leokre±loneistosunkowoproste.Rozgrywaj¡cparti¦szachow¡mo»na

wi¦cstosowa¢nast¦puj¡c¡strategi¦:rozwa»amywszystkieswojeposuni¦cia,

nast¦pnieposuni¦ciaprzeciwnikaitaknazmian¦,a»uzyskanyzostaniejeden

ztrzechrezultatów–remis,wygranalubpora»ka.Niestetyliczbapozycji

przewijaj¡casi¦przeztegotypu„siłowe”podej±ciejesttakdu»a,»edzisiaj

»adenkomputer,wi¦ctymbardziejczłowiek,niejestwstaniejejogarn¡¢.

Wiadomojednak,»esposóbmy±leniaszachistówprzebieganiecoinaczej

ijestzale»nyodsiłygry.Generalniepolegatonatym,»eprzegl¡danes¡

szczegółowotylkoposuni¦cianajbardziejobiecuj¡ce(subiektywnyczynnik

ocenypozycji)),nazmian¦dlabiałychiczarnych,zgł¦boko±ci¡kilku(kil-

kunastu)ruchówdoprzodu.Tegotypustrategiiprzeszukiwaniakomputer

trzebanauczy¢iwtymjestnajwi¦kszyproblem.

Ka»dyprogramszachowypowiniensi¦składa¢,zgrubszamówi¡c,zna-

st¦puj¡cychfunkcjonalnychcz¦±ci:

• sprawdzaj¡cejpoprawno±¢wykonywanychposuni¦¢,

• oceniaj¡cejaktualn¡pozycj¦,

• zapami¦tuj¡cejuzyskan¡wiedz¦natematpozycji.

Opiska»dejzcz¦±ciwymagaodpowiedniejreprezentacjiﬁgur,pozycjioraz

wiedzynaichtematwj¦zykuzrozumiałymdlakomputera.Takareprezen-

tacjaniejestwygodnadlaczłowieka,aledlamaszynyjestniezb¦dna,gdy»

potrzebujeonadokładnej,formalnejdeﬁnicjirzeczywisto±ci,wktórejmasi¦

porusza¢.

Sprawdzaniepoprawno±ciposuni¦¢

Pierwszyminajprostszymelementemprogramuszachowegojestcz¦±¢odpo-

wiedzialnazasprawdzaniepoprawno±ciwykonywanychposuni¦¢.Zwi¡zana

jestztymkonieczno±¢odpowiedniegokodowaniaﬁgurszachowychorazich

aktualnegopoło»enianaszachownicy.

Kodowanieﬁgurniejesttakistot1neijesttutajdu»adowolno±¢.Przykła-

dowomo»eonowygl¡da¢tak:0–pustepole,1(7)–biały(czarny)pionek,

2(8)–biały(czarny)skoczek,3(9)–biały(czarny)goniec,4(10)–biała

(czarna)wie»a,5(11)–biały(czarny)hetman,6(12)–biały(czarny)król.

Szachownicazazwyczajpami¦tanajestwpostacitablicydwuwymiarowej

(tabela1).Wówczaspolud1odpowiadawarto±¢14,polub6warto±¢62,polu

g7warto±¢77,itd.

8182838485868788

7172737475767778

6162636465666768

5152535455565758

4142434445464748

3132333435363738

2122232425262728

1112131415161718

Tabela1:Komputerowareprezentacjaszachownicy.

Dlawy»ejopisanejreprezentacjipocz¡tkoweustawienieﬁgurnaszachow-

nicyprzedstawiatabela2.

108911129810

77777777

00000000

11111111

42356324

Tabela2:Kodowaniepocz¡tkowegoustawieniaﬁgur.

Kolejnymkrokiemjestopisaniekomputerowisposobuporuszaniasi¦ﬁ-

gurposzachownicy.Przypu±¢my,»ebiałyskoczek(2)stoinapoluc3(33).

Wówczasmo»eonskoczy¢napola:a2(21),a4(41),b1(12),b5(51),d1(14),

d5(54),e2(25),e4(45),takjakzostałotoprzedstawionewtabeli3.

00000000

0520540000

4100045000

003300000

2100025000

0120140000

Tabela3:Kodowanieruchuskoczka.

Ogólnieruchyskoczkastoj¡cegonadowolnympolu x mo»nazapisa¢wzo-

rem: x 0 = x + r ,gdzie x 0 nowympolemskoczka,a r 2{± 8 , ± 12 , ± 19 , ± 21 }

reprezentujemo»liweskoki.Wa»nejest,»eprzyprzyj¦tymsposobiekodowa-

niaszachownicyruchskoczkajestpoprawnyjedyniewówczas,gdydocelowe

pole x 0 jestjedn¡zliczbztabeli1.Wpodobnysposóbopisujesi¦ruchydla

pozostałychﬁgur.

Ostatnimkrokiemjestuwzgl¦dnienieinterakcjimi¦dzyposzczególnymi

ﬁgurami.Nale»yokre±li¢kiedydaneposuni¦ciemo»ezosta¢wykonane,akie-

dynie.Istotnes¡tutajtakieszczegóły,jakszach,roszada,biciepionkami,

itd.Reprezentacjatychinformacjiwformiezrozumiałejdlakomputeranie

jesttrudna,alezatopracochłonna,bowymagarozwa»eniawieluczynników

równocze±nie.

Ocenapozycji

Prawidłowaocenapozycjijestkluczowaionataknaprawd¦decydujeosile

gryprogramuszachowego.Składasi¦nani¡szeregczynnikówmniejlubbar-

dziejwymiernych,którewjaki±sposóbtrzebaprzeło»y¢naj¦zykzrozumiały

dlamaszyny.Nale»¡donichprzewagamaterialnaorazprzewagapozycyjna

(zaj¦tecentrum,zaj¦teotwartelinie,przek¡tne,itp.).

Najprostszympomysłemjestprzypisaniewarto±ciposzczególnymﬁgu-

rom:pionek(100),skoczek(300),goniec(330),wie»a(500),hetman(900),

król(20000).Takiepodej±ciejestmniejwi¦cejzgodneznaszymiintuicjami

-pionekjestnajmniejwarto±ciow¡ﬁgur¡szachow¡,goniecjestnieznacznie

lepszyodskoczka,akróljestbezcenny.Dodatkowozka»d¡zﬁgurmo»na

skojarzy¢tablic¦heurystyczn¡okre±laj¡c¡premi¦punktow¡zaustawienieﬁ-

gurynadanympolu.Ustawienieﬁgurywcentrumnajcz¦±ciejoznaczadobr¡

pozycj¦iliczonejestnaplus.Przykładow¡tablic¦heurystyczn¡dlabiałego

skoczkaprzedstawiatabela4.

Ustawienieskoczkanapolud5(54)dajepozycj¦o19punktówlepsz¡ni»

poustawieniugonapoluh8(88).

-9-7-5-4-4-5-7-9

-62100126

-4368863-4

-468101086-4

-5267762-5

51733715

-8-3-1-1-1-1-3-8

-9-8-7-6-6-7-8-9

Tabela4:Heurystykaustawieniabiałegoskoczka.

Ostatecznaocenapozycjijestsum¡wszystkichwarto±cicz¡stkowychopi-

suj¡cychpozycj¦białychpomniejszon¡oodpowiedni¡warto±¢obliczon¡dla

czarnych.Jasnejest,»ewarto±¢dodatniaoznaczalepsz¡pozycj¦dlabiałych,

aujemnalepsz¡dlaczarnych.Najejpodstawieprogramdecyduje,któr¡

zmo»liwychkontynuacjiostateczniewybra¢.

Wi¦kszo±¢programówszachowychdziaławzbli»onysposób,ztym»e

uwzgl¦dniaj¡oneznaczniewi¦cejczynnikówwpływaj¡cychnaocen¦danej

sytuacji.Teczynnikiiprzypisywaneimznaczeniedecyduj¡ostyluipoziomie

prezentowanymprzezprogram.

Zapami¦tywaniepozycji

Wła±ciweprzechowywaniewiedzynatematpozycjimog¡cychsi¦pojawi¢

wczasiegrymaistotnywpływnaszybko±¢„my±lenia”programu.Informa-

cjetepowinnyby¢zapami¦tywanewtakisposób,abyczaspotrzebnydo

sprawdzeniaczywiemyju»co±natematzaistniałejpozycjioraznazapami¦-

tanienowejpozycjibyłyminimalne.Struktur¡danychposiadaj¡c¡tewła-

sno±ciistosowan¡wpraktycejesttzw.tablicahaszuj¡ca(ang. hash-table ).

St¡dniemalka»dyprogramzczołówki±wiatowejposiadamo»liwo±¢okre±le-

niapami¦ciRAMnani¡przeznaczonej.Mniejszyrozmiartablicyhaszuj¡cej

wymagaodprogramucz¦stszegopowtarzaniatychsamychoblicze«.

Podsumowanie

Jakwida¢konstrukcjaprogramuszachowegojestdo±¢skomplikowana,po-

mimoniewielkiejzło»ono±cisamejgry.Skorzystaniezwy»ejzasugerowanych

rozwi¡za«ipomysłówpozwalanaskonstruowaniewłasnegoprogramugraj¡-

cegowszachy.Abyjednakmógłonskuteczniewalczy¢znajlepszymi,trzeba

si¦sporonapracowa¢.Wzoremdona±ladowaniamo»eby¢darmowyprogram

Crafty(patrzCHIP-CD)stworzonyprzezhobbyst¦,agraj¡cytylkonieco

słabiejni»czołówka±wiatowa.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: