AboutWhen I asked somebody if he wants to dare a game he told me: "Only the person who starts the game can win." That is something that can be found out and the question nagged at me if his opinion is right. So I decided to give it a try and solve it by brute force.
This program calculates every possible turn of the game "Vier Gewinnt". For a later version it tries to find out if there is a path where one of the players has no chance to win the game. The program can not be used to play the game, it is only interesting for programmers. It is also not finished yet.
OverviewThe Vier Gewinnt board has 6 rows and 7 columns, that makes 64 chips to put chips in until the game has to terminate.
For every turn, there are 7 columns to choose from. So there are 7 possible play-fields with 1 chip. For the next chip there are again 7 possibilities. It doesn't matter where the first chip was thrown in. So the number of boards with 2 chips is 7*7=49 and so on. So a upper limit of the number of possible combinations can be calculated by 7^(7*6). This is an tremendous amount of calculations that cannot be done in time, these days. But fortunately there are some ways to decrease this number.
In this document, a 4x4 field have been used for a better overview.
Reduction of the number of positions to calculate
Winner DetectionIf one of the players has won, there is no need to continue the calculation of steps after this step. The number of calculation can reduced by a very large amount in this way.
SymmetrySymmetric turns can be eliminated. Here is an example:
Detection of equal Play-fieldsOne combination of chips can occur in different ways. So each board has to be stored and if it has been stored before, the next steps have not to be calculated again.
Elimination of dumb turnsE.g. if one player has 3 chips in the same row, and it's now his turn, he would be dump if he wouldn't throw his next chip in this column to get 4 and wins in this way. So if it's possible to win with one ore more columns, the other columns are not calculated.
This method has been proposed by Oliver Faust.
WhyThe software can be used with the computers RAM as storage for all the turns, but at the moment the program can only store approximately 1 million turns in 80 MBs of RAM. Even if the overhead of the Java classes would be eliminated, only 3 Million ones could be stored. So there is a need to use the hard-disk for storage. And an easy way to do this, is to use the database.
The current version of the software can handle MySQL databases. This database is free for non commercial use, very fast, very stable and well documented. Information and Java drivers can be found at www.mysql.com.
Even, if this software uses the database independent JDBC, it is very high optimized for MySQL. Therefore I don't guarantee that it works with other databases. MS-Access for example won"t work. But if you want to use a different one, it can easily be adapted. Ask me if you need help for it.
I have added a script to the sources, that creates an MySQL account automatically on a Linux machine. The usage is
Multiple DatabasesThe complexity to insert new results in a database is O(n) = n * log n. So if you want to store 4 more results, it takes 6 times longer. On the other hand, if you need to store only a quarter of the data, it is 6 times faster. Therefore I implemented support for multiple databases.
Because the slowest database would slow down the whole process, I have implemented multi-threaded database access and a simple load balancing algorithm. So also your little 486 can do some work.
Please ensure that every computer has enough disk-space, because the failure of one machine halts the calculation.
Database PerformanceThe processor type isn't very important for the performance, but the access speed of the hard-disk and the memory. The latter, because the more RAM a machine has, the more disk-cache can be used. So you will see, that at a certain point when the cachable memory is exceeded, the performance decreases rapidly.
ResultsA 5x5 sized play-field can be calculated completely in this way within 24 hours on a ordinary PC. A larger field is needs a lot of effort at the moment. So, if someone has any proposals, to decrease the number of bytes to store or to speed up the calculation, please let me know. The bottleneck is the data storage.
Log-filesHere are the log-files of the calculation for some play-fields. The calculations are made with different computers and different program versions, so the calculations times are not comparable.
The FutureAt the moment, no attempt has been tried to find out if there is a path, where someone can win, and the other one has no chance. Maybe I'll include this in a later version, but I think the probability to find such a path is very low.
I'll spend some time to write something more about the way, the program works.
Source codeThe code is written completely in Java 1.2. There is one main configuration file VP.java. The configuration is stored as
The makefile has these useful targets:
A database can be used and is the only way to do large calculations. The
code is written for the use with of a MySQL database. I cannot guarantee
that it will work with all databases, because some optimizations to the
SQL statements have been made. But you have still the opportunity to