Enhancing Chess Reinforcement Learning with Graph Representation

Summary

The paper introduces a new variant of AlphaZero, AlphaGateau, with a neural network architecture based on GNNs, that allows the model to generalize across board sizes. The new architecture outperforms the original AlphaZero architecture under certain conditions.

Strengths

The paper follows a promising direction, using GNNs in an AlphaZero-like model to utilize the graph nature of many board games. AlphaGateau is an original model that shows potential in terms of data efficiency and fast training. It learns much faster than AlphaZero during the first 100 training iterations, saturating at a much higher Elo compared to that of AlphaZero, which does not improve much in this timeframe. It is clear that when both models are tested on equal grounds, in the setting used, AlphaGateau is significantly more data efficient, and improves its Elo score much faster than AlphaZero. These are significant improvements on the original AlphaZero model if they hold under rigorous evaluation.

Weaknesses

Evaluation & comparison with AlphaZero: While figure 5 clearly shows that AlphaGateau learns much faster than AlphaZero at early training, the paper does not provide any information on how the two models compare when they are fully trained. AlphaGateau seems to reach a performance plateau within 100 steps, but the AlphaZero model trained by the authors would likely keep on improving for orders of magnitude more training steps. For comparison, the authors used a model size roughly 10% of Silver et. al.'s AlphaZero, but trained for 100 steps compared to the original 700,000 steps. It is not clear if AlphaGateau's performance will be comparable with AlphaZero, given enough training steps. I am aware that training the models for 10^5 steps is extremely expensive and not feasible for this paper. Even so, the correct solution would have been to fit the model size to the training budget and train a significanly smaller AlphaZero model, for longer time and on smaller batches (or to heavily reuse training data between optimization steps). Doing a comparison of smaller-scale models could show if AlphaGateau is a comparable model to AlphaZero. In the paper's current form, the reported Elo gap does not give the reader any knowledge about how AlphaGateau compares to a fully-trained AlphaZero, since Elo calculation is unreliable when using such large gaps. For example, the gap between the best performing AlphaGateau and best AlphaZero is about 1,500 Elo, meaning that AlphaZero would win about 1 game in every 7,500 games. This implies that the AlphaGateau Elo score is based purely on comparisons with earlier AlphaGateau training checkpoints. Another example is the gap between the first and second checkpoints, which is hard to measure by eye due to the plot format but looks roughly equal to 800. This gap implies the weaker model wins 1 game in 100, suggesting that the error of this gap is very high unless the authors use thousands of test games between this specific checkpoint pair to calculate Elo. I couldn't find the number of Elo games in the paper, and would recommend stating it clearly. Considering that the best model's Elo is probably based purely on comparisons to its earlier versions, and considering the possible error of the Elo estimate, it is possible that AlphaGateau's Elo rating will drop significantly if fully-trained AlphaZero models are added to the pool of players. This paper will benefit significantly from fitting the size of the experiments to the compute resources available to the authors. I would suggest training significanly smaller models for 100x more training steps, using the same compute budget. In its current form, the paper only showcases the advantage AlphaGateau has in terms of data-efficiency at early training, in a regime where AlphaZero is severely undertrained.

Questions

- What hyperparameters are used to calculate Elo scores? (number of models tested, number of games between each model pair, who played against who) Three minor suggestions: - It would be helpful for the reader if figures 5 and 6 had FLOPs on the x-axis instead of steps, or if training compute was reported. Plotting only steps, it is hard to understand if one training step of AlphaGateau is comparable to a training step of AlphaZero in terms of compute. - It would be easier and more convincing to use traditional methods for calculating Elo scores, such as BayesElo which was used by Silver et. al. That said, the authors provide clear explanations on their Elo calculation method. - The correct spelling of the metric is "Elo", named after Arpad Elo, rather than "ELO", which is a common typo.

Rating

5

Confidence

4

Soundness

1

Presentation

3

Contribution

3

Limitations

No limitations other than those specified above regarding evaluation.

Summary

The paper explores a novel approach to reinforcement learning for Chess by utilizing a graph-based representation of the game state instead of the traditional grid-based representation. This method is based on GNNs and aims to overcome the limitations of CNNs used in previous models like AlphaZero. Specifically, the paper introduces the Graph Attention neTwork with Edge features from Attention weight Updates (GATEAU) layer, which enhances the classical GAT layer by incorporating edge features. The primary contributions of the paper include demonstrating that the new architecture outperforms previous models with a similar number of parameters and significantly accelerates the learning process. Additionally, the paper provides evidence that the model trained on a smaller variant of chess (5x5) can be quickly fine-tuned to perform well on the standard 8x8 chessboard, indicating promising generalization capabilities. The authors have made their code available, supporting the reproducibility of their experiments and findings.

Strengths

**Novel Graph-based Approach**: This paper introduces a creative way to represent game states using a graph-based model instead of the traditional grid-based models. By employing Graph Neural Networks and the Graph Attention neTwork with Edge features from Attention weight Updates, the authors address significant limitations found in Convolutional Neural Networks used in models like AlphaZero. **Improved Learning Efficiency**: The proposed AlphaGateau model demonstrates much faster learning compared to traditional CNN-based models. Experiments show that AlphaGateau can achieve a significant increase in playing strength in a fraction of the training time required by AlphaZero, which is a notable improvement in learning efficiency. **Reproducibility**: The authors have made their code publicly available, supporting the reproducibility of their experiments.

Weaknesses

**Limited Generalization Evidence**: The paper claims promising generalization capabilities, but the experimental evidence is limited to a small variant of chess (5x5) and standard chess (8x8). It would strengthen the paper to include additional experiments on other games or variants, such as Shogi or other board games with similar complexity, to demonstrate the broader applicability of the proposed architecture. **Comparative Analysis**: The paper lacks a thorough comparative analysis with other state-of-the-art models beyond AlphaZero. Including comparisons with recent advancements in graph-based reinforcement learning models would provide a clearer picture of the relative performance and innovations of the proposed method. **Real-world Applicability**: While the focus is on reinforcement learning in chess, discussing potential real-world applications of the proposed graph-based approach would broaden the impact of the work. Highlighting areas where this approach could be applied, such as other strategic games or decision-making problems in different domains, would make the contributions more compelling.

Questions

1. How does AlphaGateau compare to other graph neural network-based reinforcement learning models, such as those presented by Ben-Assayag and El-Yaniv (2021) [1]? 2. Have the authors considered applying AlphaGateau to other strategic games beyond chess? If so, what preliminary results or observations can the authors share? 3. What potential real-world applications besides chess do the authors envision for the graph-based approach proposed in this paper? [1] Ben-Assayag, S., & El-Yaniv, R. (2021). Train on small, play the large: Scaling up board games with alphazero and gnn. *arXiv preprint arXiv:2107.08387*.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

The authors have acknowledged some limitations of their work, such as the restricted computational resources which prevented the training of deeper networks, and their focus solely on chess without extending experiments to other games. They also discussed challenges related to the reproducibility of their results due to the non-deterministic nature of parallelized GPU code. However, the paper could benefit from a deeper discussion on the broader implications of these limitations, particularly how they might affect the generalizability and robustness of the proposed method. Regarding potential negative societal impacts, the paper does not explicitly address this aspect.

Summary

The authors demonstrate a GNN that works on chess and is amenable to generalization.

Strengths

# originality This is the first chess GNN approach that performs well that I'm aware of in the literature, and requires some invoations in the edge representation. # quality The results look good, although the computational limitation of the work mean that a larger test would be good to demonstrate that this model scales up. # clarity The paper is clear and readable. # significance This is a new result in chess AI and looks like it could matter to the larger RL community. I'm not sure this will impact much chess engines in practice though as the GNN is likely much harder to optimize and implement than CNNs or heuristics, the memory usage on the attention mechanism for example would make implementing this in a high performance search code-base difficult.

Weaknesses

The authors only look at self-play for model training, the original AlphaGo models were trained on human games to establish that the algorithm performed well, before starting the much more expensive self-play training. The lack of supervised training evaluations is makes the claims of strong performance limited to a single axis (sample efficiency). This result mostly seems to arise from chess specific optimizations applied to an existing algorithm [18], while the authors suggest that it could be applied to other games they only provide evidence in chess. The fine tuning results require more training time (and thus I'm assuming compute) than the initial training, this suggests the pre-training while beneficial is of limited efficacy unless it can be made more efficient. I'm also concerned with the attention-based pooling leading degrading in performance when the graph gets larger as chess is a game that cares much more about the max than the average. I would have liked to see a more complete training run, but I understand that RL is very compute intensive so am not using this lack to negatively impact my score.

Questions

Is the MCTS process identical between AlphaGateau and AlphaZero models? Or does the graph representation change it? Could the graph representation be leveraged to allow a different search algorithm? Could the authors provide PGNs with model predictions and some discussion of the difference in the AlphaGateau and AlphaZero models? There are patterns that CNN based models are good at learning and some that are more difficult (see [1] for examples) and showing differences in the models would strengthen this result. Does the model handle the white bishop well when scaled up? If it does that would be additional evidence of generalization when scaling up since the moves would not have been seen before. Can you provide more details on the Elo calculation? You use the terms ELO and elo and seem to refer to a varation of the Elo rating system created by Arpad Elo, but don't give much details beyond the optimizer. Are you using and Elo or Glicko (2) type system or something else? Section A has not citations so it's unclear. [1] McGrath, T., Kapishnikov, A., Tomašev, N., Pearce, A., Wattenberg, M., Hassabis, D., Kim, B., Paquet, U. and Kramnik, V., 2022. Acquisition of chess knowledge in alphazero. Proceedings of the National Academy of Sciences, 119(47), p.e2206625119.

Rating

7

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

Discussed above

Discussion Period

Hi all! Just your friendly area chair checking in. First, thanks to the reviewers for your work so far on this paper. The discussion period has begun, which includes both reviewers and authors. This is our opportunity to clear up misunderstandings, get answers to questions, and generally gather enough information to make an informed decision grounded in the acceptance criteria. This paper has a sizable spread of overall assessments from the reviewers. It seems there is general agreement that the approach in the paper is interesting and promising. The main critiques raised seem to concern lack of support for claims of generality, the size of the model and extent of training (which may not cover asymptotic performance comparisons), and the validity of the ELO ratings and comparisons. Does this seem like a fair summary? Reviewers: please carefully read the other reviews and the authors' responses (with included PDF) and let us know what follow-up questions you have and to what extent your evaluation might change as a result of the additional context. Please especially raise any points of disagreement with other reviewers or the authors, as these are opportunities for us to clarify misunderstandings and detect misconceptions.