Want more features on Pastebin? Sign Up, it's FREE!
Guest

Minmax algorithm problem

By: a guest on Feb 4th, 2012  |  syntax: VB.NET  |  size: 9.10 KB  |  views: 141  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. 'Test application to tes the minmax algorithm, as well as alpha-beta pruning inside of it. A tic-tac--toe program that will never lose. By Keegan Parker
  2. Public Class Form1
  3.     Public Const PLAYER_PIECE As String = "X"
  4.     Public Const COMPUTER_PIECE As String = "O"
  5.     Public Const HUMAN_WIN As Integer = -1
  6.     Public Const COMPUTER_WIN As Integer = 1
  7.     Public Const TIE As Integer = 0
  8.     Public Const COMPUTER As Boolean = True
  9.     Public Const HUMAN As Boolean = False
  10.     Public Game_Ended As Boolean = False
  11.     Public Turn As String = "Human"
  12.     Public Board(2, 2) As Board
  13.     'Sets all objects up (mostly labels, and the board)
  14.     Private Sub On_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
  15.         Dim intindex As Integer
  16.         Dim intindex2 As Integer
  17.         For intindex = 0 To 2
  18.             For intindex2 = 0 To 2
  19.                 Dim Label As New Label
  20.                 Label.Name = "lbl" & intindex & intindex2
  21.                 Label.AutoSize = False
  22.                 Label.TextAlign = ContentAlignment.MiddleCenter
  23.                 Label.Font = New Font("Arial", 48, FontStyle.Bold)
  24.                 Label.Size = New System.Drawing.Size(100, 100)
  25.                 Label.Location = New System.Drawing.Point(intindex * 100, intindex2 * 100)
  26.                 Label.BorderStyle = Windows.Forms.BorderStyle.FixedSingle
  27.                 Board(intindex, intindex2).lbl = Label
  28.                 Board(intindex, intindex2).posX = intindex
  29.                 Board(intindex, intindex2).posY = intindex2
  30.                 Me.Controls.Add(Label)
  31.                 AddHandler Board(intindex, intindex2).lbl.Click, AddressOf Player_Move
  32.             Next
  33.         Next
  34.     End Sub
  35.     'If a player clicks on one of the labels, it will attmpt to put a player piece on that tile, and direct the game to the computer's turn.
  36.     Sub Player_Move(ByVal sender As System.Object, ByVal e As System.EventArgs)
  37.         Dim Current_Board As Board = GetBoard(sender)
  38.         Dim Best As Best
  39.         If Current_Board.owner = Nothing Then
  40.             Board(Current_Board.posX, Current_Board.posY).owner = PLAYER_PIECE
  41.             Board(Current_Board.posX, Current_Board.posY).lbl.Text = PLAYER_PIECE
  42.             Call Check_Board(Board, False)
  43.             If Game_Ended = False Then
  44.                 Turn = "Computer"
  45.                 Best = Get_Computer_Move(COMPUTER, Board)
  46.                 Board(Best.MovePosX, Best.MovePosY).owner = COMPUTER_PIECE
  47.                 Board(Best.MovePosX, Best.MovePosY).lbl.Text = COMPUTER_PIECE
  48.                 Call Check_Board(Board, False)
  49.             End If
  50.             Game_Ended = False
  51.             Turn = "Human"
  52.         End If
  53.     End Sub
  54.  
  55.     'Checks win/tie conditions. If it is a simulation (for ai), then it will return a number. If it is for legitimate checking, it will call the win function, or tie.
  56.     Function Check_Board(ByVal opBoard(,) As Board, ByVal simulation As Boolean)
  57.         Dim intindex As Integer
  58.         Dim intindex2 As Integer
  59.         'Vertical Check
  60.         For intindex = 0 To 2
  61.             If opBoard(intindex, 0).owner = opBoard(intindex, 1).owner And opBoard(intindex, 1).owner = opBoard(intindex, 2).owner And opBoard(intindex, 0).owner <> Nothing Then
  62.                 If simulation = False Then
  63.                     Win()
  64.                 Else
  65.                     Return 1
  66.                 End If
  67.             End If
  68.         Next
  69.         'Horizantal Check
  70.         For intindex = 0 To 2
  71.             If opBoard(0, intindex).owner = opBoard(1, intindex).owner And opBoard(1, intindex).owner = opBoard(2, intindex).owner And opBoard(0, intindex).owner <> Nothing Then
  72.                 If simulation = False Then
  73.                     Win()
  74.                 Else
  75.                     Return 1
  76.                 End If
  77.             End If
  78.         Next
  79.         'Diagonal Check
  80.         Dim intoppindex As Integer
  81.         Dim intoppindex2 As Integer
  82.         For intindex = 0 To 2 Step 2
  83.             For intindex2 = 0 To 2 Step 2
  84.                 If intindex = 0 Then
  85.                     intoppindex = 2
  86.                 Else
  87.                     intoppindex = 0
  88.                 End If
  89.                 If intindex2 = 0 Then
  90.                     intoppindex2 = 2
  91.                 Else
  92.                     intoppindex2 = 0
  93.                 End If
  94.                 If opBoard(intindex, intindex2).owner = opBoard(1, 1).owner And opBoard(1, 1).owner = opBoard(intoppindex, intoppindex2).owner And opBoard(intindex, intindex2).owner <> Nothing Then
  95.                     If simulation = False Then
  96.                         Win()
  97.                     Else
  98.                         Return 1
  99.                     End If
  100.                 End If
  101.             Next
  102.         Next
  103.         'Full Board
  104.         Dim movedcount As Integer
  105.         For intindex = 0 To 2
  106.             For intindex2 = 0 To 2
  107.                 If opBoard(intindex, intindex2).owner <> Nothing Then
  108.                     movedcount += 1
  109.                 End If
  110.             Next
  111.         Next
  112.         If movedcount = 9 Then
  113.             If simulation = False Then
  114.                 MessageBox.Show("It is a tie. Resetting the board.")
  115.                 For intindex = 0 To 2
  116.                     For intindex2 = 0 To 2
  117.                         Board(intindex, intindex2).owner = Nothing
  118.                         Board(intindex, intindex2).lbl.Text = Nothing
  119.                     Next
  120.                 Next
  121.                 Game_Ended = True
  122.             Else
  123.                 Return 0
  124.             End If
  125.         End If
  126.         Return Nothing
  127.     End Function
  128.  
  129.     'Allows labels to be processed in to the board
  130.     Public Function GetBoard(ByVal sender As Label)
  131.         Dim intindex As Integer
  132.         Dim intindex2 As Integer
  133.         For intindex = 0 To 2
  134.             For intindex2 = 0 To 2
  135.                 If Board(intindex, intindex2).lbl.Name = sender.Name Then
  136.                     Return Board(intindex, intindex2)
  137.                 End If
  138.             Next
  139.         Next
  140.         Return Nothing
  141.     End Function
  142.     'If a player wins, it will display a message box and reset the board
  143.     Sub Win()
  144.         MessageBox.Show(Turn & " has won. Resetting the board.")
  145.         Dim intindex As Integer
  146.         Dim intindex2 As Integer
  147.         For intindex = 0 To 2
  148.             For intindex2 = 0 To 2
  149.                 Board(intindex, intindex2).owner = Nothing
  150.                 Board(intindex, intindex2).lbl.Text = Nothing
  151.             Next
  152.         Next
  153.         Game_Ended = True
  154.     End Sub
  155.  
  156.     'Minmax algorithm that tries to get best possible move by accessing every possible scenario in the game tree. NOT WORKING. Returns a "best" object, that is then used to place the computer's piece.
  157.     Public Function Get_Computer_Move(ByVal side As Boolean, ByVal opBoard(,) As Board)
  158.         Dim mybest As New Best
  159.         Dim reply As Best
  160.         Dim LegalMoves As New List(Of LegalMove)
  161.  
  162.         LegalMoves = Get_Legal_Moves(opBoard)
  163.  
  164.         Dim oppside As Boolean
  165.         If side = COMPUTER Then
  166.             oppside = HUMAN
  167.         Else
  168.             oppside = COMPUTER
  169.         End If
  170.  
  171.         If Check_Board(opBoard, True) <> Nothing Then
  172.             mybest.Score = Check_Board(opBoard, True)
  173.             Return mybest
  174.         End If
  175.  
  176.         If side = COMPUTER Then
  177.             mybest.Score = -2
  178.         Else
  179.             mybest.Score = 2
  180.         End If
  181.  
  182.         For Each LegalMove In LegalMoves
  183.             If side = COMPUTER Then
  184.                 opBoard(LegalMove.posX, LegalMove.posY).owner = COMPUTER_PIECE
  185.             Else
  186.                 opBoard(LegalMove.posX, LegalMove.posY).owner = PLAYER_PIECE
  187.             End If
  188.             reply = Get_Computer_Move(oppside, opBoard)
  189.             opBoard(LegalMove.posX, LegalMove.posY).owner = Nothing
  190.             If (side = COMPUTER And reply.Score > mybest.Score) Or (side = HUMAN And reply.Score < mybest.Score) Then
  191.                 mybest.MovePosX = LegalMove.posX
  192.                 mybest.MovePosY = LegalMove.posY
  193.                 mybest.Score = reply.Score
  194.             End If
  195.         Next
  196.         Return mybest
  197.     End Function
  198.     'Returns potential legal moves on the board
  199.     Public Function Get_Legal_Moves(ByVal opboard(,) As Board)
  200.         Dim intindex As Integer
  201.         Dim intindex2 As Integer
  202.         Dim legalmoves As New List(Of LegalMove)
  203.         For intindex = 0 To 2
  204.             For intindex2 = 0 To 2
  205.                 If opboard(intindex, intindex2).owner = Nothing Then
  206.                     Dim legalmove As New LegalMove
  207.                     legalmove.posX = intindex
  208.                     legalmove.posY = intindex2
  209.                     legalmoves.Add(legalmove)
  210.                 End If
  211.             Next
  212.         Next
  213.         Return legalmoves
  214.     End Function
  215. End Class
  216.  
  217. Public Structure Board
  218.     Public lbl As Label
  219.     Public owner As String
  220.     Public posX As Integer
  221.     Public posY As Integer
  222. End Structure
  223.  
  224. Public Structure LegalMove
  225.     Public posX As Integer
  226.     Public posY As Integer
  227. End Structure
  228.  
  229. Public Structure Best
  230.     Public MovePosX As Integer
  231.     Public MovePosY As Integer
  232.     Public Score As Integer
  233. End Structure
clone this paste RAW Paste Data