Szachy-Jak to naprawde dziala.pdf
(
54 KB
)
Pobierz
26270518 UNPDF
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¦±ciwymagaodpowiedniejreprezentacjifigur,pozycjioraz
wiedzynaichtematwj¦zykuzrozumiałymdlakomputera.Takareprezen-
tacjaniejestwygodnadlaczłowieka,aledlamaszynyjestniezb¦dna,gdy»
potrzebujeonadokładnej,formalnejdefinicjirzeczywisto±ci,wktórejmasi¦
porusza¢.
1
Sprawdzaniepoprawno±ciposuni¦¢
Pierwszyminajprostszymelementemprogramuszachowegojestcz¦±¢odpo-
wiedzialnazasprawdzaniepoprawno±ciwykonywanychposuni¦¢.Zwi¡zana
jestztymkonieczno±¢odpowiedniegokodowaniafigurszachowychorazich
aktualnegopoło»enianaszachownicy.
Kodowaniefigurniejesttakistot1neijesttutajdu»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¡tkoweustawieniefigurnaszachow-
nicyprzedstawiatabela2.
108911129810
77777777
00000000
00000000
00000000
00000000
11111111
42356324
Tabela2:Kodowaniepocz¡tkowegoustawieniafigur.
Kolejnymkrokiemjestopisaniekomputerowisposobuporuszaniasi¦fi-
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.
2
00000000
00000000
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łychfigur.
Ostatnimkrokiemjestuwzgl¦dnienieinterakcjimi¦dzyposzczególnymi
figurami.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ólnymfigu-
rom:pionek(100),skoczek(300),goniec(330),wie»a(500),hetman(900),
król(20000).Takiepodej±ciejestmniejwi¦cejzgodneznaszymiintuicjami
-pionekjestnajmniejwarto±ciow¡figur¡szachow¡,goniecjestnieznacznie
lepszyodskoczka,akróljestbezcenny.Dodatkowozka»d¡zfigurmo»na
skojarzy¢tablic¦heurystyczn¡okre±laj¡c¡premi¦punktow¡zaustawieniefi-
gurynadanympolu.Ustawieniefigurywcentrumnajcz¦±ciejoznaczadobr¡
pozycj¦iliczonejestnaplus.Przykładow¡tablic¦heurystyczn¡dlabiałego
skoczkaprzedstawiatabela4.
Ustawienieskoczkanapolud5(54)dajepozycj¦o19punktówlepsz¡ni»
poustawieniugonapoluh8(88).
3
-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.
4
Plik z chomika:
LukaszNorek
Inne pliki z tego folderu:
Zygmunt Miłkowski [Teodor Tomasz Jeż] - Sylwety emigracyjne.pdf
(1146 KB)
World Atlas.pdf
(578 KB)
Tybetanska Ksiega Umarlych.rar
(57 KB)
Tai Chi Chuan.pdf
(658 KB)
Tae_Kwon_Do_Handbook.rar
(1890 KB)
Inne foldery tego chomika:
Antologie
Encyklopedie, słowniki
Imiona
Kucharskie
Religie
Zgłoś jeśli
naruszono regulamin