A Shannon C-type program which plays connect four perfectly
(A C-source code of the bare AI engine is now available)
Velena is a freeware expert system crafted for playing connect four. It's based on eight mathematical rules, each proven to be correct. This implies that also the conclusions made by Velena are correct.
In this way it has been possible to show that connect four is a first player win, and Velena is always able to win if she plays first.
The program is based on the theory of L.Victor Allis presented in his master thesis: "A Knowledge-based Approach of Connect-Four (Allis, 1989)" in which he gives the details on how he was able to show that the game is a first player win. He also wrote a program called Victor which is essentially the same as Velena.
There are however some enhancements in Velena based on PN and PN^2 Search. Detailed explanations of PN search can be found in "Searching for Solutions in Games and Artificial Intelligence (Allis, 1994)"
The combination of the eight rules and the PN-search engine made possible to solve connect four with a reasonable amount of resources. Consider that the game complexity is about 7.1 x 10^13 which is far beyond what are considered reasonable resources. To build up an hexaustive brute force attack, several terabytes of disk space would be required. In addition an enormous amount of time is also indispensable.. Finally it would be impossible to distribute the program.
Instead the theory used here made possible to reduce the search tree to an opening book of about 60,000 positions, which is stored in a file that is less than one megabyte.
Velena is then able to play perfectly in the sense that if she plays first she always win. She's also very hard to beat when she plays the other side. However since it's proven connect four is a first player win, Velena is not unbeatible when she plays second.
System requirements are the following:
An IBM compatible 386 or better computer (suggested 486/DX2)
A SVGA Vesa Compatible (VBE version 1.2 and above) Graphic Adapter
Four megabytes of RAM
An MS-DOS compatible operating system
Click here to download the latest version of Velena (that is V1.07)
Or here for an alternative site which is often faster than official homepage
Click here if you want a brief tutorial about connect four (game rules)
If you have problems with your graphics adapter, you may download a Universal SVGA Vesa Driver.
For example you could try: UniVBE from SciTech
See also: Giuliano Bertoletti's Home Page
I have made available to the public the Velena Engine Source code which is a bare AI engine without the fancy
graphics you see in the official version. It's completly written in C and should compile and run on almost any traditional platform.
Click here to access the Velena source code page
Any comments and suggestions are welcome