Okay, so for my science fair project, I'm programming a Tic-Tac-Toe AI opponent which starts out with no knowledge of the game, and learns as it goes along. I tried to implement a simple reinforcement learning system, but it doesn't give good enough results; it only wins 86% of its total games at most (at the beginning of the program, at around 100 games) against a random opponent, and then drops to 77-80% and stays there. I want the learning AI to win over 90% of the time, at least.
Here's the code I'm using (doesn't require any external files):
If anyone could please help me figure out what I'm doing wrong here, it would be greatly appreciated.
Here's the code I'm using (doesn't require any external files):
Open in online IDEGraphics 640,480,0,2 SetBuffer BackBuffer() AppTitle "Tic-Tac-Toe w/ Learning AI" ; Each state is defined in a type. Type state Field stateID Field boardVals[8] Field cellWeights#[8] Field lossNum End Type ; Variables and arrays Dim currentBoard(8) ; current board Global stateMap[8] ; state map for current game Global moveMap[8] ; move map for current game Global currentMoveVals#[8] ; move values for the last game (only used for debug display) Global moveNum = 0 ; move # Global highState = 0 ; the state ID of the last state created Global winNum# = 0 ; # of games won Global totalGames# = 0 ; total games played ; Main loop While Not KeyHit(1) Cls If Not checkWin() > 0.5 Then ; AI's turn learningAI() updateStateMap() If Not checkWin() > 0.5 Then ; Random opponent's turn randomMove(2) updateStateMap() checkWin() EndIf EndIf displayBoard() ;Check if the game has reached an outcome; if so, give AI feedback and restart. If checkWin() > 0.5 Then feedbackValues() If checkWin() = 1 Then winNum = winNum + 1 If checkWin() = 2 Then lossNum = lossNum + 1 totalGames = totalGames + 1 ;debugDisplay() ; Uncomment this line to enable the debug display at the end of each game. clearBoard() For x = 0 To 8 stateMap[x] = 0 moveMap[x] = 0 currentMoveVals[x] = 0 Next moveNum = 0 EndIf ; Display # of games won, total games, % of games won Text 40,20,"GAMES WON: " + winNum# Text 40,35,"TOTAL GAMES: " + totalGames If totalGames>0 Then Text 40,75,"% OF GAMES WON: " + (winNum# / totalGames#) * 100 Flip 0 Wend Function learningAI() stateMatched = False ; The following for loop checks each state to see if it matches the current board. If it does, ; it checks to see which cell has the most weight. For a.state = Each state For x = 0 To 8 If currentBoard(x) = a\boardVals[x] Then matchNum = matchNum+1 Next If matchNum = 8 Then maxWeight = 0 maxCell = 0 ; Find highest weight, and the corresponding cell for that weight. For x = 0 To 8 weight = a\cellWeights[x] If weight > maxWeight Then weight = maxWeight maxCell = x EndIf Next cellNum = maxCell Exit EndIf Next ; Marks the highest-rated cell if the state has been matched in the state table. If it hasn't, ; either move in the first unmarked spot or move randomly. If stateMatched = True Then currentBoard(cellNum) = 1 moveMap[moveNum] = cellNum Else ; Sometimes exploratory steps are taken, to increase the number of possible states the AI sees. If Rnd(0,1)>0.05 Then moveMap[moveNum] = firstMove(1) Else moveMap[moveNum] = randomMove(1) EndIf End Function ; Makes a random move. Takes the player # as a parameter (this function is used by both opponents). Function randomMove(oppNum) count = 0 Repeat count = count + 1 ff = Rand(0,8) Until currentBoard(ff) = 0 Or count > 100 If count < 100 Then currentBoard(ff) = oppNum Return ff End Function ; Puts a piece in the first available spot. Function firstMove(oppNum) For ff = 0 To 8 If currentBoard(ff) = 0 Then Exit EndIf Next If currentBoard(ff) = 0 Then currentBoard(ff) = oppNum Else ff = 0 EndIf Return ff End Function ; Checks to see if the game has reached an outcome. Function checkWin() For oppNum = 1 To 2 ; Horizontal/vertical check For x = 0 To 2 If currentBoard(x) = oppNum And currentBoard(x+3) = oppNum And currentBoard(x+6) = oppNum Then Return oppNum EndIf If currentBoard(x*3) = oppNum And currentBoard((x*3)+1) = oppNum And currentBoard((x*3)+2) = oppNum Then Return oppNum EndIf Next ; Diagonal checks If currentBoard(0) = oppNum And currentBoard(4) = oppNum And currentBoard(8) = oppNum Then Return oppNum EndIf If currentBoard(2) = oppNum And currentBoard(4) = oppNum And currentBoard(6) = oppNum Then Return oppNum EndIf Next blankNum% = 0 ; Check to see how many blank spaces there are. For x = 0 To 8 If currentBoard(x) = 0 Then blankNum = blankNum + 1 Next ; If all spaces are taken up, then game is a draw, so return 3; if not, go on and return 0.5. If blankNum = 0 Then Return 3 Return 0.5 End Function ; Displays the board. Function displayBoard() x2%=0 y2%=0 For x = 0 To 8 number% = currentBoard(x) Select number Case 1 lStr$ = "X" Case 2 lStr$ = "O" Default lStr$ = " " End Select Text 270+(x2*40),190+(y2*40),lStr$ If x2<2 Then Text 290+(x2*40),190+(y2*40),"|" If y2<2 Then Text 270,210+(y2*40),"-----------" x2=x2+1 If x2=3 Then y2=y2+1 x2=0 EndIf Next End Function ; Clears the current board. Function clearBoard() For x = 0 To 8 currentBoard(x) = 0 Next End Function ; Updates the state map, identifying which states the current game has gone through, and also ; adding new states when they are encountered. Function updateStateMap() moveNum = moveNum + 1 stateMatched = False stateNum = 0 ; Search each state for a match to the current board. If there is a match, then update ; the state map and return. For a.state = Each state For x = 0 To 8 If currentBoard(x) = a\boardVals[x] Then matchNum = matchNum+1 If matchNum = 9 Then stateNum = a\stateID stateMap[moveNum] = stateNum Return EndIf Next Next ; If there is not a match, then initialize a new state, update the state map with this state, ; and return. a.state = New state highState = highState + 1 For x = 0 To 8 a\boardVals[x] = currentBoard(x) a\cellWeights[x] = 0 a\stateID = highState Next stateMap[moveNum] = highState End Function ; Feedback function for end of game; adjusts the cell weights for all the states used in the ; previous game using the outcome of the game. Function feedbackValues() For a.state = Each state For x = 0 To 8 If a\stateID = stateMap[x] And a\stateID > 0 Then If checkWin() = 1 Then ; Win feedback [+3] a\cellWeights[moveMap[x]] = a\cellWeights[moveMap[x]]+3 Else ; Lose/draw feedback [-5] a\cellWeights[moveMap[x]] = a\cellWeights[moveMap[x]]-5 EndIf currentMoveVals[x] = a\cellWeights[moveMap[x]] EndIf Next Next End Function ; Debug Function debugDisplay() For x = 0 To 8 Text 300,10*x,stateMap[x] Text 400,10*x,moveMap[x] Text 500,10*x,currentMoveVals[x] Text 400,100,highState Next Flip Delay 500 End Function
If anyone could please help me figure out what I'm doing wrong here, it would be greatly appreciated.