AI – Artificial Intelligence – PBP Challenge For The Fittest

[T.Jackson]

<h2 style="color: red" align="center">
AI – Artificial Intelligence – Past, Present & Future. </h2>

In early days, scientists thought that the computer would experience something like an “electronic childhood”, in which it would gobble up the World’s libraries and then begin generating new radical wisdom. Seldom people talk this today because the problem of simulating intelligence is far more complex than just stuffing facts into the computer. Facts are useless without the ability to interpret and learn from them.

Until recently, computer-based games of chess could normally always be beaten at the hand of an average human player. In 1997, the expert system dubbed "Deep Blue" was the first computer to win a chess game against World champion Garry Kasparov. Today, developing chess AI is no longer considered a challenge for scientists. Arguably, even some modern Windows-based games of chess can be set to almost normally always win.

Today, expert systems, which have the ability to carry out complex human tasks, are on the rise. An expert system is a software package that is used with an extensive set of organized data that represents the computer as an expert for a specific task. It mimics the decision making of a human expert in this field. These programs are daunting to develop.

But the question on most people’s minds still remains. Can a computer really think for itself? No, and it never will. A computer will never be able compose original music of its own or write like Shakespeare. A computer has no passion, emotion, feelings or original thoughts. Computers follow rules of logic and nothing ever stands between this.

There’s another big hurdle too. How in the World can a computer ever be programmed to understand natural languages? The human language is just too diverse. Often many like words and phrases have entirely different meaning. Developing a program that can distinguish between facts & questions using everyday human context seems impossible. Nonetheless, the study of this field continues and, at current, not looking very promising. <br/>

<img src="http://www.picbasic.co.uk/forum/attachment.php?attachmentid=1587&stc=1&d=1178166656" align="left" >
<p>
Mid last year I developed an unbeatable AI for the well known game of Tic-Tac-Toe. A simple game indeed, but unfortunately not an equally as simple chore to code. After developing this project I gained some considerable respect for just how daunting AI programming can be. Note: screen shot shows an earlier version 0.3. A few trick moves allowed the player to beat AI every time. These have since been corrected.

Download game here (VB source code only): http://www.planet-source-code.com/vb/scripts/ShowCode.asp?txtCodeId=67151&lngWId=1
If you would like a compiled executable then this can be arranged.
</p>
<h2 style="color:green" align="center"><u>PBP Challenge For The Fittest</u></h2>
The challenge that I present to you all is to devise a game of Tic-Tac-Toe that is unbeatable using a graphical LCD, push buttons and other necessary components. Keep in mind that AI is only as strong as its creator's weakest link. Also, after a while, being beaten by a machine becomes quite frustrating, so the player may prefer a more intuitive opponent that isn't quite so perfect. In this instance AI will have "blonde" like moments where the player has an open space to make a move that could win them the game. This is a much more fun AI to play against. In my Windows version of the game I have coded AI to be about 95% unbeatable on hard, 75% on normal and 60% on easy. I confirmed that my AI is unbeatable by allowing the computer to play against itself many hundreds of times. Draw game always. And yes, Tic-Tac-Toe is indisputably flawed where best play leads to draw. <strong>Good Luck!</strong>
<br/>
Trent Jackson ©2007

[T.Jackson]

In addition - probably because I'm so open minded, I personally do believe it's possible for a computer to be programed to fully understand natural languages.
My personal opinion, I'm not saying this after reading from a text book - most books will probably share a similar negative attitude as I have already expressed.

[Darrel Taylor]

Trent,

A contest/challenge is typically associated with some sort of incentive.
Be it a prize, an award, or maybe just a gentleman's wager.

So assuming someone has spent the last couple days writing an Unbeatable Tic-Tac-Toe game in PicBasic Pro, and they decided to submit it.

What's the pay-off?
<br>

[T.Jackson]

I think a project competition with prizes would go down great. You already have a voting system in tact. But unfortunately, it's not such an obvious thing to be able to do. (This is one of the reasons why few threads actually have votes) The voting needs to be more clearly visible somewhere. It needs to be seen at a glance.

The other problem is that you're allowing people on the site without having to create an account. If you made it mandatory to sign up for membership after visiting the site more than a couple of times - this would possibly improve interaction. You could also enforce voting to some extent too.

[Darrel Taylor]

Sorry if that came out wrong! :confused:

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. :eek:
<br>

[T.Jackson]

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/>

[Darrel Taylor]

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. :eek:
<br>

[T.Jackson]

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



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

[T.Jackson]

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

[T.Jackson]

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

[T.Jackson]

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

[Darrel Taylor]

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

[T.Jackson]

I spent about a month studying Tic-Tac-Toe and developing the Windows-based software. Had a lot of fun doing this project as it gave me a greater sense for logic and a bit of an insight as to how the human mind thinks.

I tried many different protocols for AI. Including one that favors blocking the players move over winning the actual game itself. I was unable to produce anything successful with this. I think this is actually impossible, you just can't play the game with sole intentions of blocking. You've gotta play to win.

Interesting stuff - if it's your cup of tea.

[Darrel Taylor]

OK,

Well, I'll take that as there wasn't really a "Challenge" to begin with.

Nevermind.
<br>

[T.Jackson]

Oh I don't know about that. Coding a project like this in PBP would be twice as involved as doing it in Visual Basic. In fact, I don't know of any perfected Tic-Tac-Toe project that relies solely on an embedded system.

[Darrel Taylor]

You keep telling me how it's such a difficult task, and would take months to figure out.

And I keep telling you I've done it with a 16F and less than 4K words of code.

He said, she said.

Prove it, or go home.
<br>

[T.Jackson]

You know, if you stand on your head for a few minutes and count backwards from 1,000 you eventually loose gravity.

[Darrel Taylor]

There's 2 days of my life I'd rather have back. :mad:
<br>

[T.Jackson]

Here's a totally free copy of the Windows executable for everyone. First start by obtaining a required dll from here: <a href="http://www.dll-files.com/dllindex/dll-files.shtml?msvbvm50" target="_blank">Download msvbvm50.dll </a>

Now download TIC-TAC-TOE.zip below...

[leisryan]

Talking electronics has published a project using only pic16f84 TIC-TAC-Toe designed by Colin Mitchell and I had a first hand experienced in playing wth it, i must tell everyone that the AI implemented with it is so simple but so perfectly suited!!! the outcome is an uncanny pocket game!!! this topic must go with Darrel i believe it's not that hard!!!

[T.Jackson]

Talking Electronics has been defunct for many years. I always found most of their projects to be sloppy and half hearted.