Systematic N-tuple Networks for Position Evaluation: Exceeding 90% in the Othello League

by Wojciech Jaśkowski
Abstract:
N-tuple networks have been successfully used as position evaluation functions for board games such as Othello or Connect Four. The effectiveness of such networks depends on their architecture, which is determined by the placement of constituent n-tuples, sequences of board locations, providing input to the network. The most popular method of placing n-tuples consists in randomly generating a small number of long, snake-shaped board location sequences. In comparison, we show that learning n-tuple networks is significantly more effective if they involve a large number of systematically placed, short, straight n-tuples. Moreover, we demonstrate that in order to obtain the best performance and the steepest learning curve for Othello it is enough to use n-tuples of size just 2, yielding a network consisting of only 288 weights. The best such network evolved in this study has been evaluated in the online Othello League, obtaining the performance of nearly 96% — more than any other player to date.
Reference:
Systematic N-tuple Networks for Position Evaluation: Exceeding 90% in the Othello League (Wojciech Jaśkowski), Technical report, Institute of Computing Science, Poznan University of Technology, 2014.
Bibtex Entry:
@TechReport{Jaskowski2014systematic,
  Title                    = {Systematic N-tuple Networks for Position Evaluation: Exceeding 90% in the Othello League},
  Author                   = {Wojciech Jaśkowski},
  Institution              = {Institute of Computing Science, Poznan University of Technology},
  Year                     = {2014},

  Address                  = {Poznań, Poland},
  Number                   = {RA-06/2014, arXiv:1406.1509},

  Abstract                 = {N-tuple networks have been successfully used as position evaluation functions for board games such as Othello or Connect Four. The effectiveness of such networks depends on their architecture, which is determined by the placement of constituent n-tuples, sequences of board locations, providing input to the network. The most popular method of placing n-tuples consists in randomly generating a small number of long, snake-shaped board location sequences. In comparison, we show that learning n-tuple networks is significantly more effective if they involve a large number of systematically placed, short, straight n-tuples. Moreover, we demonstrate that in order to obtain the best performance and the steepest learning curve for Othello it is enough to use n-tuples of size just 2, yielding a network consisting of only 288 weights. The best such network evolved in this study has been evaluated in the online Othello League, obtaining the performance of nearly 96% --- more than any other player to date.},
  Eprint                   = {arXiv:1406.1509},
  Keywords                 = {Othello, Reversi, evolution strategy, n-tuple networks, Othello League, tabular value functions, strategy representation},
  Url                      = {http://arxiv.org/abs/1406.1509}
}

This entry was posted by . Bookmark the permalink.