\(n\)-player impartial combinatorial games with random players (Q2513668)

From the author's abstract: ``We develop a method of analyzing \(n\)-player impartial combinatorial games where \(n-1\) players behave optimally while one of the players plays randomly. More specifically, we develop a function \(g_r\) that maps impartial combinatorial games to \(n\)-tuples called game values. A game value of some impartial combinatorial game \(G\) describes the probability that any player can win assuming player \(r\) plays randomly (i.e., player \(r\) chooses games at random without strategy).'' This interesting idea of mixing probability distribution and combinatorial game theory is applied to the analysis of three-player Chomp, whereby the second player plays randomly. Three alternative methods are also discussed: either having more than one single random player or, the random player chooses from an arbitrary distribution over games (as opposed to uniform). This second extension allows the author to model a player who makes correct decisions for ``simple'' instances close to an end while playing randomly for more complex games. Finally, the random player only makes a mistake with probability \(\varepsilon\) and otherwise plays strategically.