| HOME | BLOG | PERSONAL CV | GAMES | DOWNLOADS | LINKS | CONTACT |
|
|
||||||
|
Date: 25 March 2005. This page is DISCONTINUED, but the article and source-code of the program is left below for archival purposes. If you want to play a game just like Hexxagon, please have a look at: WinAttaxx, which is a program I wrote in C#.NET that plays the game of Attaxx.
DATE: 8 May 2003.
I am currently working on 
Project Hexxagon, which is a new hexxagon game that I am
creating in Visual Basic. Please let me know if you have any ideas, currently you can only play against yourself! There is NO Artificial Intelligence in the game yet.
Below is the explanation of older work that I did on the Hexxagon game, when I was programming in Delphi3.
Hexxagon is a 'grab-territory' 2-player board game (multiplayer). You can read the rules of the game here, or here with pictures.
Back in 1998, I programmed a Delphi3 PC version of Hexxagon. Unfortunately, I never really finished the interface of the program. That is probably due to the fact that some other people on the net have build better programs.
Anyway, as I'm not doing alot with the code anymore, you can grab my version of Hexxagon written in Delphi down here.
Download hexxagonfiles (2MB)
Please note though: If you make improvements to the code, please let me know you do and send me a copy.
If you have questions about the software use the contact-page or sent me an email.
In the program I have tried to use the Negascout algorithm. So what's negascout? Well it's an alpha-beta version-like technique to search the game-tree. And I'm sure that when you are still with me and reading this stuff, you know what I mean with a game-tree:-) if not, you'll find plenty of information over here. Anyway, somehow I could not really get that negascout thing to work, and I found the algorithm to be a bit slow.
What I did was speed up the search for a move by disabling certain branches in the search tree. I found this to be a reasonable approach in the game of hexxagon, because once a certain move is found to be not very productive further on in the game, you can safely disregard that move all along. This is because Hexxagon is a very different game from, for example, chess. In chess there are situations where sacrificing a strong piece may yield good results further on into the game. In hexxagon, I found out that these situations are about not existent. Only in some circumstances, when the game is very 'unstable' we have to look far in the future of the game-tree.
Example of an 'unstable position':
1 2 3 4 5
/ / / / / 6
A o x . . x / 7
B . o . o x . / 8
C o x . o . . o / 9
D x . o . . x . x /
E x . . x x . o . o
F . x o . o x . o
G o . x . . x .
H x . . o . x
I o . . . x
A move at B3 for X, could be counterd with a move
at C3 by player O. Making all stones around these
two (yet still empty) positions very unstable.
However, in the game (in practice) there are almost never unstable positions on the whole board. An unstable position would arise when alot of empty squares exist, along with filled squares of different players, like the example above. I call that 'unstable' because all those filled squares (stones) will change sides when a player moves its stone in such an empty square.
Such unstable positions are about never the case on the whole board, but are alot! the case locally, somewhere on the board.
Example of a position with a local 'unstable position':
1 2 3 4 5
/ / / / / 6
A- o . . . o / 7
B- x o o o . . / 8
C- x x x o . . . / 9
D- . . . x . . . . /
E- . . . . . . . . x
F- . . . . . . . .
G- . . . . o . .
H- . . . . o .
I- x . . . o
Player 'o' is to move:
1 2 3 4 5
/ / / / / 6
A- o . . . o / 7
B- x o o o . . / 8
C- x o o . . . . / 9
D- . . O o . . . . /
E- . . . . . . . . x
F- . . . . . . . .
G- . . . . o . .
H- . . . . o .
I- x . . . o
Player 'o' has just played a 'jump-move' C4-D3, hereby grabbing all
stones at the squares around D3.
Now player 'x' is to move.
It should be clear that the action has fully taken place
on the top-left side of the board, and will go on there
for a while. There is no real need to very deeply analyze
moves for 'x' around I5 or E9, or for 'o' in the corner in I9.
And as it seems, those local positions are always the places where both players put in the most effort, because once territory is gained locally, the local unstable position fills up with stones and therefore becomes stable. In the game it is beneficial to have 'safe stones', or 'stable stones', that is, stones that won't change colour every move. So in other words: both players strive for stable territory on the board.
Stable stones for player 'x':
1 2 3 4 5
/ / / / / 6
A- x o o . o / 7
B- x x o o . . / 8
C- x x o . . . . / 9
D- x x x o . . . . /
E- x x o o . . . . x
F- o o o . . . . .
G- O o . . o . .
H- . . . . o .
I- x . . . o
'o' has just jumped G5-G3, closing in all the 'x' squares. But, 'x' has
achieved a very stable position for his stones at the A1-E1 line, while
still able to do a move with the stone on E9.
Note: 'Jumping out in the open' (C2-C4) would grab alot of o-stones,
but 'o' will than happily jump into the position with E4-C2...
The program fuzzily understands that C2-C4 makes the x-stones vulnerable and
will probably prefer moving H4 (taking G3-G4 for 'x').
The way to strive for stability on the board is to fill-up empty squares next to other stones, preferably next to stones of your opponent (H4 for x is such a move).
These fights are local fights untill the board is filled or local positions suddenly 'become' stable.
Jumping stones to the 'empty field' is counter-productive. So, putting/jumping your stowns next to other stones is the best strategy in the game of hexxagon, picking up lots of stones of your opponent of course ;-).
1 2 3 4 5
/ / / / / 6
A- o . . . o / 7
B- x o o o . . / 8
C- x x x o . . . / 9
D- . . . x . . . . /
E- . . . . . . . . x
F- . . . . . . . .
G- . . . . o . .
H- . . . . o .
I- x . . . o
'o' is to move. Jumping C4 to D6 or C6 does not improve the position.
player 'x' would answer with a move to C4 resulting in:
o: C4 - D6, x: C4
1 2 3 4 5
/ / / / / 6
A- o . . . o / 7
B- x o x x . . / 8
C- x x x x . . . / 9
D- . . . x . o . . /
E- . . . . . . . . x
F- . . . . . . . .
G- . . . . o . .
H- . . . . o .
I- x . . . o
Jumping into the 'empty field' is counterproductive.
You'll find this out yourself by playing the game of hexxagon. When examening the source-code, you'll see that the program disregards whole branches of the tree if any of the branches fall out of some 'top-score of branches from the node'. So in the above example, the move C4-D6 would be disregarded once looked 3 moves ahead in the tree, because C4-D3 (and some other moves for 'o') are far better.
This makes it possible to do quite fuzzy-like searches with great depths, making pretty good estimates far up the tree.
/\
/ \
/\ /\
/ \ /\
/\ \ X X
/\ \ /\
/\ \ /\/\
A game-tree. At the bottom are all positions for ALL moves that both 'o' and 'x' can do.
In this example, the program 'knows' to not search ahead in the game-tree at the X-spots,
thereby cutting down the number of to be inspected nodes all the way down the tree.
In short: we are not interested in the sole best move of the given position, we are interested in the flow of the game and we try to look at all the great moves in the game. We're not that interested in that path that sacrifices stones five steps ahead and then takes the whole board back, we simply improve the number of own stones all the way to the end of the game.
First, try beating the pc on the most easy level. This is a great way to understand the game of hexxagon (and yes, you WILL have a hard time beating the pc the first few games, even on the lowest level!) When you've mastered the game, you will get the hang of it. When it's above 'master-level' you will soon find out you can't beat the pc-player. At least, I can't....
(BTW: Does that prove that using a programming language on the pc, I created (artificial) intelligence, that goes even beyond my own capabilities?)
Note: When you press 'PC Move now', the pc is able to change the colours of the stones according to the rules of the game of hexxagon. If you however want to do a move, you will have to change colours yourself by pressing the according left/right mouse buttons as described above. I'm sorry I've never finished the interface of the game, I was only interested in improving the pc-algorithm :-)
Melle Koning