Editing Game tree (section)

===Randomized algorithms version===
[[Randomized algorithm]]s can be used in solving game trees. There are two main advantages in this type of implementation: speed and practicality. Whereas a deterministic version of solving game trees can be done in {{math|''Ο''(''n'')}}, the following randomized algorithm has an expected run time of {{math|''θ''(''n''<sup>0.792</sup>)}} if every node in the game tree has degree 2. Moreover, it is practical because randomized algorithms are capable of "foiling an enemy", meaning an opponent cannot beat the system of game trees by knowing the algorithm used to solve the game tree because the order of solving is random.

The following is an implementation of randomized game tree solution algorithm:<ref name="Roche2013">{{cite book | author = Daniel Roche | author-link = Daniel Roche | year = 2013 | title = SI486D: Randomness in Computing, Game Trees Unit | publisher = United States Naval Academy, Computer Science Department | url = http://www.usna.edu/Users/cs/roche/courses/s13si486d/u03/ | access-date = 2013-04-29 | archive-date = 2021-05-08 | archive-url = https://web.archive.org/web/20210508074443/https://www.usna.edu/Users/cs/roche/courses/s13si486d/u03/ | url-status = dead }}</ref>

<syntaxhighlight lang="python">
def gt_eval_rand(u) -> bool:
    """Returns True if this node evaluates to a win, otherwise False"""
    if u.leaf:
        return u.win
    else:
        random_children = (gt_eval_rand(child) for child in random_order(u.children))
        if u.op == "OR":
            return any(random_children)
        if u.op == "AND":
            return all(random_children)
</syntaxhighlight>

The algorithm makes use of the idea of "[[Short-circuit evaluation|short-circuiting]]": if the root node is considered an "{{mono|OR}}" operator, then once one {{mono|True}} is found, the root is classified as {{mono|True}}; conversely, if the root node is considered an "{{mono|AND}}" operator then once one {{mono|False}} is found, the root is classified as {{mono|False}}.

<ref>{{Cite journal|last1=Pekař|first1=Libor|last2=Matušů|first2=Radek|last3=Andrla|first3=Jiří|last4=Litschmannová|first4=Martina|date=September 2020|title=Review of Kalah Game Research and the Proposition of a Novel Heuristic–Deterministic Algorithm Compared to Tree-Search Solutions and Human Decision-Making|journal=Informatics|language=en|volume=7|issue=3|pages=34|doi=10.3390/informatics7030034|doi-access=free|hdl=10084/142398|hdl-access=free}}</ref>{{clear}}