SHOW:
|
|
- or go back to the newest paste.
| 1 | Public Class Form1 | |
| 2 | ' Date made: 1 July 2012 | |
| 3 | ' The aim of this program is to determine which method is faster in determining whether a given tic-tac-toe board contains a | |
| 4 | ' win: representing the board as two boolean arrays, one for each player, and checking for wins by simply checking each of the | |
| 5 | ' rows/columns, or representing the board as two integers, one for each player, with each position on the board being a prime | |
| 6 | ' number, and checking for wins by testing for divisibility of the specified number. A number of boards will be generated, | |
| 7 | ' and both methods will test the same boards. | |
| 8 | ||
| 9 | ' Results: Prime method is far more efficient. | |
| 10 | ||
| 11 | Dim numberOfGenerations As Integer = 100000 | |
| 12 | Dim boardToPrime As New Dictionary(Of Integer, Integer) | |
| 13 | Dim currentZeroToEightList As New List(Of Integer) | |
| 14 | ' The boards to be generated, saved and tested. | |
| 15 | Dim playerOneArrays As New List(Of Array) | |
| 16 | Dim playerTwoArrays As New List(Of Array) | |
| 17 | Dim playerOneNumbers As New List(Of Integer) | |
| 18 | Dim playerTwoNumbers As New List(Of Integer) | |
| 19 | ||
| 20 | ||
| 21 | Private Sub Form1_Load(sender As System.Object, e As System.EventArgs) Handles MyBase.Load | |
| 22 | ||
| 23 | Randomize() | |
| 24 | ||
| 25 | ' Make the "board number to prime number" dictionary. | |
| 26 | boardToPrime(1) = 2 | |
| 27 | boardToPrime(2) = 3 | |
| 28 | boardToPrime(3) = 5 | |
| 29 | boardToPrime(4) = 7 | |
| 30 | boardToPrime(5) = 11 | |
| 31 | boardToPrime(6) = 13 | |
| 32 | boardToPrime(7) = 17 | |
| 33 | boardToPrime(8) = 19 | |
| 34 | boardToPrime(9) = 23 | |
| 35 | ||
| 36 | End Sub | |
| 37 | ||
| 38 | Private Sub btnGenerateBoards_Click(sender As System.Object, e As System.EventArgs) Handles btnGenerateBoards.Click | |
| 39 | ' Two different types of boards have to be generated, one type for each method. | |
| 40 | ||
| 41 | ' Reset the overall lists. | |
| 42 | playerOneArrays.Clear() | |
| 43 | playerTwoArrays.Clear() | |
| 44 | playerOneNumbers.Clear() | |
| 45 | playerTwoNumbers.Clear() | |
| 46 | For i = 1 To numberOfGenerations | |
| 47 | ' Declare arrays and player numbers. | |
| 48 | Dim playerOneArray(8) As Boolean | |
| 49 | Dim playerTwoArray(8) As Boolean | |
| 50 | Dim playerOneNumber As Integer = 1 | |
| 51 | Dim playerTwoNumber As Integer = 1 | |
| 52 | Dim numberOfCrosses, numberOfNoughts As Integer | |
| 53 | ' Reset boolean arrays. | |
| 54 | For j = 0 To 8 | |
| 55 | playerOneArray(j) = False | |
| 56 | playerTwoArray(j) = False | |
| 57 | Next | |
| 58 | ' Randomise the number of noughts and crosses (whichever is randomised first has a higher chance of being higher). | |
| 59 | If Rnd() > 0.5 Then | |
| 60 | numberOfCrosses = Math.Floor(Rnd() * 9) | |
| 61 | numberOfNoughts = Math.Floor(Rnd() * (9 - numberOfCrosses)) | |
| 62 | Else | |
| 63 | numberOfNoughts = Math.Floor(Rnd() * 9) | |
| 64 | numberOfCrosses = Math.Floor(Rnd() * (9 - numberOfNoughts)) | |
| 65 | End If | |
| 66 | ' Reset the currentZeroToEightList. | |
| 67 | currentZeroToEightList.Clear() | |
| 68 | For j = 0 To 8 | |
| 69 | currentZeroToEightList.Add(j) | |
| 70 | Next | |
| 71 | ' Randomly place the pieces in the boolean arrays, using a list to avoid picking the same number twice. | |
| 72 | For j = 1 To numberOfCrosses | |
| 73 | Dim randomNumber As Integer = currentZeroToEightList(Math.Floor(Rnd() * currentZeroToEightList.Count)) | |
| 74 | currentZeroToEightList.Remove(randomNumber) | |
| 75 | playerOneArray(randomNumber) = True | |
| 76 | Next j | |
| 77 | For j = 1 To numberOfNoughts | |
| 78 | Dim randomNumber As Integer = currentZeroToEightList(Math.Floor(Rnd() * currentZeroToEightList.Count)) | |
| 79 | currentZeroToEightList.Remove(randomNumber) | |
| 80 | playerTwoArray(randomNumber) = True | |
| 81 | Next j | |
| 82 | ' Transfer the pieces in the boolean arrays to the numbers. | |
| 83 | For j = 0 To 8 | |
| 84 | If playerOneArray(j) = True Then | |
| 85 | playerOneNumber *= boardToPrime(j + 1) | |
| 86 | End If | |
| 87 | If playerTwoArray(j) = True Then | |
| 88 | playerTwoNumber *= boardToPrime(j + 1) | |
| 89 | End If | |
| 90 | Next j | |
| 91 | ' Add these board representations to the overall lists. | |
| 92 | playerOneArrays.Add(playerOneArray) | |
| 93 | playerTwoArrays.Add(playerTwoArray) | |
| 94 | playerOneNumbers.Add(playerOneNumber) | |
| 95 | playerTwoNumbers.Add(playerTwoNumber) | |
| 96 | Next i | |
| 97 | MessageBox.Show("Done.")
| |
| 98 | End Sub | |
| 99 | ||
| 100 | Private Sub btnRunPrimeMethod_Click(sender As System.Object, e As System.EventArgs) Handles btnRunPrimeMethod.Click | |
| 101 | ' Test all the boards for wins using the prime method, and time the process. | |
| 102 | ||
| 103 | Dim numberOfPlayerOneWins As Integer = 0 | |
| 104 | Dim numberOfPlayerTwoWins As Integer = 0 | |
| 105 | Dim currentNumber As Integer | |
| 106 | ||
| 107 | Dim startTime As Date = Now | |
| 108 | ||
| 109 | For i = 0 To numberOfGenerations - 1 | |
| 110 | currentNumber = playerOneNumbers(i) | |
| 111 | ' Check for player one wins. | |
| 112 | ' Rows. | |
| 113 | If currentNumber Mod 30 = 0 Then | |
| 114 | numberOfPlayerOneWins += 1 | |
| 115 | Continue For | |
| 116 | End If | |
| 117 | If currentNumber Mod 1001 = 0 Then | |
| 118 | numberOfPlayerOneWins += 1 | |
| 119 | Continue For | |
| 120 | End If | |
| 121 | If currentNumber Mod 7429 = 0 Then | |
| 122 | numberOfPlayerOneWins += 1 | |
| 123 | Continue For | |
| 124 | End If | |
| 125 | ' Columns. | |
| 126 | If currentNumber Mod 238 = 0 Then | |
| 127 | numberOfPlayerOneWins += 1 | |
| 128 | Continue For | |
| 129 | End If | |
| 130 | If currentNumber Mod 627 = 0 Then | |
| 131 | numberOfPlayerOneWins += 1 | |
| 132 | Continue For | |
| 133 | End If | |
| 134 | If currentNumber Mod 1495 = 0 Then | |
| 135 | numberOfPlayerOneWins += 1 | |
| 136 | Continue For | |
| 137 | End If | |
| 138 | ' Diagonals. | |
| 139 | If currentNumber Mod 506 = 0 Then | |
| 140 | numberOfPlayerOneWins += 1 | |
| 141 | Continue For | |
| 142 | End If | |
| 143 | If currentNumber Mod 935 = 0 Then | |
| 144 | numberOfPlayerOneWins += 1 | |
| 145 | Continue For | |
| 146 | End If | |
| 147 | ||
| 148 | currentNumber = playerTwoNumbers(i) | |
| 149 | ' Check for player two wins. | |
| 150 | ||
| 151 | ' Rows. | |
| 152 | If currentNumber Mod 30 = 0 Then | |
| 153 | numberOfPlayerTwoWins += 1 | |
| 154 | Continue For | |
| 155 | End If | |
| 156 | If currentNumber Mod 1001 = 0 Then | |
| 157 | numberOfPlayerTwoWins += 1 | |
| 158 | Continue For | |
| 159 | End If | |
| 160 | If currentNumber Mod 7429 = 0 Then | |
| 161 | numberOfPlayerTwoWins += 1 | |
| 162 | Continue For | |
| 163 | End If | |
| 164 | ' Columns. | |
| 165 | If currentNumber Mod 238 = 0 Then | |
| 166 | numberOfPlayerTwoWins += 1 | |
| 167 | Continue For | |
| 168 | End If | |
| 169 | If currentNumber Mod 627 = 0 Then | |
| 170 | numberOfPlayerTwoWins += 1 | |
| 171 | Continue For | |
| 172 | End If | |
| 173 | If currentNumber Mod 1495 = 0 Then | |
| 174 | numberOfPlayerTwoWins += 1 | |
| 175 | Continue For | |
| 176 | End If | |
| 177 | ' Diagonals. | |
| 178 | If currentNumber Mod 506 = 0 Then | |
| 179 | numberOfPlayerTwoWins += 1 | |
| 180 | Continue For | |
| 181 | End If | |
| 182 | If currentNumber Mod 935 = 0 Then | |
| 183 | numberOfPlayerTwoWins += 1 | |
| 184 | Continue For | |
| 185 | End If | |
| 186 | Next i | |
| 187 | ||
| 188 | Dim runLength As TimeSpan = Now.Subtract(startTime) | |
| 189 | Dim milliseconds As Integer = runLength.TotalMilliseconds | |
| 190 | ||
| 191 | MessageBox.Show("Done." & vbNewLine & vbNewLine & "Player one wins: " & numberOfPlayerOneWins & vbNewLine & "Player two wins: " & numberOfPlayerTwoWins & vbNewLine & vbNewLine & "Time taken(ms): " & milliseconds)
| |
| 192 | End Sub | |
| 193 | Private Sub btnRunBooleanMethod_Click(sender As System.Object, e As System.EventArgs) Handles btnRunBooleanMethod.Click | |
| 194 | ' Test all the boards for wins using the boolean method, and time the process. | |
| 195 | ||
| 196 | Dim numberOfPlayerOneWins As Integer = 0 | |
| 197 | Dim numberOfPlayerTwoWins As Integer = 0 | |
| 198 | Dim currentArray As Array | |
| 199 | ||
| 200 | Dim startTime As Date = Now | |
| 201 | ||
| 202 | For i = 0 To numberOfGenerations - 1 | |
| 203 | currentArray = playerOneArrays(i) | |
| 204 | ' Check for player one wins. | |
| 205 | ' Rows. | |
| 206 | If currentArray(0) And currentArray(1) And currentArray(2) Then | |
| 207 | numberOfPlayerOneWins += 1 | |
| 208 | Continue For | |
| 209 | End If | |
| 210 | If currentArray(3) And currentArray(4) And currentArray(5) Then | |
| 211 | numberOfPlayerOneWins += 1 | |
| 212 | Continue For | |
| 213 | End If | |
| 214 | If currentArray(6) And currentArray(7) And currentArray(8) Then | |
| 215 | numberOfPlayerOneWins += 1 | |
| 216 | Continue For | |
| 217 | End If | |
| 218 | ' Columns. | |
| 219 | If currentArray(0) And currentArray(3) And currentArray(6) Then | |
| 220 | numberOfPlayerOneWins += 1 | |
| 221 | Continue For | |
| 222 | End If | |
| 223 | If currentArray(1) And currentArray(4) And currentArray(7) Then | |
| 224 | numberOfPlayerOneWins += 1 | |
| 225 | Continue For | |
| 226 | End If | |
| 227 | If currentArray(2) And currentArray(5) And currentArray(8) Then | |
| 228 | numberOfPlayerOneWins += 1 | |
| 229 | Continue For | |
| 230 | End If | |
| 231 | ' Diagonals. | |
| 232 | If currentArray(0) And currentArray(4) And currentArray(8) Then | |
| 233 | numberOfPlayerOneWins += 1 | |
| 234 | Continue For | |
| 235 | End If | |
| 236 | If currentArray(2) And currentArray(4) And currentArray(6) Then | |
| 237 | numberOfPlayerOneWins += 1 | |
| 238 | Continue For | |
| 239 | End If | |
| 240 | ||
| 241 | currentArray = playerTwoArrays(i) | |
| 242 | ' Check for player two wins. | |
| 243 | ' Rows. | |
| 244 | If currentArray(0) And currentArray(1) And currentArray(2) Then | |
| 245 | numberOfPlayerTwoWins += 1 | |
| 246 | Continue For | |
| 247 | End If | |
| 248 | If currentArray(3) And currentArray(4) And currentArray(5) Then | |
| 249 | numberOfPlayerTwoWins += 1 | |
| 250 | Continue For | |
| 251 | End If | |
| 252 | If currentArray(6) And currentArray(7) And currentArray(8) Then | |
| 253 | numberOfPlayerTwoWins += 1 | |
| 254 | Continue For | |
| 255 | End If | |
| 256 | ' Columns. | |
| 257 | If currentArray(0) And currentArray(3) And currentArray(6) Then | |
| 258 | numberOfPlayerTwoWins += 1 | |
| 259 | Continue For | |
| 260 | End If | |
| 261 | If currentArray(1) And currentArray(4) And currentArray(7) Then | |
| 262 | numberOfPlayerTwoWins += 1 | |
| 263 | Continue For | |
| 264 | End If | |
| 265 | If currentArray(2) And currentArray(5) And currentArray(8) Then | |
| 266 | numberOfPlayerTwoWins += 1 | |
| 267 | Continue For | |
| 268 | End If | |
| 269 | ' Diagonals. | |
| 270 | If currentArray(0) And currentArray(4) And currentArray(8) Then | |
| 271 | numberOfPlayerTwoWins += 1 | |
| 272 | Continue For | |
| 273 | End If | |
| 274 | If currentArray(2) And currentArray(4) And currentArray(6) Then | |
| 275 | numberOfPlayerTwoWins += 1 | |
| 276 | Continue For | |
| 277 | End If | |
| 278 | Next i | |
| 279 | ||
| 280 | Dim runLength As TimeSpan = Now.Subtract(startTime) | |
| 281 | Dim milliseconds As Integer = runLength.TotalMilliseconds | |
| 282 | ||
| 283 | MessageBox.Show("Done." & vbNewLine & vbNewLine & "Player one wins: " & numberOfPlayerOneWins & vbNewLine & "Player two wins: " & numberOfPlayerTwoWins & vbNewLine & vbNewLine & "Time taken(ms): " & milliseconds)
| |
| 284 | End Sub | |
| 285 | ||
| 286 | End Class |