Computational Approaches to the Gold Grabbing Game

Grabbing Game is a game played on a vertex-weighted graph (weights in gold), where two players (Alice and Bob) take turns removing vertices without disconnecting the graph, with Alice starting the game. The winner is the player who accumulates the highest total weight from the chosen vertices. In the literature, it is shown that the Grabbing Game is a problem belonging to the PSPACE-complete class. However, most studies present mathematical approaches focused on gold maximization. This work aims to fill that gap by investigating computational approaches that consider both simple victory and gold maximization. First, an optimal brute-force strategy is proposed along with its algorithmic analysis, highlighting its high computational cost. Then, opti mizations using dynamic programming (DP) are proposed for path graphs and complete bipartite graphs. Greedy approaches are also explored in complete graphs, complete bipartite graphs, and paths, as well as bicoloring strategies in path and cycle graphs.