Solving NP-Complete Akari games with deep learning

被引：0

作者：

Sbrana, Attilio ^{[1
]}

Bizarro Mirisola, Luiz Gustavo ^{[1
]}

Soma, Nei Yoshihiro ^{[1
]}

Lima de Castro, Paulo Andre ^{[1
]}

机构：

[1] Aeronaut Inst Technol ITA, Dept Comp Sci, Sao Jose Dos Campos, SP, Brazil

来源：

ENTERTAINMENT COMPUTING | 2023年 / 47卷

基金：

巴西圣保罗研究基金会;

关键词：

Deep learning; Puzzle solving; NP-completeness; ALGORITHM;

D O I：

10.1016/j.entcom.2023.100580

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This work proposes a deep learning-based agent that solves 10 x 10 board size puzzle games of the NPComplete Akari genre, while learning tabula rasa, that is, never exposed to any rules of the game. A six-model ensemble is trained to form a single solution policy. Lamp placements are chosen sequentially until the final resolution or failure. For the training and testing of the agent, over 3 million games were randomly produced with at least one known solution. The proposed agent solves 98.1% of Akari games that were never shown to it during training, revealing that the agent can learn implicit rules in NP-complete games. These approaches and training procedures proposed can guide future research on tabula rasa neural network agents for solving games or NP-Complete problems.

引用

页数：8