Content:

Vier Gewinnt

About

When 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.

Mathematical Theory

Overview

The 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 Detection

If 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.

Symmetry

Symmetric turns can be eliminated. Here is an example:

O	O	O	O
O	O	O	O
X	O	O	O
X	O	O	X

<=>

O	O	O	O
O	O	O	O
O	O	O	X
X	O	O	X

The number of turns can be reduced by 50% in this way.

Detection of equal Play-fields

One 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.

For example:

O O O O
O O O O
O O O O
X X X O

This play-field can be achieved in two ways:

O O O O
O O O O
O O O O
X O O O

=>

O O O O
O O O O
O O O O
X X O O

=>

O O O O
O O O O
O O O O
X X X O

and

O O O O
O O O O
O O O O
O O X O

=>

O O O O
O O O O
O O O O
O X X O

=>

O O O O
O O O O
O O O O
X X X O

So after calculating the second way, it is possible to detect that all following steps have been calculated before. The path ends here.

Elimination of dumb turns

E.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.

For example:

O O O O
O O O O
X X X O
X X X O

If the red player has now it's turn, there are 4 possible columns. But only the one is calculated, that leads to a finished game, in this case column 4. Columns 1-3 are ignored.

This method has been proposed by Oliver Faust.

Database support

Why

The 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 VierGewinntDBAdmin . create creates a database and makes it only accessible with a username and password. Both can be changed in the script. drop removes the database and access information completely.

Multiple Databases

The 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 Performance

The 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.

Results

A 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-files

Here 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.

4x2 5x2 6x2 7x2 8x2

4x4 5x4 6x4
4x5 5x5
4x6
4x7
4x8

The Future

At 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 code

The code is written completely in Java 1.2. There is one main configuration file VP.java. The configuration is stored as final public static class members to give the compiler the chance to remove unneeded code. The disadvantage is, that all old class files must be removed after a change to VP.java, to ensure that the new constant values are used in the other classes.

The makefile has these useful targets:

all Compiles the code
run Compiles the code and starts the compilation
test Compiles the code and starts a class for self testing. This is useful if you have applied changes, and you want to find out if everything is still calculated in the right way.

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 edit the VierGewinntDB class.

Download code

Michael Habermann