Dark Bit Factory & Gravity

PROGRAMMING => Other languages => Blitz => Topic started by: ablade on June 22, 2007

Title: Tic Tac Toe (Help)[BB2D]
Post by: ablade on June 22, 2007

Topic: (Tic Tac Toe Help)

Hi,

I need help with creating a computer opponent that will make a winning move when there is a chance to win. I already have a method to do this, but the computer takes all the empty slots.
I just want someone to tell me how to limit the computer move to 1, then check if the move is a win; if its not, check the next empty slot.


Note: The computer moves with the left mouse click. You have to click on an unoccupied slot to allow the computer to make the move.

You can download the source + necessary files in the following link.

Code: [Select]

http://askavenger.250free.com/downloads/GameProgramming/tictac.rar

Title: Re: Tic Tac Toe (Help)
Post by: mike_g on June 22, 2007

A way to go about it could be to play a piece on each free square. Then check all rows, columns, and diagonals for a win. If no win then remove the piece and move on to the next free square. This is quite inefficient, but it would be the simplest to code. Heres sort of an example of what I mean:

Code: [Select]

Function CheckForWin()
;Check rows for win
For y = 0 To 2
For x = 0 To 2
        If slot[x][y] = OWN_PIECE Then count=count+1
Next
Next

If count = 3 Then Return True
count=0

;Check columns for win
For x = 0 To 2
For y = 0 To 2
        If slot[x][y] = OWN_PIECE Then count=count+1
Next
Next

If count = 3 Return True
count=0
 
;Check Diagonals for win
For x = 0 To 2
    If slot[x][x] = OWN_PIECE Then count=count+1
Next

If count = 3 Return True
count=0

If slot[0][2] = OWN_PIECE Then count=count+1
If slot[1][1] = OWN_PIECE Then count=count+1
If slot[2][0] = OWN_PIECE Then count=count+1

If count = 3 Return True
EndIfHope that helps :)

Title: Re: Tic Tac Toe (Help)
Post by: Tetra on June 25, 2007

Hello ablade,

Welcome to the board :)

Having looked at your code I can see that the biggest problem you have is the ComputerMove() function. Your looping through each square and cheking if its empty then filling in the square with an X. What it should do is find a free square then fill it in with an X then stop, rather that continue through all the squares. However, that method does not attempt to win in any way.

Before I start with a possible solution I'd like to change a few thing about you program if thats ok. Not to say what you have done is wrong, but Blitz has some functionality that will make the code a little simpler to write. I have no idea of your experience with programming in Blitz, but I will write it for someone who is resonable new to Blitz, so that its more useful to more people.

Firstly and mostly is the images you are using. Blitz has a great function called LoadAnimImage() This function allows you to load a single image and split it up into sections. What this means is that you could combine all your images into one long image and save your self the effort of loading each image sepperately. What i've done is create an image of width 500 (125*4) and height 125. Each tile you have created will be lined up side by side in this image. I'll also save it in png format wich will reduce the image file size, especially with this type of image where there are long lengths of the same color, i.e the black. This is however more usefull on larger images of this nature.
I will then use LoadAnimImage("Tiles.png", 125,125, 0,4 ) to load it into memory and seperate the individual frames in the image. I can then access each frame using the normal DrawImage() command with the optional frame variable set. In this case there will be 4 frames 0 -> 3.

An alternative to loading images is to create one using Blitz graphics commands. You get stuff like Line and then Rect and Oval that can be outlined or floodfilled squares and circles. I'll include this method too in the code.

The second thing I'm going to do is add some constants that will help with the image frame number and playing field state ( empty, cross, circle ).

As for the game AI, the simplest way I can see to tackle the problem is to break it down into the steps the players would take.

   1. Can the computer win on this go?
     If Yes then Mark the winnig block, game over computer wins
     If No the goto step 2

   2. Is the player going to win on their next go?
     If Yes then block them using the computers go.
     If No then goto step 3

   3. Mark a random empty block   

   or a more advanced AI would

   3. Mark the block most likey to get the Computer a win
     This will be the position that give you the maximun number of possible lines.
     When there are multiple equally possible positions,
     then choose the one that reduces the number of possible lines the player has.
     otherwise randomly pick one.

But the more advanced version would be harder to code and near impossible to win, so I'm sticking with the random method. That way the player has a chance of winning as much as the computer. Althoug, eventually the player could learn how to win everytime.

Thats about it from me. I'll attach the new image and code to go with what I have explained here. Note the code doesnt actually require the image, but I have included a variable wich you can set to True to load the image file instead of generating the shapes.

Code: [Select]

;---------------------------------------------------
;
; TicTacToe writen by Tetra to aid the mebers at
;
; www.dbfinteractive.com
;
;---------------------------------------------------

AppTitle "TicTacToe - Press Escape to quit"

;-- Constants --------------------------------

;-- Square states / Image index ----------
;
; These constants double up in use,
; firstly to reprisent the square state
; in the array, secondly they reprisent
; the corresponding image frame for that
; shape
;
Const STATE_BLANK = 0
Const STATE_CIRCLE = 1
Const STATE_CROSS = 2
Const CURSOR_SQUARE = 3 ; The cursor image

Const SHAPE_PLAYER = STATE_CIRCLE ; Player is the circle
Const SHAPE_COMPUTER = STATE_CROSS  ; Computer is the cross

;--------------------------------------------/


;-- Program Constants ------------------------

;-------------------------------------
;  True: Loads the Tiles image
; False: Use Blitz graphics commands
;
Const USE_IMAGE_FILE = False

;-------------------------------------
; Tile information
;
Const TILE_WIDTH = 125
Const TILE_HEIGHT = 125
Const TILE_FRAMES =   4
Const TILE_FILENAME$ = "Tiles.png"

;--------------------------------------------/


;-- Globals ----------------------------------

;-- Square states / Image index --

Global tiles ; Global variable that will hold the tile images

Dim playing_field( 9 ) ; This stores the states/image_frame of the playing field

; |0|1|2|
; |3|4|5|
; |6|7|8|

;-- Playing Field information -----

Global playing_field_x = 132
Global playing_field_y =  52

Global winning_pos ; used for passing information from CheckLine() to CanPlayerWin()

Global whos_go = SHAPE_PLAYER ; whos go is it currently?

Global next_move ; used as a tempoary value in the main loop

;--------------------------------------------/


;-- Initialize ----------------------------------

Graphics 640,480,32,2

SeedRnd( MilliSecs() )

CreateTileImages()

;--------------------------------------------/


;-- Main Loop -------------------------------

SetBuffer( BackBuffer() )

While Not KeyDown(1)

;-----------------------------
; Check whos go it is and call
; the according function
;
If ( whos_go = SHAPE_PLAYER )

next_move = PlayerGo()

If ( next_move > -1 )
playing_field( next_move ) = SHAPE_PLAYER
whos_go = SHAPE_COMPUTER
CheckForWinner()
EndIf

ElseIf ( whos_go = SHAPE_COMPUTER )

next_move = ComputerGo()

If ( next_move > -1 )
playing_field( next_move ) = SHAPE_COMPUTER
whos_go = SHAPE_PLAYER
CheckForWinner()
EndIf

Else

;-----------------------------
; Display the correct message
;
Color( 255,255,255 )

Select ( whos_go )
Case -1
Text 10,10,"You have Won, well done!"
Text 10,30,"Press F1 to play again."
Case -2
Text 10,10,"You have Lost."
Text 10,30,"Press F1 to try again."
Case -3
Text 10,10,"The game was a Draw."
Text 10,30,"Press F1 to try again."
End Select

;-----------------------------
; Reset the playing field if
; F1 is pressed. Also randomly
; choose the player or
; computer to go first
;
If ( KeyDown( 59 ) )

If ( Rand(0,1) = 0 )
whos_go = SHAPE_PLAYER
Else
whos_go = SHAPE_COMPUTER
EndIf

For i = 0 To 8
playing_field( i ) = STATE_BLANK
Next

EndIf

EndIf

DrawPlayingField()

Flip
Cls

Wend

;--------------------------------------------/


;-- Program Ends ----------------------------

End

;--------------------------------------------/



;======================================================
;
; Functions
;
;======================================================

;-------------------------------------
; This function either loads or
; creates the tile images based on
; a Program Constants
;
Function CreateTileImages()

;-------------------------------------
; Load or Create the Tile images?
;
If ( USE_IMAGE_FILE )

;----------------------------------------
; Load the image and seperates the frames
;
tiles = LoadAnimImage( TILE_FILENAME$, TILE_WIDTH,TILE_HEIGHT, 0,TILE_FRAMES )

Else

;----------------------------------------
; Create an image with the right number
; of frames
;
tiles = CreateImage( TILE_WIDTH,TILE_HEIGHT, TILE_FRAMES )

;----------------------------------------
; Sets the drawing surface to the tile
; image, Blank frame
;
SetBuffer( ImageBuffer( tiles, STATE_BLANK ) )

Color( 128,128,64 )
Rect( 0,0, TILE_WIDTH,TILE_HEIGHT, False ) ; draw an outline Square

;----------------------------------------
; Sets the drawing surface to the tile
; image, Circle frame
;
SetBuffer( ImageBuffer( tiles, STATE_CIRCLE ) )

Color( 128,128,64 )
Rect( 0,0, TILE_WIDTH,TILE_HEIGHT, False ) ; draw an outline square

Color( 255,60,66 )
Oval( 15,20,93,89, False ) ; draw an outline Circle

;----------------------------------------
; Sets the drawing surface to the tile
; image, Cross frame
;
SetBuffer( ImageBuffer( tiles, STATE_CROSS ) )

Color( 128,128,64 )
Rect( 0,0, TILE_WIDTH,TILE_HEIGHT, False ) ; draw an outline square

Color( 0,0,255 )
Line( 14, 14, 110,110 ) ; Draw one side of the \
Line( 14,110, 110, 14 ) ; Draw the other side of the /

;----------------------------------------
; Sets the drawing surface to the tile
; image, Cursor frame
;
SetBuffer( ImageBuffer( tiles, CURSOR_SQUARE ) )

Color( 255,128,64 )
Rect( 26,26, 72,72, True ) ; draw a floodfilled Rectangle
Color( 0,0,0 )
Rect( 28,28, 68,68, True ) ; draw a floodfilled Rectangle

EndIf

End Function


;-------------------------------------
; Draws the Playing Field to the
; screen
;
Function DrawPlayingField()

Local x,y

For y = 0 To 2
For x = 0 To 2

DrawImage( tiles, playing_field_x + ( TILE_WIDTH * x ), playing_field_y + ( TILE_HEIGHT * y ), playing_field( x + ( y * 3 ) ) )

Next
Next

End Function


;-------------------------------------
; Returns the position the computer
; want to mark
;
Function PlayerGo()

Local pos = -1
Local x,y

;------------------------
; Did the player try to
; click on the playing
; field?
;
If ( MouseDown(1) )

;------------------------------
; If the mouse is over the
; playing field, then calculate
; he position its over
;
x = ( MouseX() - playing_field_x ) / TILE_WIDTH
y = ( MouseY() - playing_field_y ) / TILE_HEIGHT

If ( x >= 0 )And( x < 3 )And( y >=0 )And( y < 3 ) Then pos = x + ( y * 3 )

;------------------------------
; Make sure the selected block
; is blank
;
If ( playing_field( pos ) <> STATE_BLANK ) Then pos = -1

EndIf

Return pos

End Function


;-------------------------------------
; Returns the position the computer
; want to mark
;
Function ComputerGo()

Local pos = -1

;-----------------------------------
; Can the computer win on this go?
; If yes Return the winning move
; position
;
pos = CanPlayerWin( SHAPE_COMPUTER )
If ( pos > -1 ) Then Return pos

;-----------------------------------
; Can the player win?
; If yes Return the blocking move
; position
;
pos = CanPlayerWin( SHAPE_PLAYER )
If ( pos > -1 ) Then Return pos

;-----------------------------------
; Choose a random block to mark
;
pos = Rand(0,8)

While ( playing_field( pos ) <> STATE_BLANK )
pos = Rand(0,8)
Wend

;-----------------------------------
; Return the computers next move
;
Return pos

End Function

;-------------------------------------
; Checks to see if the player can win
; on their next go.
; Returns the wining position if true
; otherwise it returns -1
;
Function CanPlayerWin( aPlayer )

Local x,y

If ( CheckLine( 0,1,2, aPlayer ) ) Then Return winning_pos
If ( CheckLine( 3,4,5, aPlayer ) ) Then Return winning_pos
If ( CheckLine( 6,7,8, aPlayer ) ) Then Return winning_pos

If ( CheckLine( 0,3,6, aPlayer ) ) Then Return winning_pos
If ( CheckLine( 1,4,7, aPlayer ) ) Then Return winning_pos
If ( CheckLine( 2,5,8, aPlayer ) ) Then Return winning_pos

If ( CheckLine( 0,4,8, aPlayer ) ) Then Return winning_pos
If ( CheckLine( 2,4,6, aPlayer ) ) Then Return winning_pos

Return -1 ; the player cannot win on next go

End Function

;-------------------------------------
; Checks for a possible winning line
;
Function CheckLine( pos1, pos2, blank, aPlayer )

If ( playing_field( pos1 ) = aPlayer )And( playing_field( pos2 ) = aPlayer )And( playing_field( blank ) = STATE_BLANK )

winning_pos = blank
Return True

ElseIf ( playing_field( blank ) = aPlayer )And( playing_field( pos2 ) = aPlayer )And( playing_field( pos1 ) = STATE_BLANK )

winning_pos = pos1
Return True

ElseIf ( playing_field( pos1 ) = aPlayer )And( playing_field( blank ) = aPlayer )And( playing_field( pos2 ) = STATE_BLANK )

winning_pos = pos2
Return True

Else
Return False
EndIf

End Function


;-------------------------------------
;
Function CheckForWinner()


;--------------------------
; Has the player won?
;
If ( CheckWinningLine( 0,1,2, SHAPE_PLAYER ) ) Then whos_go = -1
If ( CheckWinningLine( 3,4,5, SHAPE_PLAYER ) ) Then whos_go = -1
If ( CheckWinningLine( 6,7,8, SHAPE_PLAYER ) ) Then whos_go = -1

If ( CheckWinningLine( 0,3,6, SHAPE_PLAYER ) ) Then whos_go = -1
If ( CheckWinningLine( 1,4,7, SHAPE_PLAYER ) ) Then whos_go = -1
If ( CheckWinningLine( 2,5,8, SHAPE_PLAYER ) ) Then whos_go = -1

If ( CheckWinningLine( 0,4,8, SHAPE_PLAYER ) ) Then whos_go = -1
If ( CheckWinningLine( 2,4,6, SHAPE_PLAYER ) ) Then whos_go = -1

;--------------------------
; Has the computer won?
;
If ( CheckWinningLine( 0,1,2, SHAPE_COMPUTER ) ) Then whos_go = -2
If ( CheckWinningLine( 3,4,5, SHAPE_COMPUTER ) ) Then whos_go = -2
If ( CheckWinningLine( 6,7,8, SHAPE_COMPUTER ) ) Then whos_go = -2

If ( CheckWinningLine( 0,3,6, SHAPE_COMPUTER ) ) Then whos_go = -2
If ( CheckWinningLine( 1,4,7, SHAPE_COMPUTER ) ) Then whos_go = -2
If ( CheckWinningLine( 2,5,8, SHAPE_COMPUTER ) ) Then whos_go = -2

If ( CheckWinningLine( 0,4,8, SHAPE_COMPUTER ) ) Then whos_go = -2
If ( CheckWinningLine( 2,4,6, SHAPE_COMPUTER ) ) Then whos_go = -2


Local pos = 0

;------------------------------
; Are there any blank blocks?

While ( pos < 9 )
If ( playing_field( pos ) = STATE_BLANK ) Then pos = 10
pos = pos + 1
Wend

;------------------------------
; If all the blocks are filled
; then its a draw

If ( pos = 9 )
whos_go = -3
EndIf

End Function

;-------------------------------------
; Checks for an actual winning line
;
Function CheckWinningLine( pos1, pos2, pos3, aPlayer )

If ( playing_field( pos1 ) = aPlayer )And( playing_field( pos2 ) = aPlayer )And( playing_field( pos3 ) = aPlayer )
Return True
Else
Return False
EndIf

End Function



Title: Re: Tic Tac Toe (Help)
Post by: ablade on June 25, 2007

Thanks mike_g and Tetra. I am confused with what mike_g wrote. I also didn't know you can use LoadAnimImage in that way. Thanks for your replys. I will look at the TicTacToe.zip soon.