is Íslenska en English

Lokaverkefni (Bakkalár)

Háskólinn í Reykjavík > Tæknisvið / School of Technology > BSc Tölvunarfræðideild / Department of Computer Science >

Vinsamlegast notið þetta auðkenni þegar þið vitnið til verksins eða tengið í það: http://hdl.handle.net/1946/9180

Titill: 
  • Titill er á ensku Investigation of Multi-Cut Pruning in Game-Tree Search
  • Endurmat leitaraðferðarinnar Multi-Cut pruning í tölvuskák
Námsstig: 
  • Bakkalár
Leiðbeinandi: 
Útdráttur: 
  • Útdráttur er á ensku

    Computers have long surpassed humans when it comes to playing chess, but this did not happen overnight. Modern chess programs are the product of decades of research which has predominantly dealt with the topic of game tree search. Consequently, there exist many search enhancement techniques for improving the effectiveness and decision quality of such programs.
    In this report, we give a brief historical overview of how search paradigms in computer chess have shifted over the years. We also present a discussion on game tree search and popular search enhancement techniques. In particular, we investigate one such technique, multi-cut pruning, and introduce enhancements to it. The enhanced technique is implemented in our own chess program and quantitative experiments are carried out which demonstrate a statistically significant improvement over the original technique. Moreover, the enhanced technique is examined in the context of other popular search enhancements like null-move pruning and we find that it complements them much better than its predecessor.

  • Það er langt síðan að tölvur tóku fram úr manneskjunni hvað varðar getu í skák, en þetta gerðist þó ekki á einni nóttu. Nútímaskákforrit eru afurð áratugalangra rannsókna sem varða fyrst og fremst leit í leitartrjám. Ein af afleiðingum þessara rannsókna er fjöldi leitaraðferða sem hjálpa skákforritum sem og öðrum forritum sem nýta sér leit í leitartrjám að taka betri ákvarðanir á styttri tíma.
    Í þessari skýrslu lítum við örstutt á það hvernig helstu einkenni leitar í tölvuskák hafa þróast síðustu áratugi. Við fjöllum einnig almennt um leit í leitartrjám og tökum fyrir nokkrar vinsælar leitaraðferðir og kynnum þær. Sérstaklega tökum við þó fyrir eina leitaraðferð, multi-cut pruning, og kynnum til sögunnar endurbætta útgáfu af henni. Endurbætta útgáfan var útfærð í okkar eigin skákforriti og tilraunir framkvæmdar. Niðurstöður tilraunanna sýna með tölfræðilega marktækum hætti að hún ber höfuð og herðar yfir upprunalegu útgáfuna. Jafnframt skoðum við endurbættu útgáfuna í samhengi við aðrar vinsælar leitaraðferðir eins og null-move pruning en svo virðist sem hún falli þar betur inn en forveri sinn.

Athugasemdir: 
  • Heildartexti lokaskýrslu. Prentuð útgáfa og öll fylgiskjöl á CD eru varðveitt í bókasafni HR
Samþykkt: 
  • 9.6.2011
URI: 
  • http://hdl.handle.net/1946/9180


Skrár
Skráarnafn Stærð AðgangurLýsingSkráartegund 
research-report.pdf469.69 kBOpinnHeildartextiPDFSkoða/Opna
project-report.pdf224.37 kBLokaðurFylgiskjölPDF