Performance of a multi-agent greedy algorithm in a cooperative game with imperfect information

Abstract

Artificial Intelligence (AI) is slowly integrating into our everyday lives. Some of these AI applications must cooperate with humans and each other. Such cooperation is essential for the safety of people in contact with these AIs. This proves to be difficult, due to the sheer amount of uncertainty in the real world. The virtual environments in games are a safe starting place for the research and development of AI capabilities such as cooperation in imperfect information environments. However, cooperative games with imperfect information are an uncommon topic for AI, which is why we have researched such a game called The Crew. We implemented the card game into a program and made an AI that can play it using different algorithms. We experimented with a random algorithm, a cooperative multi-agent greedy algorithm called CoopGreedy, and a competitive multi-agent greedy algorithm called CompGreedy. These algorithms also incorporated heuristics to improve their performance. Our results showed that CoopGreedy outperformed the other algorithms considerably. CoopGreedy in combination with the Expected Value Hand Estimation Heuristic and the Longest Suit Higher Card Goal Selection Heuristic also noticeably improved performance. We also found that CoopGreedy performed better with perfect information than with imperfect information. Our findings indicate that cooperation and heuristics improved performance significantly, but that imperfect information impedes AI performance. We can derive from our experiment that CoopGreedy could be used as a benchmark algorithm for further research. We recommend future research on local search and learning algorithms for The Crew.