Systematic N-Tuple Networks for Othello Position Evaluation

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 this paper, we show that learning n-tuple networks is more effective if it involves, instead, a large number of systematically placed, short, straight n-tuples. In addition, we demonstrate that a simple variant of coevolutionary learning can evolve a systematic n-tuple network with tuples of size just 2 of a comparable performance to the best 1-ply Othello players. Our network consists of only 288 parameters, which is an order of magnitude less than the top published players to date. This indicates a need for more effective learning methods that would be capable of taking a full advantage of larger networks.
Reference:
Systematic N-Tuple Networks for Othello Position Evaluation (Wojciech Jaśkowski), In ICGA Journal, volume 37, 2014.
Bibtex Entry:
@Article{Jaskowski2014ICGAsystematic,
  Title                    = {Systematic N-Tuple Networks for Othello Position Evaluation},
  Author                   = {Wojciech Jaśkowski},
  Journal                  = {ICGA Journal},
  Year                     = {2014},

  Month                    = {June},
  Number                   = {2},
  Pages                    = {85--96},
  Volume                   = {37},

  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 this paper, we show that learning n-tuple networks is more effective if it involves, instead, a large number of systematically placed, short, straight n-tuples. In addition, we demonstrate that a simple variant of coevolutionary learning can evolve a systematic n-tuple network with tuples of size just 2 of a comparable performance to the best 1-ply Othello players. Our network consists of only 288 parameters, which is an order of magnitude less than the top published players to date. This indicates a need for more effective learning methods that would be capable of taking a full advantage of larger networks.},
  Keywords                 = {Othello, Reversi, evolution strategy, n-tuple networks, tabular value functions, strategy representation, board features, agent policy},
  Url                      = {http://www.cs.put.poznan.pl/wjaskowski/pub/papers/jaskowski2014ICGAsystematic.pdf}
}

This entry was posted by . Bookmark the permalink.