Although simple individually, artificial neurons provide state-of-the-artperformance when interconnected in deep networks. Unknown to many, there existsan arguably even simpler and more versatile learning mechanism, namely, theTsetlin Automaton. Merely by means of a single integer as memory, it learns theoptimal action in stochastic environments. In this paper, we introduce theTsetlin Machine, which solves complex pattern recognition problems witheasy-to-interpret propositional formulas, composed by a collective of TsetlinAutomata. To eliminate the longstanding problem of vanishing signal-to-noiseratio, the Tsetlin Machine orchestrates the automata using a novel game. Ourtheoretical analysis establishes that the Nash equilibria of the game arealigned with the propositional formulas that provide optimal patternrecognition accuracy. This translates to learning without local optima, onlyglobal ones. We argue that the Tsetlin Machine finds the propositional formulathat provides optimal accuracy, with probability arbitrarily close to unity. Infour distinct benchmarks, the Tsetlin Machine outperforms both Neural Networks,SVMs, Random Forests, the Naive Bayes Classifier and Logistic Regression. Itfurther turns out that the accuracy advantage of the Tsetlin Machine increaseswith lack of data. The Tsetlin Machine has a significant computationalperformance advantage since both inputs, patterns, and outputs are expressed asbits, while recognition of patterns relies on bit manipulation. The combinationof accuracy, interpretability, and computational simplicity makes the TsetlinMachine a promising tool for a wide range of domains, including safety-criticalmedicine. Being the first of its kind, we believe the Tsetlin Machine willkick-start completely new paths of research, with a potentially significantimpact on the AI field and the applications of AI.