Combinatorial explosion in games

Artificial Intelligence is researched since decades. From the 1950s to the 2010s a huge amount of projects and papers were generated about the subject. Even for experts on the fields its impossible to list all the subjects. It seems, that there is no clear leading paradigm inside AI research.

The only true rock solid paradigm are the unsolved problems within AI. Namely the Combinatorial explosion in games is repeating pattern over decades. In the 1950s a simple strategy game like Tictactoe was hard to solve for computers and the same situation is there in 2010s. The different AI related theories about expert systems, search algorithms and Qlearning policies are trying mostly to overcome Combinatorial explosion in games.

The reason why so many different theories are available is because its unclear how to do so. The disappointing situation has to do with a large state space in games like chess and the slow performing computer hardware. The typical situation in the last decades of AI research was, that a certain algorithm will need too much CPU ressources while figuring out the optimal action. Especially in robotics based on motion planning this problem is the constant bottleneck.

The interesting situation is, that every generation of AI researchers has struggled with the same bottleneck. Early attempts to play games for example with the Monte carlo tree search algorithm resulted in huge CPU consumption, while later more advanced attempts to control robots with Refinforcement learning algorithm resulted also in huge CPU consumption. The reason was that the underlying cause (the combinatorial explosion) remains unsolved. If the task for a computer is to investigate a graph with 10 billion nodes, the computer has always a long runtime. The problem is too big for the machine.

The good news is, that the situation can be summarized into a simple question: How to solve np hard problems? Thats the only interesting question within AI in the last 50 years. All the other topics in AI research, e.g. neural networks, planning algorithms or pattern recognition are only sub-problems of this overall challenge.