3 ms·
In 1989, Victor Allis "solved" the game of Connect 4, proving (apparently) that the first player can always force a win, even if both sides play perfectly. In
by superbatfish 9y ago
In 1989, Victor Allis "solved" the game of Connect 4, proving (apparently) that the first player can always force a win, even if both sides play perfectly.
In 1996, Giuliano Bertoletti implemented Victor Allis's strategy in a program named Velena:
http://www.ce.unipr.it/~gbe/velena.html http://www.ce.unipr.it/~gbe/velena.html
It's written in C. If someone can get it to compile on a modern system, it would be interesting to see how well the AlphaZero approach fares against a supposedly perfect AI.
- gwern 9y agoTo benchmark A0 further, you can take whatever NN you're training and instead train it against the 'ground truth' of Velena's moves when going first (the NN predicts for each possible move if Velena would take it or not, 0/1 labels). Then one can know how close does the A0 NN trained via expert iteration approaches the Velena-supervised NN and how much compute is spent on the need to train from scratch?
- tromp 9y agoThe Fhourstones benchmark at http://tromp.github.io/c4/fhour.html http://tromp.github.io/c4/fhour.html solves the 7x6 game in under 2 minutes. The "make C476" version at https://github.com/tromp/fhourstones88 https://github.com/tromp/fhourstones88 also maintains a book, allowing for much faster replies.