Implementing 3D Tic-Tac-Toe game in Visual Basic
Sometimes looking at past and what you did before makes you happy. Yesterday I was deleting some test projects from my Visual Studio 2003 projects folder and saw my old 3D XO (Tic-tac-toe) game. I wrote it in cloudy years (inspired from a famous novel by Ali Ashraf Darvishian) in university when I had Data Structures course. It was one of my projects for this course.
Always I love practices and writing uncommon codes because they force me to think and design. Most of things developers code everyday can be coded by using some patterns.
To write this game I followed a famous algorithm for all 2D XO games which is written based on Game Trees. I extended it for 3 dimensions. In a nutshell this was my algorithm:
- Create a node structure to save a 3D array of chars (for "X" or "O"), a pointer to a child node (the header node of child Link List), a pointer to next node in current Link List and an integer value for turn.
- Start with an initial node as root.
- Generate all childes for root by adding all possible values for next node based on turns and add these nodes as a Link List the child node of root.
- Recursively do previous step for all nodes in this Link List until we can't add new item to game array.
- Find the best path from root to a leaf by performing a MinMax or MaxMin function on node. These functions need a static function to assign a number to each node by finding the number of possible positions for rival (in this case human) in next turn. Larger number is better position.
3-dimensional game needs more nodes so needs a good memory management especially in some iterative functions such as the function to test the win of one player or static function. There are some techniques to have less calculations finding symmetric nodes and ignore them.
In 3-dimensional game first player can win the game easier than second one if he chooses the center position. These are some more resources about game trees and Tic-tac-toe game: 1, 2, 3.
This was my node structure:
Friend Class TreeNode
Public Board(3, 3, 3) As Char
Public Turn As Integer
Public Son As TreeNode
Public NextNode As TreeNode
End Class
And my main class to find the best path to win the game from user:
Public Class GameTree
Sub New()
End Sub
Private Function GetNode(ByRef Board(,,) As Char, _
ByVal Turn As Boolean) As TreeNode
Dim Node As New TreeNode
Board.Copy(Board, Node.Board, Node.Board.Length)
Node.Turn = Turn
Return Node
End Function
Public Sub NextMove(ByVal Board(,,) As Char, _
ByVal LookLevel As Integer, ByVal Player As Char, _
ByRef NewBoard(,,) As Char)
Dim ptree As New TreeNode
Dim best As New TreeNode
Dim Value As Integer
ptree = BuildTree(Board, LookLevel)
BestBranch(ptree, Player, best, Value)
best.Board.Copy(best.Board, NewBoard, _
best.Board.Length)
End Sub
Private Function BuildTree(ByVal Board(,,) As Char _
, ByVal LookLevel As Integer) As TreeNode
Dim ptree As New TreeNode
Board.Copy(Board, ptree.Board, _
ptree.Board.Length)
ptree.Turn = 1
ptree.Son = Nothing
ptree.NextNode = Nothing
Expand(ptree, 0, LookLevel)
Return ptree
End Function
Private Sub Expand(ByRef P As TreeNode, _
ByVal PLevel As Integer, ByVal Depth As Integer)
Dim q As New TreeNode
If PLevel < Depth Then
q = Generate(P.Board, -(P.Turn))
P.Son = q
While Not (q Is Nothing)
If P.Turn = 1 Then
q.Turn = -1
Else
q.Turn = 1
End If
q.Son = Nothing
Expand(q, PLevel + 1, Depth)
q = q.NextNode
End While
End If
End Sub
Private Function Generate(ByVal Board(,,) As Char, _
ByVal Turn As Integer) As TreeNode
Dim CharTemp As Char
If Turn = 1 Then
CharTemp = "X"
Else
If Turn = -1 Then
CharTemp = "O"
End If
End If
Dim objSymmetric As New Symmetric
Dim objQueue As New Queue
objSymmetric.MakeQueue(Board, _
objQueue, CharTemp)
Dim Head As New TreeNode
Dim Node As New TreeNode
If objQueue.Count <> 0 Then
Node = objQueue.Dequeue
End If
Head = Node
While objQueue.Count <> 0
Node.NextNode = objQueue.Dequeue
Node = Node.NextNode
End While
Head.Turn = Turn
Return Head
End Function
Private Sub BestBranch(ByVal pnd As TreeNode, _
ByVal Player As Char, ByRef pBest As TreeNode, _
ByRef pvalue As Integer)
Dim Temp As Integer = Temp.MinValue
Dim Best As New TreeNode
Dim Son As New TreeNode
Son = pnd.Son
While Not (Son Is Nothing)
If Temp < MinMax(Son, Player) Then
Temp = MinMax(Son, Player)
pBest = Son
End If
Son = Son.NextNode
End While
End Sub
Private Function MinMax(ByVal Node As TreeNode, _
ByVal Player As Char) As Integer
If Node.Son Is Nothing Then
Dim objStatic As New StaticFunction
Return objStatic.StaticFunction(Node.Board, _
Player)
Else
Dim Temp As New TreeNode
Temp = Node.Son
If Node.Turn = 1 Then
Dim Max As Integer = Max.MinValue
While Not (Temp Is Nothing)
If Max < MinMax(Temp, Player) Then
Max = MinMax(Temp, Player)
End If
Temp = Temp.NextNode
End While
Return Max
Else
Dim Min As Integer = Min.MaxValue
While Not (Temp Is Nothing)
If Min > MinMax(Temp, Player) Then
Min = MinMax(Temp, Player)
End If
Temp = Temp.NextNode
End While
Return Min
End If
End If
End Function
End Class
Obviously always machine is winner.
[advertisement] Axosoft OnTime 2008 is four developer tools in one: bug tracking, project wiki, feature management, and help desk. It manages your development process so developers can focus on coding. Installed or Hosted – Free Single-user license -- Free 30-day team trial.
3 Comments : 07.29.06
Feedbacks
Hi there, I could not compile your VB program. It can not recognise Symmetric, Temp, StaticFunction and maybe few others. What am I missing?
Looking forward to hear from you
thx for u it is very nice
#1
Keyvan Nayyeri
08.14.2007 @ 10:02 AM