Recent

Author Topic: TicTacToe_game (3*3) with AI  (Read 1178 times)

T_For_Vendetta

  • Newbie
  • Posts: 2
TicTacToe_game (3*3) with AI
« on: May 30, 2020, 05:11:11 pm »
Hi guys, I am new to lazarus and I was wondering if you can help me make this.
At this point I know that I should make 3*3 string grid and then computer will put for example O at random spot. (I can't solve this).
In addition to that stronger AI, should put the move on the spot whit most points. Best move=most points.
Any help would be greatly appreciated.

lucamar

  • Hero Member
  • *****
  • Posts: 2921
Re: TicTacToe_game (3*3) with AI
« Reply #1 on: May 30, 2020, 08:36:52 pm »
Google "solving tic-tac-toe". Plenty of pointers out there: it's have been a favourite in the AI field since the release of "War Games" :D

At this point I know that I should make 3*3 string grid and then computer will put for example O at random spot. (I can't solve this).

Getting a random spot to start is easy:

Code: Pascal  [Select][+][-]
  1. procedure GetFirstMove(var x, y: Integer);
  2. var
  3.   i: Integer;
  4. begin
  5.   Randomize;
  6.   i := Random(9);
  7.   x := i div 3;
  8.   y := i mod 3;
  9. end;
« Last Edit: May 30, 2020, 08:51:10 pm by lucamar »
Turbo Pascal 3 CP/M - Amstrad PCW 8256 (512 KB !!!) :P
Lazarus 2.0.8/FPC 3.0.4 - 32/64 bits on:
(K|L|X)Ubuntu 12..18, Windows XP, 7, 10 and various DOSes.

VTwin

  • Hero Member
  • *****
  • Posts: 900
  • Former Turbo Pascal 3 user
Re: TicTacToe_game (3*3) with AI
« Reply #2 on: May 30, 2020, 09:49:38 pm »
Getting a random spot to start is easy:

Although a "smart" computer wouldn't pick random start. :D 

When I was a kid I made a tic-tac-toe "computer" out of a cigar box, small lights, and magnetic switches. The "computer" always had a win or draw. ;D
“Talk is cheap. Show me the code.” -Linus Torvalds

macOS 10.13.6: Lazarus 2.0.6 (64 bit Cocoa, also fixes and trunk)
Ubuntu 18.04.3: Lazarus 2.0.6 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.0.6 (64 bit on VBox)

winni

  • Hero Member
  • *****
  • Posts: 1460
Re: TicTacToe_game (3*3) with AI
« Reply #3 on: May 30, 2020, 10:17:22 pm »
Short version :

Code: Pascal  [Select][+][-]
  1. function TicTacToe: TMyresult;
  2. begin
  3. result := stalemate;
  4. end;

Winni

T_For_Vendetta

  • Newbie
  • Posts: 2
Re: TicTacToe_game (3*3) with AI
« Reply #4 on: May 30, 2020, 10:50:33 pm »
Thank you guys for suggestions, if you come up with new solutions let me know.
Regards,
T

VTwin

  • Hero Member
  • *****
  • Posts: 900
  • Former Turbo Pascal 3 user
Re: TicTacToe_game (3*3) with AI
« Reply #5 on: May 30, 2020, 11:59:03 pm »
Just because I'm bored, I tried some of the games available online. Most of them use pretty terrible algorithms. This is the best I found:

https://www.mathsisfun.com/games/tic-tac-toe.html

If you play against Computer (Hard), and have not had too much to drink, you get winni's solution.

The fun part will working out the AI.

Enjoy,
VTwin
“Talk is cheap. Show me the code.” -Linus Torvalds

macOS 10.13.6: Lazarus 2.0.6 (64 bit Cocoa, also fixes and trunk)
Ubuntu 18.04.3: Lazarus 2.0.6 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.0.6 (64 bit on VBox)

Leledumbo

  • Hero Member
  • *****
  • Posts: 8222
  • Programming + Glam Metal + Tae Kwon Do = Me
Re: TicTacToe_game (3*3) with AI
« Reply #6 on: May 31, 2020, 12:18:09 am »
AI doesn't randomly move, it "thinks" (though sometimes random might be a viable decision). Tic-tac-toe is a classic example and is usually presented in intelligence system class as introduction to real world classic AI implementation. It differs from current AI trends which works through function fitting (also termed "learning"). AI was no more complex than a state space explorer with ability to find the best path to win.

Minimax (with or without alpha/beta pruning, it only differs in speed, not correctness) is the algorithm you're looking for to write an AI agent for this particular game, but going straight to this will only make you lost, unless your basic math is quite strong. In a game whose state space is limited like 3*3 tic-tac-toe, minimax can calculate all possible endings thus making the AI unbeatable. To make it weaker, you can adjust the depth of state space it must explore so it can only calculate as far as that depth. What makes your minimax different from everyone else is the heuristic function. This takes the current state and a rule that gives all possible next states then calculate which next state leads the AI agent closer to the winning state or at least draw.

Feel free to read the more technical explanation: https://en.wikipedia.org/wiki/Minimax

winni

  • Hero Member
  • *****
  • Posts: 1460
Re: TicTacToe_game (3*3) with AI
« Reply #7 on: May 31, 2020, 12:25:56 am »
The experiece says:

Start in a corner - otherwise you are lost.

Spend a lot of time with TicTacToe.
Waiting for the schoolbus as little boy.

Winni

VTwin

  • Hero Member
  • *****
  • Posts: 900
  • Former Turbo Pascal 3 user
Re: TicTacToe_game (3*3) with AI
« Reply #8 on: May 31, 2020, 02:32:17 am »
Like I said, implementing AI will be the fun part. :D

I'm sure you can implement an algorithm with a few simpler rules as a test project though. It does not have to win every time.

Have fun,
VTwin

“Talk is cheap. Show me the code.” -Linus Torvalds

macOS 10.13.6: Lazarus 2.0.6 (64 bit Cocoa, also fixes and trunk)
Ubuntu 18.04.3: Lazarus 2.0.6 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.0.6 (64 bit on VBox)

Mr.Madguy

  • Hero Member
  • *****
  • Posts: 507
Re: TicTacToe_game (3*3) with AI
« Reply #9 on: May 31, 2020, 10:03:10 am »
I have my old infinite board (any size may be set) project with several different AIs implemented as plug-ins, including my own AI, that can fight each other in any combinations and vs human players to determine, which one is the best. But for several reasons I won't post it's code. Mine AI is "medium difficulty", as it uses fast heuristics in order to play, but isn't that smart. I have my friend's AI, that is little bit harder. Not sure, if it's weight-based or heuristic-based.
« Last Edit: May 31, 2020, 10:10:43 am by Mr.Madguy »
DynamicData 3.0 is released!
Since now development is frozen - only optimization passes will be made at some point.
Lack of multiple inheritance turns it into abomination.

MarkMLl

  • Hero Member
  • *****
  • Posts: 925
Re: TicTacToe_game (3*3) with AI
« Reply #10 on: May 31, 2020, 10:58:12 am »
Just because I'm bored, I tried some of the games available online. Most of them use pretty terrible algorithms. This is the best I found:

https://www.mathsisfun.com/games/tic-tac-toe.html

If you play against Computer (Hard), and have not had too much to drink, you get winni's solution.

The fun part will working out the AI.

Enjoy,
VTwin

https://en.wikipedia.org/wiki/Pentago is far more interesting.

MarkMLl
Turbo Pascal v1 on CCP/M-86, multitasking with LAN and graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.

BeniBela

  • Hero Member
  • *****
  • Posts: 739
    • homepage
Re: TicTacToe_game (3*3) with AI
« Reply #11 on: May 31, 2020, 04:50:23 pm »
The smart AI will print "The only winning move is not to play" and then quit

Leledumbo

  • Hero Member
  • *****
  • Posts: 8222
  • Programming + Glam Metal + Tae Kwon Do = Me
Re: TicTacToe_game (3*3) with AI
« Reply #12 on: May 31, 2020, 07:52:05 pm »
The experiece says:

Start in a corner - otherwise you are lost.
This is exactly how my AI chooses. Not sure why, something is wrong with my heuristic or terminal function maybe. It thinks the corner is the best place to start and despite I never succeed to win against it, I still question why it didn't follow the textbook we used. The center is clearly a better choice as it closes many possibilities for the second player to win.

Mr.Madguy

  • Hero Member
  • *****
  • Posts: 507
Re: TicTacToe_game (3*3) with AI
« Reply #13 on: June 01, 2020, 09:25:21 am »
3x3 is so easy, that you can actually take all variants into account, i.e. build complete game tree.

Try this heuristic. I haven't tested it, but it should work. Check every cell and calculate weight as follows.
Weight[X] = number of lines, that cross this cell, that:
[1] Have 2 our X or O
[2] Have 2 enemy X or O
[3] Have 1 our X or O
[4] Aren't blocked by enemy X or O

Then Weight = Weight[1] * 1000 + Weight[2] * 100 + Weight[3] * 10 + Weight[4]

Then pick one with highest Weight.

P.S. This AI seems to be working. Only problem - it uses first available "best" move, not random one from list of equal ones.
« Last Edit: June 01, 2020, 03:28:21 pm by Mr.Madguy »
DynamicData 3.0 is released!
Since now development is frozen - only optimization passes will be made at some point.
Lack of multiple inheritance turns it into abomination.

Mr.Madguy

  • Hero Member
  • *****
  • Posts: 507
Re: TicTacToe_game (3*3) with AI
« Reply #14 on: June 08, 2020, 02:50:07 pm »
I've found flaw in logic of my AI - "prefer corner or center" heuristic is added between 2 and 3. Not sure, if this should have lower priority or not.
DynamicData 3.0 is released!
Since now development is frozen - only optimization passes will be made at some point.
Lack of multiple inheritance turns it into abomination.

 

TinyPortal © 2005-2018