Section outline

  • V tem sklopu smo si pogledali pristope za igranje nasprotniških iger za dva igralca (razširljivo tudi za več igralcev). Predstavili smo dobri stari algoritem minimax, ki je še vedno osnova za marsikatero igro za katero znamo ustvariti dobro hevristično ocenjevalno fukcijo. Le-ta vodi preiskovanje enako kot pri algoritmih iz prejšnjega poglavja. V nadaljevanju smo predstavili "varno" nadgradnjo osnovnega minimax algoritma, t.j. alfa-beta rezanje. Takšno rezanje je varno, ker zagotovljeno vrne enak rezultat kot minimax, le veliko hitreje. Koliko hitreje lahko vidite v priloženem jupyter zvezku.

    Kot alternativo, ki ne potrebuje hevristične ocenjevalne funkcije, smo spoznali Monte-Carlo pristope. Z večanjem računskih zmogljivosti računalnikov so ti pristopi postali zelo močna alternativa klasičnim pristopom na osnovi minimax algoritma. Demonstrirali smo moč naključnih simulacij, več spet lahko vidite v jupyter zvezku. Preprosti Monte-Carlo pristopi pa ne izkoriščajo najbolje zmogljivosti (časa), ki so jim na voljo. Tako smo si ogledali moderno nadgradnjo MCTS (Monte-Carlo Tree Search), ki večino časa nameni zanimivim kandidatom za naslednjo potezo v igri.

    Na koncu smo si na kratko pogledali pristope AlphaZero, ki kombinirajo MCTS z nevronskimi mrežami in spodbujevalnim učenjem.

    V jupyter zvezku spodaj si lahko ogledate implementacije večine algoritmov na primeru križcev in krožcev ter jih lahko preizkusite v medsebojni igri.