AI – Artificial Intelligence – PBP Challenge For The Fittest


Closed Thread
Results 1 to 21 of 21

Hybrid View

  1. #1
    Join Date
    Jul 2003
    Location
    Colorado Springs
    Posts
    4,959


    Did you find this post helpful? Yes | No

    Default

    Sorry if that came out wrong!

    What I meant to say was....

    I've just spent the last two days writing an unbeatable Tic-Tac-Toe program for PicBasic Pro.

    There seems to have been a challenge to do so, so I accepted it without even knowing Why. (other than it seemed interesting)

    As you've already pointed out, it's not as easy as it first seems.
    I'm currently trying to finish up the third version.
    The first two did more toward teaching me how to play Tic-Tac-Toe than they did actually playing it.

    One thing I found interesting with those two versions was, when you let the PIC play against itself, it was always a draw. But when you played it yourself, it was quite easy to beat. Even the first version was like that.

    So I have to question the reasoning that letting a program play against itself somehow proves that it's unbeatable. It may just be playing at the same level.

    With that in mind, I think that the only way to determine who's is the closest to Un-Beatable, we need to come up with a way to have the programs play each other.

    But then there's that what's in it for me thing.
    <br>
    DT

  2. #2
    T.Jackson's Avatar
    T.Jackson Guest


    Did you find this post helpful? Yes | No

    Smile Right on...

    Did you take a look at the Visual Basic source? If the protocol is correct - AI is solid if it always draws while playing against itself. But it can't always follow hard coded rules of logic. This I suspect is where your error is.

    Protocol should be as follows:

    AI checks for winning move.
    AI checks to block opponents win.
    AI makes move at random. (without this you can't verify AI's strength if set to play against itself)
    <br/>
    Last edited by T.Jackson; - 5th May 2007 at 03:54.

  3. #3
    Join Date
    Jul 2003
    Location
    Colorado Springs
    Posts
    4,959


    Did you find this post helpful? Yes | No

    Default

    Quote Originally Posted by T.Jackson View Post
    Did you take a look at the Visual Basic source?
    No. It was a total process of "Trial&Error".
    I did a search on Google, but came up with a bunch of C++
    Might as well have shown me a map to antarctica. Would have helped just as much.

    So the idea is a completely original re-creation of what I'm sure 1,000 other people have already done.

    ... This I suspect is where your error is.
    Here's where the challenge comes in. . . . You think I have Errors!

    Protocol should be as follows:

    AI checks for winning move.
    AI checks to block opponents win.
    AI makes move at random. (without this you can't verify AI's strength if set to play against itself)
    If I recall, that was version 1.
    <br>
    DT

  4. #4
    T.Jackson's Avatar
    T.Jackson Guest


    Did you find this post helpful? Yes | No

    Post VB Source Portion A

    I can't paste the entire source - (500,000 chrs in length) - So I'll instead post the 3 main procedures of the protocol.

    Code:
    Public Sub Perform_Calculated_Move(Compare As Integer)
       '-----------------------------------------------------------------------------
       'Procedure is called for when CPU is attempting to block your win or win the
       'actual game itself. For calculated blocking Compare is set to 0. When the CPU
       'decides that there are no wining moves, it will then attempt to block your win.
       'Compare is then set to 1. Looking at all angles, rows, cols & diagonal streaks.
       '-----------------------------------------------------------------------------
       '//
       Dim i As Long
       Dim j As Long
                 '//
                 'Check diagonal \, do we have 2?
       '//
       If Grid_Set(0, 0) = Players_CHR(Compare) And Grid_Set(2, 2) = Players_CHR(Compare) And Grid_Set(1, 1) = 0 Then
          Grid_Set(1, 1) = Players_CHR(Players_Turn)
          CPU_Moved = True
                 Exit Sub
          
          ElseIf Grid_Set(0, 0) = Players_CHR(Compare) And Grid_Set(1, 1) = Players_CHR(Compare) And Grid_Set(2, 2) = 0 Then
                 Grid_Set(2, 2) = Players_CHR(Players_Turn)
                 CPU_Moved = True
                 Exit Sub
       '//
          ElseIf Grid_Set(1, 1) = Players_CHR(Compare) And Grid_Set(2, 2) = Players_CHR(Compare) And Grid_Set(0, 0) = 0 Then
                 Grid_Set(0, 0) = Players_CHR(Players_Turn)
                 CPU_Moved = True
                 Exit Sub
       
                 '//
                 'Now checking diagonal /, do we have 2?
       
          ElseIf Grid_Set(0, 2) = Players_CHR(Compare) And Grid_Set(1, 1) = Players_CHR(Compare) And Grid_Set(2, 0) = 0 Then
                 Grid_Set(2, 0) = Players_CHR(Players_Turn)
                 CPU_Moved = True
                 Exit Sub
                      
          ElseIf Grid_Set(0, 2) = Players_CHR(Compare) And Grid_Set(2, 0) = Players_CHR(Compare) And Grid_Set(1, 1) = 0 Then
                 Grid_Set(1, 1) = Players_CHR(Players_Turn)
                 CPU_Moved = True
                 Exit Sub
       '//
          ElseIf Grid_Set(1, 1) = Players_CHR(Compare) And Grid_Set(2, 0) = Players_CHR(Compare) And Grid_Set(0, 2) = 0 Then
                 Grid_Set(0, 2) = Players_CHR(Players_Turn)
                 CPU_Moved = True
                 Exit Sub
          End If
                 '//
                 'Now checking rows consiting 2
       
          If Not CPU_Moved Then
             For j = 0 To 2
                 If Grid_Set(j, 0) = Players_CHR(Compare) And Grid_Set(j, 1) = Players_CHR(Compare) And Grid_Set(j, 2) = 0 Then
                    Grid_Set(j, 2) = Players_CHR(Players_Turn)
                    CPU_Moved = True
                    Exit For
       '//
                    ElseIf Grid_Set(j, 0) = Players_CHR(Compare) And Grid_Set(j, 2) = Players_CHR(Compare) And Grid_Set(j, 1) = 0 Then
                           Grid_Set(j, 1) = Players_CHR(Players_Turn)
                           CPU_Moved = True
                           Exit For
       '//
                    ElseIf Grid_Set(j, 1) = Players_CHR(Compare) And Grid_Set(j, 2) = Players_CHR(Compare) And Grid_Set(j, 0) = 0 Then
                           Grid_Set(j, 0) = Players_CHR(Players_Turn)
                           CPU_Moved = True
                           Exit For
                 '//
                 'Now checking cols consiting 2
                    
                    ElseIf Grid_Set(0, j) = Players_CHR(Compare) And Grid_Set(1, j) = Players_CHR(Compare) And Grid_Set(2, j) = 0 Then
                           Grid_Set(2, j) = Players_CHR(Players_Turn)
                           CPU_Moved = True
                           Exit For
       '//
                    ElseIf Grid_Set(0, j) = Players_CHR(Compare) And Grid_Set(2, j) = Players_CHR(Compare) And Grid_Set(1, j) = 0 Then
                           Grid_Set(1, j) = Players_CHR(Players_Turn)
                           CPU_Moved = True
                           Exit For
       '//
                    ElseIf Grid_Set(1, j) = Players_CHR(Compare) And Grid_Set(2, j) = Players_CHR(Compare) And Grid_Set(0, j) = 0 Then
                           Grid_Set(0, j) = Players_CHR(Players_Turn)
                           CPU_Moved = True
                           Exit For
                    End If
              Next
          End If
    End Sub
    Last edited by T.Jackson; - 5th May 2007 at 09:27.

  5. #5
    T.Jackson's Avatar
    T.Jackson Guest


    Did you find this post helpful? Yes | No

    Post VB Source Portion B

    Code:
    Public Sub CPU_Makes_Move()
       '-----------------------------------------------------------------------------
       '*Here we check for 2 or more of the player's chr on the same row or col,
       'the odds that we generate determine as to if we apply the move.
       '-----------------------------------------------------------------------------
       '//
       Dim Apply_Move As Boolean 'Allow CPU to apply calculated move if set true
       Dim i          As Long    'General working var
       Dim j          As Long    '""
       Dim CPU_Odds   As Long    'Random odds based on difficulty setting
                                 '(to apply or not to apply the calulated move)
       CPU_Moved = False
       '//
                   For i = 0 To (Rnd * 100) + 1
                       CPU_Odds = (Rnd * 100) 'Rnd num of samples (really scramble it)
                   Next
                   '//
                   'chance % that CPU will make calculated move
                   Select Case Game_Difficulty
                          Case 0              'Easy, 60%
                               If CPU_Odds <= 60 Then Apply_Move = True
                          Case 1              'Norm, 80%
                               If CPU_Odds <= 80 Then Apply_Move = True
                          Case 2              'hard, 95%
                               If CPU_Odds <= 95 Then Apply_Move = True
                   End Select
       '//
                   If Apply_Move Then         'Flag set?
       '//
       'Is there a winning possibility in the next move for CPU?
                      Call Perform_Calculated_Move(1)
       '//
       'Lets analyze player's game play, something to block?
                      If Not CPU_Moved Then
                         Call Perform_Calculated_Move(0)
                      End If
       '//
       '-----------------------------------------------------------------------------
       '(Nothing to analyze, nothing to win nor block)
       'Pick middle if empty or decide on corner to pick (depending on player's moves)
       '-----------------------------------------------------------------------------
                      If Not CPU_Moved Then
                         If Grid_Set(1, 1) = 0 Then     'Middle
                            CPU_Moved = True
                            Grid_Set(1, 1) = Players_CHR(Players_Turn)
                          
                         ElseIf Grid_Set(2, 2) = 0 Then 'Bottom right?
                            If Grid_Set(1, 2) = Players_CHR(0) Or Grid_Set(2, 1) = Players_CHR(0) Then
                               CPU_Moved = True
                               Grid_Set(2, 2) = Players_CHR(Players_Turn)
                            End If
                                
                         ElseIf Grid_Set(0, 0) = 0 Then 'Top left?
                            If Grid_Set(0, 2) <> Players_CHR(0) Then
                               CPU_Moved = True
                               Grid_Set(0, 0) = Players_CHR(Players_Turn)
                            End If
                            
                         ElseIf Grid_Set(0, 2) = 0 Then 'Top right?
                            If Grid_Set(0, 0) <> Players_CHR(0) Then
                               CPU_Moved = True
                               Grid_Set(0, 2) = Players_CHR(Players_Turn)
                            End If
                            
                         ElseIf Grid_Set(2, 0) = 0 Then 'Bottom left?
                            CPU_Moved = True
                            Grid_Set(2, 0) = Players_CHR(Players_Turn)
                         End If
                      End If
       '//
       '-----------------------------------------------------------------------------
       'Look for row / col with CPU's prior moves, then check for empty
       'col or row, if that fails look for one of player's prior moves.
       '-----------------------------------------------------------------------------
       '//
                      For j = 1 To 0 Step -1
                          If Not CPU_Moved Then
                             For i = 0 To 2
                                 If Grid_Set(0, i) = Players_CHR(j) And Grid_Set(2, i) = 0 And Grid_Set(1, i) = 0 Then
                                    Grid_Set(1, i) = Players_CHR(Players_Turn)
                                    CPU_Moved = True
                                    Exit For
                                
                                 ElseIf Grid_Set(1, i) = Players_CHR(j) And Grid_Set(2, i) = 0 And Grid_Set(0, i) = 0 Then
                                    Grid_Set(0, i) = Players_CHR(Players_Turn)
                                    CPU_Moved = True
                                    Exit For
                         
                                 ElseIf Grid_Set(2, i) = Players_CHR(j) And Grid_Set(1, i) = 0 And Grid_Set(0, i) = 0 Then
                                   Grid_Set(0, i) = Players_CHR(Players_Turn)
                                   CPU_Moved = True
                                   Exit For
                                 End If
                             Next
                          End If
            '//
            'Row
                          If Not CPU_Moved Then
                             For i = 0 To 2
                                 If Grid_Set(i, 0) = Players_CHR(j) And Grid_Set(i, 2) = 0 And Grid_Set(i, 1) = 0 Then
                                    Grid_Set(i, 1) = Players_CHR(Players_Turn)
                                    CPU_Moved = True
                                    Exit For
                                
                                 ElseIf Grid_Set(i, 1) = Players_CHR(j) And Grid_Set(i, 2) = 0 And Grid_Set(i, 0) = 0 Then
                                    Grid_Set(i, 0) = Players_CHR(Players_Turn)
                                    CPU_Moved = True
                                    Exit For
                         
                                 ElseIf Grid_Set(i, 2) = Players_CHR(j) And Grid_Set(i, 1) = 0 And Grid_Set(i, 0) = 0 Then
                                    Grid_Set(i, 0) = Players_CHR(Players_Turn)
                                    CPU_Moved = True
                                    Exit For
                                 End If
                             Next
                          End If
       '//
       'No prior CPU moves?, find empty col
                          If Not CPU_Moved Then
                             For i = 0 To 2
                                 If Grid_Set(0, i) = 0 And Grid_Set(2, i) = 0 And Grid_Set(1, i) = 0 Then
                                    Grid_Set(0, i) = Players_CHR(Players_Turn)
                                    CPU_Moved = True
                                    Exit For
                                 End If
                             Next
                          End If
       '//
       'No empty col?, find row
                          If Not CPU_Moved Then
                             For i = 0 To 2
                                 If Grid_Set(i, 0) = 0 And Grid_Set(i, 2) = 0 And Grid_Set(i, 1) = 0 Then
                                    Grid_Set(i, 0) = Players_CHR(Players_Turn)
                                    CPU_Moved = True
                                    Exit For
                                 End If
                             Next
                          End If
                      Next
                   '//
                   Else   'The odds are on the players side, make move by chance
                   '//
       'No brainer move', (go fetch any rnd pos)
                      Call Find_Random_Spot
                   End If
       '//
       Players_Turn = Players_Turn + 1                 'Player makes next turn
     Players_Turn = Players_Turn Mod 2                 'Limit val to 1, player's take successive turns
           Move_Count = Move_Count + 1                 'Keep track of moves, max of 9
                      Call Scrn_Render                 'Render graphics
                    Call Check_For_Win                 'Check for wining line
    End Sub

  6. #6
    T.Jackson's Avatar
    T.Jackson Guest


    Did you find this post helpful? Yes | No

    Post VB Source Portion C

    Code:
    Public Sub Check_For_Win()
       '-----------------------------------------------------------------------------
       '*Someone win game?, check all possibilities line ups of 3 both X & O
       '-----------------------------------------------------------------------------
       Dim Count_Correct     As Long    'Total of correct in line up / sequence
       Dim Wining_Line(3, 3) As Long    'Store coords of matrix
       Dim i                 As Long    'General working var
       Dim j                 As Long    '""
       Dim k                 As Long    '""
       Dim e                 As Long    '""
       Dim XO_Wins(1)        As Boolean 'X & O flgas set true if game won
       '//
       For j = 0 To 1
           If Not XO_Wins(0) And Not XO_Wins(1) Then
              For k = 0 To 2                           'This array allows us to blink the wining line
                  For i = 0 To 2                       '
                      Wining_Line(i, k) = 0            'Reset for next check
                  Next
              Next
              Count_Correct = 0
       '//
       'Check rows ply1, ply2 or CPU
              For e = 0 To 2
                  For i = 0 To 2
                      If Grid_Set(e, i) = (j + 1) Then 'Inc
                         Count_Correct = Count_Correct + 1
                         Wining_Line(e, i) = 1         'Set
                      End If
                  Next
                  XO_Wins(j) = (Count_Correct = 3)     'Set flag if 3 in a row
                  '//
                  If Not XO_Wins(0) And Not XO_Wins(1) Then
                     For k = 0 To 2                    'Reset for next check
                         For i = 0 To 2                '
                             Wining_Line(i, k) = 0     '
                         Next
                     Next
                     Count_Correct = 0
                  Else
                     Exit For                          'Bail out we have a winner
                  End If
              Next
           End If
       '//
           If Not XO_Wins(0) And Not XO_Wins(1) Then
              For k = 0 To 2                           'Reset for next check
                  For i = 0 To 2                       '
                      Wining_Line(i, k) = 0            '
                  Next
              Next
              Count_Correct = 0
       '//
       'Cols
              For e = 0 To 2
                  For i = 0 To 2
                      If Grid_Set(i, e) = (j + 1) Then 'Inc
                         Count_Correct = Count_Correct + 1
                         Wining_Line(i, e) = 1         'Set
                      End If
                  Next
                  XO_Wins(j) = (Count_Correct = 3)     'Set flag if 3 in a row
                  '//
                  If Not XO_Wins(0) And Not XO_Wins(1) Then
                     For k = 0 To 2                    'Reset for next check
                         For i = 0 To 2                '
                             Wining_Line(i, k) = 0     '
                         Next
                     Next
                     Count_Correct = 0
                  Else
                     Exit For                          'Bail out we have a winner
                  End If
              Next
           End If
       '//
       'Test diagonal \
           If Not XO_Wins(0) And Not XO_Wins(1) Then
              For k = 0 To 2                           'Reset for next check
                  For i = 0 To 2                       '
                      Wining_Line(i, k) = 0            '
                  Next
              Next
              Count_Correct = 0
              '//
              For i = 0 To 2
                  If Grid_Set(i, i) = (j + 1) Then
                     Count_Correct = Count_Correct + 1 'Inc
                     Wining_Line(i, i) = 1             'Set
                  End If
              Next
              XO_Wins(j) = (Count_Correct = 3)         'Set flag if 3 in a row
           End If
       '//
           If Not XO_Wins(0) And Not XO_Wins(1) Then
              For k = 0 To 2                           'Reset for next check
                  For i = 0 To 2                       '
                      Wining_Line(i, k) = 0            '
                  Next
              Next
              Count_Correct = 0
              k = 0
       '//
       'Diagonal /
              For i = 2 To 0 Step -1
                  If Grid_Set(k, i) = (j + 1) Then
                     Count_Correct = Count_Correct + 1 'Inc
                     Wining_Line(k, i) = 1             'Set
                  End If                               '
                  k = k + 1                            'Inc offset for / check
              Next
              k = 0
              XO_Wins(j) = (Count_Correct = 3)         'Set flag if 3 in a row
           End If
       Next
       '//
       Dim Player_Won As Byte
       If XO_Wins(0) Or XO_Wins(1) Then                'X or O Win flags set?
          '//                                          '
          Select Case XO_Wins(1)                       'Which one?
                 '//                                   '
                 Case True                             '
                      If Players_CHR(0) = 2 Then       'Wining player using 0 or X?
                         Player_Won = 0                'Add to stats
                         Total_Losses(1) = Total_Losses(1) + 1
                      Else
                         Player_Won = 1                'Add to stats
                         Total_Losses(0) = Total_Losses(0) + 1
                      End If
                 '//
                 Case Else
                 '//
                      If Players_CHR(0) = 2 Then
                         Player_Won = 1                'Add to stats
                         Total_Losses(0) = Total_Losses(0) + 1
                      Else
                         Player_Won = 0                'Add to stats
                         Total_Losses(1) = Total_Losses(1) + 1
                      End If
          End Select
      '//
      'Inform who won
          Game_Msg.Caption = Players_Name(Player_Won) & " WON!"
          Total_Wins(Player_Won) = Total_Wins(Player_Won) + 1
      '//
          If Settings_Play_Sound.Checked Then
             i = sndPlaySound(App.Path & "\Win.wav", CSNDaSync)
          End If
      '//
      'Player's or CPU's best time?
          If Game_Duration < Best_Time(Player_Won) Or Best_Time(Player_Won) = 0 Then
             Best_Time(Player_Won) = Game_Duration
          End If
      '//
          Game_Rounds = Game_Rounds + 1                'Inc round count
          Call LED_Displays                            'Refresh displays
          Game_Over = True                             'Flag set
      '//
          If Not Terminate_App Then                    'Object still loaded?
             For e = 0 To 10
                 For i = 0 To 2
                     For j = 0 To 2
                  'Scrn_Render all current
                         BitBlt Play_Area.hDC, 9 + (i * 60), 9 + (j * 60), 45, 45, X0(Grid_Set(j, i)).hDC, 0, 0, SrcCopy
       '//
                  'Flash render wining
                         If k And Wining_Line(j, i) Then
                            BitBlt Play_Area.hDC, 9 + (i * 60), 9 + (j * 60), 45, 45, X0(0).hDC, 0, 0, SrcCopy
                         End If
                     Next
                 Next
       '//
                 Call Delay(250)                       '250mS
                 Play_Area.Cls                         'Wipe screen
                 k = k + 1                             'Inc K which allows the winning line to be flashed
                 k = k Mod 2                           'Reset K
                 DoEvents                              'Yeild to OS
       '//
       'Player select new round or request app term?, bail out of here is so...
                 If Game_Duration = 0 Or Terminate_App Then Exit For
             Next
          End If
       '//
       'Music playing?
          If Not Terminate_App Then
             If Settings_Play_Music.Checked Then
                Music ("stop med")                     'Cease music!
             End If
          End If
       End If
    End Sub

  7. #7
    T.Jackson's Avatar
    T.Jackson Guest


    Did you find this post helpful? Yes | No

    Post

    You'll need a big PIC with a lot of code space to properly do this project.

  8. #8
    Join Date
    Jul 2003
    Location
    Colorado Springs
    Posts
    4,959


    Did you find this post helpful? Yes | No

    Default

    I can do it on a 16F877.
    <br>
    DT

Members who have read this thread : 1

You do not have permission to view the list of names.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts