Using Go in teaching the theory of computation

Research output: Contribution to journalArticleResearch

Abstract

With increased public interest in the ancient game of Go since 2016, it is an especially good time to use it in teaching. The game is an excellent source of exercises in the theory of computation. We give some exercises developed during our research on Go which were then used when teaching this subject at Monash University. These are based on One-Dimensional Go (1D-Go) which uses a path graph as its board. They are about determining whether or not a position is legal and counting the number of legal
positions. Curriculum elements that may be illustrated and practised using 1D-Go include: regular expressions, linear recurrences, proof by induction, finite automata, regular grammars, context-free grammars and languages, pushdown automata, and Turing machines.
Original languageEnglish
Pages (from-to)65-78
Number of pages14
JournalSIGACT News
Volume50
Issue number1
DOIs
Publication statusPublished - Mar 2019

Keywords

  • theory of computation
  • Go
  • Weiqı
  • Baduk
  • game
  • legal position

Cite this