# A Review: Machine Learning for Combinatorial Optimization Problems in Energy Areas
## 3 Learning to Solve COPs
### Improvement RL
#### 3.1.3 Game Theoretic Methods  
Single-Player Game  
Some COPs are modeled as reinforcement learning problems, in which the idea of single-player games and self-play can be applied. [PERSON] et al. [89] used the concept of self-play on 2D and 3D BPP problems and proposed the ranked reward algorithm. When applying MCTs to solve a BPP problem modeled as MDP, the reward for all non-terminal states is usually set to 0 and for the terminal state, is obtained according to the quality of the solution. [PERSON] et al. reshaped the reward function by storing the agent's recent performance against which new solutions are compared, earning the reward related to whether or not it outperformed itself. In this approach, ranked reward reproduces the benefits of self-play for single-player games, removes the requirement of training data, and obtains a well-suited adversary. Experiments show that it outperforms ranked-free strategies on BPP problems. [PERSON] et al. [250] proposed a method to transform certain COPs into Zermelo games to use self-play-based neural MCTS. The Zermelo game is a two-player, finite information game with perfect information. During the game, two players alternate actions, and finally one wins and one loses. [PERSON] et al. modeled a type of COP (the highest safe rung (HSR) problem (Highest safe rung (HSR): consider throwing jars from a specific rung of a ladder where the jars could either break or not. If a jar is unbroken during a test, it can be used next time. The highest safe rung is a rung that for any test performed above it, the jar will break.)) as a Zermelo game, mainly using its recursive property. The state-space convergence and solution quality of the algorithm prove to be good, but it faces the common time-consuming problem of the neural MCTS algorithm. [PERSON] et al. [90] modeled some COPs of choosing edges over graphs as a single-player game, represented by a decision tree. [PERSON] et al. used the graph attention network to encode the line-graph variant of the original graph, and then used the attention mechanism to select actions (add/remove an edge). Finally, they updated the network weights through the evaluation oracle of the leaf nodes, where perfect information game theory proved that a similar mechanism could approximately converge to an optimal policy. [PERSON] et al. conducted experiments on four problems of minimum spanning tree, shortest path, TSP, and VRP, and demonstrated linear running times with good optimality gaps. Competitive Game  
[PERSON] et al. [91] regarded each strategy of the TSP problem as a player and iteratively updated them through competition and reinforcement to obtain the optimal strategy. Specifically, [PERSON] et al. first randomly initialized some strategies, each of which has a payoff equal to 0. In each round of iteration, for the player \(X_{i}\), an opponent player \(X_{j}\) is chosen to compare; if \(X_{j}\) wins, then \(X_{i}\) imitates the strategy of \(X_{j}\) (copy some sequence from the opponent) to update itself, and rewards the winning player according to probabilistic utility theory, otherwise, \(X_{i}\) updates itself according to the current global best player and the local best player (the strongest strategy that \(X_{i}\) has explored). If the update does not exceed its previous performance, the strategy of \(X_{i}\) is updated again with a local search strategy 2-opt. Cooperative Game  
In tasks involving cooperation among multiple agents, the concept of equilibrium and communication in game theory tends to lead to good solution quality. [PERSON] et al. [92] proposed to use probability collectives to solve the small-scale multi-depot multiple traveling salesmen problem (MDMTSP). This method is a kind of cooperative approach, and the main idea is to treat each salesman as an agent, and each route as a strategy that forms an agent's strategy set.