Viết chương trình Carô

Tròchơi đối kháng (twoagent,conflicting game (?)) : Gồm 2 người chơi, đối thủ này sẽ tìm cáchdành chiến thắng trước đối thủ kia trong một số hữu hạn nước đi, mỗi nước đi đuợc tạo ra dựa từ 1 trạng thái bấtkỳ của trận đấu.
Nội dung trích xuất từ tài liệu:
Viết chương trình CarôViếtchươngtrìnhCarô(Gomoku)GIỚITHIỆUVỀTRÒCARÔGOMOKUVIẾTMỘTCHƯƠNGTRÌNHGAMEGOMOKUNHƯTHẾNÀO...1.Giớithiệu:Tròchơiđốikháng(twoagent,conflictinggame(?)):Gồm2ngườichơi,đốithủnàysẽtìmcáchdànhchiếnthắngtrướcđốithủkiatrongmộtsốhữuhạnnướcđi,mỗinướcđiđuợctạoradựatừ1trạngtháibấtkỳcủatrậnđấu.Nếusau1sốgiớihạnnướcđi,nếuchưaaidànhchiếnthắngthìxemnhưhoà.Ngoàira,thôngtinvềtrậnđấulàhoàntoànbiếtđuợc(perfectinformation)đốivớicả2đốithủ.CờCarô(haycòngọilàGomoku)cũnglà1loạitròchơiđốikháng,trongđómỗiđốithủtrongmỗilượtđicủamìnhsẽchọn1ôtrốngcònlạitrênbàncờ(kẻsẵncácôlưới)saochotạothànhnconliêntiếpđểchiếnthắng...Nếun=3thìnócó1tênkháclàTicTacToe,nếubổsungthêmluậtchonóthìcóthểđổitênlàPenta,Pentix(cóănquân)...Ngoàira,cóluậtthiđấumàngườitađãchứngminhđuợcngườiđitruớcbaogiờcungcóthuậttoánđểthắng(thôngtinnàyđángtincậykhôngthìemhôngchắc...chỉbiếtlàemcóđọcquatàiliệunày...hìhìhì...),dođóđểhạnchếthuậnlợicủangườiđitrước,ngườitađãđặtraluậtrừngsau(luậtnàysẽsửdụngchoquátrìnhpháttriểnchươngtrình):+BàncờcókíchthướctuỳýNxN,chọnn=16;+Quâncờđầutiênphảiđánhchínhgiữalướibàncờ.+Nếutồntạiđúng5conliêntiếptrên1hànglàthắng(chéo,ngang,dọc).[*]+Nếuhếtchỗđithì2bênhoà.+Và1sốluậtkhác,nhưngđểđongiản,emdẹpsạch...[*]:Luậtnàyđánglẽlàgắthơnnhưsau:Đúng5convàkhôngbịchặnhaiđầu...nhưngemđểdànhchocácbáccảitiến...2.ThuậtngữAnhViệt:Đểtiệnchocácbácđọcsaunày,emxingiớithiệu1sốthuậtngữcơbảnsau,dĩnhiênmớnàylàemtựdịchhoặcxemtàiliệunênkhôngtránhđuợcsaisóthoặcchưachínhxác...mongcácbácthôngcảmvàgópý...(1)Giớithiệuvềkhônggiantìmkiếmnướcđi:Nhưcácbácđãbiết,trongtròchơiCaro,cứsaumỗinướccờ,mỗiđốithủsẽchọnratừnhữngôtrống(emptynotoccupied)đểđi,dođó,sau1mỗinướcđithìsốôtrốngcònlạisẽgiảm.Nhưvậy,việctìmnướcđitiếptheochotrạngtháicósẵnchỉlàviệctìmkiếmnhữngôtrốngcònlại,đồngthời,khônggiantìmkiếmsẽthuhẹptheosốnướcđiđãtạo...Emnóiđếnđiềunàylàđểsaunàycảitiếnthêmviệcgiatăngđộsâutínhtoánchochươngtrìnhởnhữngnướccờtàn...Nhưvậy,đểchọn1nướcđikếtiếptừ1trạngtháibàncờcósẵn,taphảitìmkiếmnướcđi...Khônggianchọnnướcđitừmỗitrạngtháibanđầulàhữuhạn,nhưngkhônggiantìmkiếm(searchingspace)1nướcđidẫnđếnchiếnthắnglà...hữuhạnluôn(?..hì..?..hì..?..hì...)...nhưngrõràngsốlượngphầntửcủahaikhônggiannàyđuợcsosánhgiốngnhưhạtcátvàsamạc(hoặcnhưtậpsốtựnhiênlàvôhạnđếmđuợc,tậpsốhữutỉcũngvôhạnđếmđuợcnhưngmàsốlượngphầntửcủaQsovớicủaNlà1trời1vực...)...Dođótakhôngthểvétsạchkhônggiantìmkiếmnướcđinày(nếulàmđuợcđiềunàythìlàmgìcònnhữnggiảicờnữa...vìchỉcầnhọcthuộcthếcờlàxong...)màtaphảigiớihạnkhônggiantìmkiếm...Mộtkhônggiantìmkiếmcóthểhiệnthựctheodạng1cáicâyđaphânbìnhthườngnhưtrongDataStructđịnhnghia,lúcnàynóđuợcgọilàcâytìmkiếm,câytròchơi...(SearchingTree,GameTree),mỗinút(Node)cùngmứccủacâynàythểhiệnmộtlựachọncácnướcđicósẵn,mức(Ply)nàysẽthểhiệnchoviệcđánhgiákhoảngcáchtừnútgốcđếnnhữngnútconnày...Nếusốnútởmỗimứccàngnhiều,tứclàcónhiềukhảnăngchọnlựa1nướcđitừ1trạngtháitrước,dođóđộphânnhánh(Branchingfactor)củacâynàycànglớn...Dựavàocáicâytròchơiđãđịnhnghĩaởtrên,việctìmkiếmnướcđilàchọn1núttrêncây(ởmức1)saochonướcđólàtốt(tốtởđâyđuợchiểulàdomìnhđánhgiáthui,vì1nướcđinàylàtốthơnnướcđikiathìphụthuộctrìnhđộ,khảnăngcủangườichơicờ...),theothôngthườngkhichơi,mộtnướcđitốthaykhônglàphụthuộcvàokhảnăngdànhchiếnthắnglàcaohaythấpsaukhinướcđinàyđuợcmade(tứclàđi),dođó,muốnchọn1nướcđitốtthìnếuchỉdựavàothếcờhiệntạilàchưađủ,màphảibiếtthôngtincủanhữngthếcờsaukhichọnnướcnàyđểđi...VídụnhưkhichơitròCarô,cácbáclạichọnmộtnướcđivào1ônàođóđểchậnđuờng3hởhaiđầucủađốithủ(Opponent,Enemy)vìcácbácbiếtlànếukhôngđinuớcnàythìsẽthuaở2nửanướcđitiếptheo,tứclàtrạngtháithuacònchưabiếtđuợcnếungaysaukhichọnđi1ôkhácđểđixuấtpháttrạngtháinày.Kháiniệmđộsâucungnảysinhtừđây,đongiảnthìđộsâu(Depth)làkhảnăngnhìnthấytrước(lookingahead)1nướcđitốtsaumộtloạtnướcđixuấtpháttừhiệntại,vídụnhưnếutừtrạngtháinày,cácbácnhậnbiếtđuợclàsau6connữalàmìnhsẽthắng(tứclàmỗibênđi3con),khiđóđộsâutínhtoáncủacácbá ...