João Pedro Neto is co-author of the paper “Disjunctive sums of quasi-nimbers” published in top-ranked journal Theoretical Computer Science (h5-index: 35). The paper is first-authored by Alexandre Silva (University of Minho) and also co-authored by Carlos Pereira dos Santos (FCT NOVA), and Richard J. Nowakowski (Dalhousie University).

The paper presents a study on Combinatorial Game Theory (CGT). CGT studies two-player games, with perfect information and no chance device. A common, almost defining feature, is that these games often decompose into sub-components and a player is only allowed to move in one of these at each stage of play. This situation is called a disjunctive sum of games. It is also commonplace to allow addition of games with similar and well defined properties, games in such a family do not necessarily need to have the same rule sets. Another relevant term herein is the concept of nimber; formally ∗n ={0, ∗, ∗2, …, ∗(n −1)}, each value representing a finite heap in the classic game NIM.

PAINT CAN is an example of a CGT game whose positions are disjunctive sums, and a move in any component reduces that component to a nimber. John H. Conway, in On Numbers and Games, partially analyzed the related game supernim, and called these components “superstars”, mentioning “There does not appear to be a complete theory”. The book contains one result about these games, and, until now, there has been no advance in finding good strategies. In the paper, the researchers show that, for a human, the use of canonical forms is not a good approach. The researchers present an algorithmic, recursive approach to the general case, based on a fundamental reduction of these positions, as well as on a Nimber Avoidance Theorem. An analysis of the computational time of the algorithm is presented.

The paper is available here.