Coordination in Complex Intelligent Systems: Why there is “no AI” to predict the World Cup winner
Recent predictions by AI algorithms that predicted Spain or Germany as the World Cup winner have failed miserably. The goal is not to rehash the failures of these algorithms, but to shed light on the underlying “science” behind decision-making, consensus and coordination in teams of agents necessary to model competitive multiplayer games like football.
Football is a perfect example of a complex intelligent system (CIS) in which many agents (players) interact with each other towards a unifying team objective — scoring goals — -while obeying some basic rules and restrictions (constrains).
Many of us have watched football countless of times but rarely do we think of beautiful flocks of birds, or schools of fish as playing a competitive game.
This form of collective behavior of teams of agents existed in nature for thousands of years before football was invented in the form of flocking, schooling, swarming, and herding. The objectives for animals vary from migration, to foraging, attacks, defense, and mating.
The team objectives of animal groups show up as modes of behavior of a football team during a game:
- Exploration: searching for opportunities with organized passing games resembles foraging behavior,
- Attack, and
- Defense.
Unified attack and defense modes are necessary in football when the team discovers opportunities, or advantageous opportunities arise for the opposing team. Tie breaking penalty shots are almost universally disliked as they represent individualistic exchanges between a player from each team — -the team as a whole has no physical involvement in penalty shots, despite emotional support from the two players — the goalie and the striker.
The mathematical theory and algorithms for flocking behavior in complex systems was developed by the author in [1]. This framework heavily relied on consensus strategies for teams of agents communicating over networks [2], [3]. The resulting flocking behavior looks very natural and consistent with how birds flock: each agent at most interacts with a small number of its teammates locally (short passes) or globally (long-range crosses). These algorithms have been extensively used by robotics researchers around the world to create anything from dazzling displays of quadrotor drones by the Intel team to self-driving autonomous vehicles [4].
Interesting, AI or machine learning plays absolutely no role in either explaining or generating collective behavior of flocks. The disciplines that play a critical role include control theory, distributed computing, optimization, nonlinear dynamics, graph theory, algebraic graph theory, geometry of manifolds, Hamiltonian systems, wireless communications, etc.
To over-simplify the science behind any intelligent system or group of agents into a two letter abbreviation “AI” is a huge mistake. It undercuts the real science and engineering behind creating complex intelligent systems; namely, control theory, distributed computing, game theory, optimization, and complex networks plus a large array of computational and mathematical tools.
In a recent blog, Micheal Jordan — the renown machine learning scientist from UC, Berkley — eluciated how control theory had already discovered backpropagation years before it was introduced in machine learning by Paul Werbos in 1974 and the dangers of over-stating the capabilities of AI.
In recent years, Google DeepMind, has been rediscovering the wheel over-and-over by its work on “reinforcement learning” originally discovered by Richard Bellman at Princeton in the early 1960s and called “dynamic programming” [5] — you say tomato, I say tomato. Google has even succeeded to patent such well-known algorithms that have been known to the public for over half a century. Neuro Dynamic Programming [5] published in mid-1990s was the application of neural networks to approximation of value functions in dynamic programming — -something that Google copied with deep learning architectures.
Despite all the limited success by deep Q-learning (another variation of neuro-dynamic programming) on single-player games like Atari 2600 [6] and GO [7], there has yet to be any success in a deep Q-learning algorithm that can play football with 11 player on both teams competing with each other (See the Challenge at the end of the blog).
Contrary to the simplistic cases of single-player board games where the player has a finite set of discrete choices/actions, the choices of a football player is almost endless and by no means discrete in nature. The first step is to reduce these choices is to discretize the game of football in a away that doesn’t detract from the beauty of the free-flowing realistic games. This can be achieved by limiting forward/backward passes to a limited conic view of every player and then probabilistically modeling a pass as sending a wireless packet as amessage that might or might not arrive at the destination (or the target teammate). The same model is applicable to a strike on goal that has a probability of success given the “state” of the game.
As you can see, one can mathematically model a complex game like football but the elements of modeling don’t involve today’s AI technology as AI is extremely premature. Here are the actual necessary elements:
1) Mobility model for the players (a dynamic system similar to the particle model of a bird)
2) Model for the actions of each player
3) Model for inter-agent communications with probabilistic models of passing between players
4) A probabilistic model of strikes on goal
5) Team consensus on modes of collective behavior of the team, i.e. are we in exploration, attack, or defense modes as a team?
6) Capturing transition probabilities between modes of behavior of the team based on external inputs from the opponent
7) Modeling the goalkeeper as a dedicated agent with a primary role
8) Modeling substitutions and obeying the rules based on timing and results
9) Modeling “discrete events” including collisions, tackles, conflicts, penalties, set pieces, corners, throws, delays, and referee decisions (they translate to “hard” constraints in optimization)
10) Modeling the fact that players have limited effective energy (or fuel) to play at full capacity and that changes based on fauls and incidents that have happened during a game
This is by no means an exhaustive list but almost every element that is needed in a realistic model of football in stated. Finally, the most promising approach would be to distributed dynamic programming, or reinforcement learning for the team as a whole with stochastic model of discrete events.
In short, there are four takeaways:
i) today’s AI and machine learning lacks the necessary elements to even model complex systems like football teams (bar unrealistic over-simplifications).
ii) There are many fields of science and engineering that are better suited to address team coordination and decision-making problems than AI and machine learning
iii) Reinvent the wheel at your own risk of staying behind or being ridiculed (loss of credibility and trust by the public)
iv) We are years behind the ability to predict the results of the world cup.
Enjoy the rest of the World Cup games and don’t fall for the hype in AI.
Open Challenge:
I hereby challenge the Google DeepMind team to predict the results of this year’s World Cup based on their deep reinforcement learning technology. Atari is kids play, why don’t you flex your AI muscles in a game that adults love to watch and play: Football. Here are some basic advantages of Google:
a) You have the entire history of football as “data”, I think it’s fair to say that’s “big” enough!
b) You claim to be the leading company in image/video processing. that should give you plenty of advantage to parse video of games in the current or past World Cups or league games to obtain the necessary data for training the predicive models of actions by the players.
c) You have three months to complete this challenge! Post the links to your solutions as a comment, or directly submit them to me.
Feel free to use the “hints” in this blog. Good luck! :)
References:
[1] Olfati-Saber, Reza. “Flocking for multi-agent dynamic systems: Algorithms and theory.” IEEE Transactions on automatic control 51, no. 3 (2006): 401–420.
[2] Olfati-Saber, Reza, and Richard M. Murray. “Consensus problems in networks of agents with switching topology and time-delays.” IEEE Transactions on automatic control 49, no. 9 (2004): 1520–1533.
[3] Olfati-Saber, Reza, J. Alex Fax, and Richard M. Murray. “Consensus and cooperation in networked multi-agent systems.” Proceedings of the IEEE 95, no. 1 (2007): 215–233.
[4] Iftekhar, Lamia, and Reza Olfati-Saber. “Autonomous driving for vehicular networks with nonlinear dynamics.” In Intelligent Vehicles Symposium (IV), 2012 IEEE, pp. 723–729. IEEE, 2012.
[5] Bellman, Richard. “Dynamic programming treatment of the travelling salesman problem.” Journal of the ACM (JACM) 9, no. 1 (1962): 61–63.
[6] Bertsekas, Dimitri P., and John N. Tsitsiklis. “Neuro-dynamic programming: an overview.” In Proceedings of the 34th IEEE Conference on Decision and Control, vol. 1, pp. 560–564. Piscataway, NJ: IEEE Publ., 1995.
[7] Mnih, Volodymyr, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves et al. “Human-level control through deep reinforcement learning.” Nature 518, no. 7540 (2015): 529.
[8] Silver, David, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser et al. “Mastering the game of Go with deep neural networks and tree search.” nature 529, no. 7587 (2016): 484.