Resources for understanding game trees?

Question

I am trying to make an AI to solve the popular game $2048$, and I think that the theory of game trees would help me quite a bit in this endeavor. The only issue is that most of the results I've found on google are either a bit simplistic, don't really go into enough depth to be helpful, or assume I already know a ton about the topic. Are there any resources, hopefully free, that anybody's found on the topic of game trees?

Answer 1

I would suggest you the following resources:

• Chapter 2 and Chapter 3 of the comprehensive book "The Bounds of Reason: Game Theory and the Unification of the Behavioral Science" by Herbert Gintis, which deal with key concepts of game theory and game tree in a very clear manner;

• "Game Tree Algorithms and Solution Trees" by W.Pijls and A. de Bruin, a paper dedicated to game tree algorithms based upon the concept of "solution tree" (the full text should be available here);

• "A review of game-tree pruning", an interesting paper by T.A. Marsland focused on methods for game-tree searching and pruning, which illustrates several key concepts of game-tree analysis, such as Minimax search, $\alpha-\beta$ algorithm, aspiration and quiescence search, horizon effect, and so on;

• "Improving game-tree search by incorporating error propagation and social orientations" by B. Wilson, a well-structured thesis on the intriguing issue of the so-called game-free pathology, i.e. the study of violations of the assumptions underlying standard search algorithms, with a particular focus on potential biases in the equivalence "deeper search = better decision" and in the assumption of player indifference to opponents'utility;

• "2048-AI", a nice AI by G. Cirillo dedicated to 2048 and for which the code is also available, together with a number of interesting comments in a recent post on Stack Overflow;

• "An AI for 2048", another well-written review published on artent.net, with several interesting hints on how to create an AI for 2048.