Need help with learning AI

Blitz3D Forums/Blitz3D Beginners Area/Need help with learning AI

Sonic65
 #1
Success! I decided to research the topic a bit more, and found a Perl program which did exactly what I wanted to do here. After looking over that program and replicating it Blitz3D, as well as making it about 100x faster (in terms of how fast it learns, not program speed), it reaches the goal of 90% in only ~2000 games! The process it uses is very similar to the process I described above, except it stores the board in a string, and uses a different feedback function.

Here's the code (again, doesn't require any external files):

Graphics 640,480,0,2
SetBuffer BackBuffer()
SeedRnd MilliSecs()


; Each state is in a type, with two fields; the board it represents and its value
Type state
	Field boardID$
	Field stateV#
End Type

; These variables are used when a function needs to return a string or decimal.
Global rBString$
Global rBVal#

Global currentBoard[8]			; Stores the current board.


Global winNum#					; Number of games won
Global numOfEpisodes = 50000	; Total number of training games to play
Global currentEpisode# = 0		; Current training game
Global winRate#					; Win rate (%)

Global terminalState = False
Global humanMode = False		; set this to true to enable player control. if not set, the
								; program goes into training mode (against a random opponent).



loadSavedStates()

While currentEpisode < numOfEpisodes
	
	clearBoard()
	terminalState = False
	
	Cls
	
	While terminalState = False
	
		; AI's turn
		convertToString(currentBoard)
		curStr$ = rBString$
		
		selectAction()
		
		convertToString(currentBoard)
		newStr$ = rBString$
		
		; Update the state values after the player's turn.
		updateV(curStr$,newStr$)
		
		; Check if anybody has won, or if the game is a draw.
		isWinnerL = checkWin(newStr)
		If isWinnerL <> 0 Then
			terminalState = True
			Exit
		EndIf
		
		
		; Opponent turn	
		convertToString(currentBoard)
		curStr$ = rBString$		
		
		If humanMode = False
			randomMove(2)
		Else
			humanPlayer()
			FlushKeys()
		EndIf
		
		convertToString(currentBoard)
		newStr$ = rBString$
		
		; Update the state values after the opponent's turn.
		updateV(curStr$,newStr$)	
		
		; Check if anybody has won, or if the game is a draw.
		isWinnerL = checkWin(newStr)
		If isWinnerL <> 0 Then
			terminalState = True
			Exit
		EndIf	
		
	Wend
	
	Cls
	
	currentEpisode = currentEpisode + 1	
	
	If isWinnerL = 1 Then winNum = winNum + 1
	
	displayBoard()
	winRate# = (winNum#/currentEpisode#) * 100

	Text 20,20,currentEpisode
	Text 80,20,winNum
	Text 140,20,winRate
	Flip 0	
	
Wend

Cls

Print winNum
Flip 0
Delay 500

; Save the AI states and corresponding values to a file.
saveFile()



; Displays the board.

Function displayBoard()
	x2%=0
	y2%=0
	
	For y = 0 To 2
		For x = 0 To 2
			pos = (y*3) + x
			
			number% = currentBoard[pos]
			
			Select number
				Case 1
					lStr$ = "X"
				Case 2
					lStr$ = "O"
				Default
					lStr$ = " "		
			End Select
				
			Text 270+(x*40),190+(y*40),lStr$
			If x<2 Then Text 290+(x*40),190+(y*40),"|"
			If y<2 Then Text 270,210+(y*40),"-----------"
		Next
	Next
End Function


; Clears the board.

Function clearBoard()
	For x = 0 To 8
		currentBoard[x] = 0
	Next
End Function


; Converts a board array to a string.
Function convertToString(board[8])
	returnStr$ = ""
	
	returnStr$ = returnStr$ + board[0]
	returnStr$ = returnStr$ + board[1]
	returnStr$ = returnStr$ + board[2]
	returnStr$ = returnStr$ + board[3]
	returnStr$ = returnStr$ + board[4]
	returnStr$ = returnStr$ + board[5]
	returnStr$ = returnStr$ + board[6]
	returnStr$ = returnStr$ + board[7]
	returnStr$ = returnStr$ + board[8]
	
	rbString$ = returnStr$
End Function


; Function which selects the move for the learning AI.

Function selectAction()
	Local evalBoard[8]
	Local maxV# = -2
	Local maxCell = 0
	
	; Copies the current board array to the local evaluation board array.
	
	For x = 0 To 8
		evalBoard[x] = currentBoard[x]
	Next
	
	For x = 0 To 8
		If evalBoard[x] = 0 Then
			
			; Evaluate all blank spaces, and find the highest-ranked one.
			
			evalBoard[x] = 1
			
			convertToString(evalBoard)
			selS$ = rBString$
			
			evalBoard[x] = 0
			
			If stateExists(selS$) Then
				; If a state exists that matches the board, then get its value.
				
				getStateValue(selS$)
				val# = rbVal#
			Else
				; If there isn't any state that matches with the board, then create a new one
				; with a value of 0.5.
				
				createNewState(selS$,0.5)
				val# = 0.5
			EndIf
			
			If val > maxV
				maxV = val
				maxCell = x
			EndIf
			
		EndIf
	Next
	
	; Mark the spot selected.
	currentBoard[maxCell] = 1
End Function


; Check the board string attached, to see if there is a winner.

Function checkWin(bStr$)
	Local tempB[8]
	
	For x = 0 To 8
		tempB[x] = Int(Mid$(bStr,x+1,1))
	Next	
	
	For winner = 1 To 2
	
		; Horizontal/vertical checks
		For x = 0 To 2
			If tempB[x] = winner And tempB[x+3] = winner And tempB[x+6] = winner Then Return winVal(winner)
			If tempB[x*3] = winner And tempB[(x*3)+1] = winner And tempB[(x*3)+2] = winner Then Return winVal(winner)
		Next
		
		; Diagonal checks
		If tempB[0] = winner And tempB[4] = winner And tempB[8] = winner Then Return winVal(winner)
		If tempB[2] = winner And tempB[4] = winner And tempB[6] = winner Then Return winVal(winner)
	Next
	
	; Check if there are any empty spaces left; if not, return a draw.
	emptyCount = 0
	
	For x = 0 To 8
		If tempB[x] = 0 Then emptyCount = emptyCount + 1
	Next
	
	If emptyCount = 0 Then Return 3 Else Return 0
		
End Function


; Win values; 1 for the player, -1 for the opponent
Function winVal(winner)
	If winner = 1 Then Return 1
	If winner = 2 Then Return -1
End Function



;----------------------------------------------------
; STATE FUNCTIONS
;----------------------------------------------------

; Check to see if a state exists for the board string given.

Function stateExists(selS$)
	For a.state = Each state
		If a\boardID$ = selS$ Then Return True
	Next
	
	Return False
End Function


; Get the value for the state given.

Function getStateValue(selS$)
	For a.state = Each state
		If a\boardID$ = selS$ Then 
			rbVal# = a\stateV#
			Return True
		EndIf
	Next
	
	rbVal# = 0
End Function


; Update the value of the state given, with the value given.

Function updateStateValue(selS$,value#)
	For a.state = Each state
		If a\boardID$ = selS$ Then 
			a\stateV# = value#
			Return True
		EndIf
	Next
	
	Return False
End Function


; Create a new state with the board given, containing the value given.
Function createNewState(selS$,value#)
	a.state = New state
	a\boardID$ = selS$
	a\stateV# = value#
	Return True
End Function


; State value updating function; the heart of the AI system.

Function updateV(curStr$,newStr$)
	Local alpha# 
	
	Local cVal# = 0
	Local nVal# = 0
	
	alpha# = 0.08 * (0.95 - (0.9 * (currentEpisode/numOfEpisodes)))	; Alpha value; increases as the
																	; number of games increases.
																	; Influences learning rate.
	
	If stateExists(curStr$) Then
		getStateValue(curStr$)		; If a state exists for the old board, get its value.
	Else
		lookupV(curStr$)			; If not, look up the value to see if it is a winning board.
	EndIf
	
	cVal = rbVal
		
	
	If stateExists(newStr$) Then
		getStateValue(newStr$)		; If a state exists for the new board, get its value.
	Else
		lookupV(newStr$)			; If not, look up the value to see if it is a winning board.
	EndIf
	
	nVal = rbVal
	
	newVal# = cVal + (alpha * (nVal - cVal))	; Updates the state value, based on the values of the
	updateStateValue(curStr, newVal)			; previous and new states.
End Function


; Value lookup function; checks if the state given is a winning state, a losing state, a draw state,
; or none, and return a corresponding value.

Function lookupV(state$)
	isWinnerV = checkWin(state$)
	
	If isWinnerV = 3 Then
		createNewState(state$,0)
		rbVal = 0
		Return
	ElseIf isWinnerV = 1 Then
		createNewState(state$,1)
		rbVal = 1
		Return
	ElseIf isWinnerV = -1
		createNewState(state$,-1)
		rbVal = -1
		Return -1
	EndIf
	
	createNewState(state$,0.5)
	rbVal = 0.5
	Return
End Function


; Random move functions, used for training.

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


; Saves all the states and their values to a file.

Function saveFile()
	fileOut=WriteFile("trainData.txt")
	
	For a.state = Each state
		WriteLine fileOut, a\boardID
		WriteLine fileOut, Str$(a\stateV#)
		WriteLine fileOut, " "
	Next
End Function


; Loads saved states and their values from a file.

Function loadSavedStates()
	If FileType("trainData.txt")
		fileIn = ReadFile("trainData.txt")
		
		While Not Eof(fileIn)
			a.state = New state
			a\boardID$ = ReadLine(fileIn)
			a\stateV# = ReadLine(fileIn)
			ReadLine(fileIn)
		Wend
	EndIf	
End Function


; Player control function.

Function humanPlayer()
	Local hMoved = False
	
	While hMoved = False
		displayBoard()
		Flip
		WaitKey()
		
		If KeyHit(2) Then
			If currentBoard[0] = 0 Then currentBoard[0] = 2: Return
		ElseIf KeyHit(3)
			If currentBoard[1] = 0 Then currentBoard[1] = 2: Return
		ElseIf KeyHit(4)
			If currentBoard[2] = 0 Then currentBoard[2] = 2: Return
		ElseIf KeyHit(16)
			If currentBoard[3] = 0 Then currentBoard[3] = 2: Return
		ElseIf KeyHit(17)
			If currentBoard[4] = 0 Then currentBoard[4] = 2: Return
		ElseIf KeyHit(18)
			If currentBoard[5] = 0 Then currentBoard[5] = 2: Return
		ElseIf KeyHit(30)
			If currentBoard[6] = 0 Then currentBoard[6] = 2: Return
		ElseIf KeyHit(31)
			If currentBoard[7] = 0 Then currentBoard[7] = 2: Return
		ElseIf KeyHit(32)
			If currentBoard[8] = 0 Then currentBoard[8] = 2: Return
		EndIf
		
	Wend
End Function


If you want to play against it without having to train it first against the random opponent, then download the file below and put it in the same folder as the code (without changing the name or the file), and set the human flag to True.

http://www.fileden.com/files/2006/8/1/150488/trainData.txt