Lazarus

Programming => General => Topic started by: T_For_Vendetta on May 30, 2020, 05:11:11 pm

Title: TicTacToe_game (3*3) with AI
Post by: T_For_Vendetta 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.
Title: Re: TicTacToe_game (3*3) with AI
Post by: lucamar 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

Quote from: T_For_Vendetta on May 30, 2020, 05:11:11 pm
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;
Title: Re: TicTacToe_game (3*3) with AI
Post by: VTwin on May 30, 2020, 09:49:38 pm
Quote from: lucamar on May 30, 2020, 08:36:52 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
Title: Re: TicTacToe_game (3*3) with AI
Post by: winni 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
Title: Re: TicTacToe_game (3*3) with AI
Post by: T_For_Vendetta 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
Title: Re: TicTacToe_game (3*3) with AI
Post by: VTwin 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
Title: Re: TicTacToe_game (3*3) with AI
Post by: Leledumbo 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
Title: Re: TicTacToe_game (3*3) with AI
Post by: winni 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
Title: Re: TicTacToe_game (3*3) with AI
Post by: VTwin 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

Title: Re: TicTacToe_game (3*3) with AI
Post by: Mr.Madguy 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.
Title: Re: TicTacToe_game (3*3) with AI
Post by: MarkMLl on May 31, 2020, 10:58:12 am
Quote from: VTwin 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

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

MarkMLl
Title: Re: TicTacToe_game (3*3) with AI
Post by: BeniBela on May 31, 2020, 04:50:23 pm
The smart AI will print "The only winning move is not to play" and then quit
Title: Re: TicTacToe_game (3*3) with AI
Post by: Leledumbo on May 31, 2020, 07:52:05 pm
Quote from: winni on May 31, 2020, 12:25:56 am
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.
Title: Re: TicTacToe_game (3*3) with AI
Post by: Mr.Madguy 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.
Title: Re: TicTacToe_game (3*3) with AI
Post by: Mr.Madguy 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.
Title: Re: TicTacToe_game (3*3) with AI
Post by: Thaddy on June 08, 2020, 04:22:02 pm
@Schuler
This is a perfect example for your library.. Maybe you will find the time to answer...
TinyPortal © 2005-2018