Jump to content




TicTacToe with real AI, using AI API (Neural Network)


28 replies to this topic

#1 Creator

    Mad Dash Victor

  • Members
  • 2,168 posts
  • LocationYou will never find me, muhahahahahaha

Posted 15 October 2015 - 07:43 PM

Hi guys,

as I promised in this thread, I am publishing the game TicTacToe. It uses my AI API and should be able to learn. However, the code is not ready. I just came up with an idea to train it, so implementing it might take some time. I am only publishing it because I promised I'd do it. Shouldn't have done that.

Anyways, here are the downloads.
pastebin get TFxkELib TTT
pastebin get GHHCma5U AI


#2 SquidDev

    Frickin' laser beams | Resident Necromancer

  • Members
  • 1,427 posts
  • LocationDoes anyone put something serious here?

Posted 15 October 2015 - 08:13 PM

Hmm, interesting. A project I did for a friend recently was writing a program to play a board game. However I found for trivial games such as that (and Tic Tac Toe) that just using min-max and then scoring the board was easier to implement and pretty effective. Seeing as there are only 362880 138 possible end board states, it should be just as efficient. I guess another issue with using a neural net is that it is harder to cope with boards which are technically identical but aren't (rotations, reflections) - it might be possible to standardise the board.

Otherwise, this is pretty cool - heh, maybe there should be a ComputerCraft pencil-paper/board game competition! Obviously you haven't done tons of work on it yet, but just wondering how effectively it plays against itself?

#3 Creator

    Mad Dash Victor

  • Members
  • 2,168 posts
  • LocationYou will never find me, muhahahahahaha

Posted 15 October 2015 - 08:36 PM

Well, at the moment it does not play at all because I have not figured out an effective way to train it. Min-Max is better I suppose.

Maybe AI should be used to recognize handwritten letters intsead.

#4 Bomb Bloke

    Hobbyist Coder

  • Moderators
  • 7,099 posts
  • LocationTasmania (AU)

Posted 15 October 2015 - 08:39 PM

View PostSquidDev, on 15 October 2015 - 08:13 PM, said:

... just wondering how effectively it plays against itself?

... and what conclusions it draws about "the only winning move"?

#5 Creator

    Mad Dash Victor

  • Members
  • 2,168 posts
  • LocationYou will never find me, muhahahahahaha

Posted 15 October 2015 - 10:02 PM

What is the only winning move?

#6 Lyqyd

    Lua Liquidator

  • Moderators
  • 8,465 posts

Posted 15 October 2015 - 11:57 PM

Not to play, of course.

#7 SquidDev

    Frickin' laser beams | Resident Necromancer

  • Members
  • 1,427 posts
  • LocationDoes anyone put something serious here?

Posted 16 October 2015 - 06:40 AM

View PostBomb Bloke, on 15 October 2015 - 08:39 PM, said:

View PostSquidDev, on 15 October 2015 - 08:13 PM, said:

... just wondering how effectively it plays against itself?

... and what conclusions it draws about "the only winning move"?

View PostLyqyd, on 15 October 2015 - 11:57 PM, said:


I was wondering when someone was going to quote that. How about a nice game of Chess?

#8 Waitdev_

  • Members
  • 432 posts
  • LocationAdelaide

Posted 16 October 2015 - 07:01 AM

hmm... it seems like its trying to go down from 9-1


it's not learning anything...

#9 Creator

    Mad Dash Victor

  • Members
  • 2,168 posts
  • LocationYou will never find me, muhahahahahaha

Posted 16 October 2015 - 07:36 AM

I know. At this point it is useless.

#10 Andrew2060

  • Members
  • 109 posts
  • LocationLos Angeles, California

Posted 16 October 2015 - 08:52 AM

All I see in the application of AI is basically nuclear defense.

It would be interesting to watch two AI's continuously fire at each other until they figure out how to prevent losses.
Well in actuality one would not be that stupid to hand over the Ability to kill 200 million in seven minutes to a computer.

You should try and get it to play against itself just like in the movie.
The only way to win tic tac toe against itself is not to play, it learns this by trying every possibility in every way.
Hence it relates to nuclear war, everybody loses somehow.

#11 Creator

    Mad Dash Victor

  • Members
  • 2,168 posts
  • LocationYou will never find me, muhahahahahaha

Posted 16 October 2015 - 08:57 AM

That statement is so deep. And by the way I will watch the movie and learn something from it.

#12 Creator

    Mad Dash Victor

  • Members
  • 2,168 posts
  • LocationYou will never find me, muhahahahahaha

Posted 16 October 2015 - 01:29 PM

How could I train the Neural Network to play TicTacToe like a pro?

#13 H4X0RZ

  • Members
  • 1,315 posts
  • LocationGermany

Posted 16 October 2015 - 01:45 PM

Maybe make it play against a bot (which always takes the best spot) for thousands of rounds until it learned from that?

#14 Creator

    Mad Dash Victor

  • Members
  • 2,168 posts
  • LocationYou will never find me, muhahahahahaha

Posted 16 October 2015 - 02:34 PM

When I let it play vs a bot, the AI also needs to know what is should have done. How do I get that info?

#15 H4X0RZ

  • Members
  • 1,315 posts
  • LocationGermany

Posted 16 October 2015 - 04:53 PM

Make it choose random fields for the first hundred (or so) rounds and collect the random fields+if that move was "worth" it (if it gave the AI an advantage or atleast didn't make the game worse)+the steps the enemy did. This way you can tell the AI which moves are good, or bad, under specific circumstances because the AI "learn't" from the best bot possible. (ok, depends on the way you made the bot.)

A bit like watching a small kid play and then telling him/her if it was a good move but automated.

Edited by H4X0RZ, 16 October 2015 - 04:54 PM.


#16 Bomb Bloke

    Hobbyist Coder

  • Moderators
  • 7,099 posts
  • LocationTasmania (AU)

Posted 16 October 2015 - 10:28 PM

I haven't looked at your code and have little idea how a "neural network" works, but it seems to me that you'd need to hard-code some concepts in if you wanted an AI to be able to play - even if it's just the shape of the board, how to make a move, the concept of turns, and the concepts of winning (the goal) and losing (something to avoid).

I'd probably also cheat a bit and program in what the win condition is, rather than having the AI try to figure that out for itself. That way, it'd at least know that it should 1) be attempting to make lines and 2) blocking its opponent's attempts to complete lines. Creating an AI that could figure out those two (fairly abstract) concepts on its own is entirely possible, but it'd increase the amount of code involved by a fair margin. The point is that it needs to understand the game before it can play the game.

Once it hits that point, having it play against itself would enable it to figure out the best opening moves, and the priorities it should be assigning to offensive/defensive moves, until all games it plays are draws.

#17 H4X0RZ

  • Members
  • 1,315 posts
  • LocationGermany

Posted 16 October 2015 - 11:44 PM

View PostBomb Bloke, on 16 October 2015 - 10:28 PM, said:

I haven't looked at your code and have little idea how a "neural network" works, but it seems to me that you'd need to hard-code some concepts in if you wanted an AI to be able to play - even if it's just the shape of the board, how to make a move, the concept of turns, and the concepts of winning (the goal) and losing (something to avoid).

I'd probably also cheat a bit and program in what the win condition is, rather than having the AI try to figure that out for itself. That way, it'd at least know that it should 1) be attempting to make lines and 2) blocking its opponent's attempts to complete lines. Creating an AI that could figure out those two (fairly abstract) concepts on its own is entirely possible, but it'd increase the amount of code involved by a fair margin. The point is that it needs to understand the game before it can play the game.

Once it hits that point, having it play against itself would enable it to figure out the best opening moves, and the priorities it should be assigning to offensive/defensive moves, until all games it plays are draws.

(This is just my understanding of neural networks and could be far off of the actual way a neural network works)

A neuron basically has an input, an activator function and an output. The input is and output is always a number. When a neuron get's input the input is given to the activator function which checks if the input should pass (by checking if the input is greater than a specific threshold IIRC) and if the activator function returns true the output gives it number over to every neuron on the next layer or to the output layer.

Like this.
Spoiler

When backward propagating you give the NN (Neural Network) an expected outcome and an in input. The NN "executes" with the given input and, if the output and the expected output aren't the same, it will change the threshold of specific (or all) neurons a bit so it will be more likely that it outputs the expected results. Because the changes are minor it has to train a lot to get better.

Edited by H4X0RZ, 16 October 2015 - 11:45 PM.


#18 Bomb Bloke

    Hobbyist Coder

  • Moderators
  • 7,099 posts
  • LocationTasmania (AU)

Posted 17 October 2015 - 01:59 AM

So essentially a bunch of adjustable semiconductor diodes hooked up to a bunch of AND gates... hmm.

The trick would be to have the inputs passed in be "the state of the board after every turn it takes", and the expected outputs passed in being "random layouts which represent a victory for the NN, with a line of three in them".

To prevent confusion, you'd ensure every example "victory" layout you feed it was based on the current state of play - just randomly generate moves for BOTH players until the game is won (regenerating if it's a lose/draw for the AI). If a victory wasn't possible from the current state (or if you simply failed to get a "victory" within a certain number of randomisations, at least), you wouldn't feed the NN any more data until the next game.

#19 Creator

    Mad Dash Victor

  • Members
  • 2,168 posts
  • LocationYou will never find me, muhahahahahaha

Posted 17 October 2015 - 06:18 AM

Thanks for the suggestions. I will certainly be considering those. I also got another idea. I make it play normally and at the end of the game, if it won, I approve of the moves and if it lost I disapprove of the moves. That way it will know for each and every situation what the thing to do is. If it does a wrong move, I will have another algorithm find out the best move with the given and train it to do that.

Neurons also have wieghts, meaning that some inputs are more important than others.

#20 Bomb Bloke

    Hobbyist Coder

  • Moderators
  • 7,099 posts
  • LocationTasmania (AU)

Posted 17 October 2015 - 07:01 AM

Actually, scratch what I was saying. It's a load of bunk.

The key is that you shouldn't be having the NN play while it's training. Instead, you devise two other AIs, and have them play each other instead.

One plays perfectly, and should always win or draw - we'll call that AI PP. The other should simply play at random, without any consideration as to whether its moves are worthwhile or not. We'll call that AI R.

As the games progress, take each state of the board at the start of PP's turn, and use that as an input. Pass the state of the board after PP's turn as the expected output. You otherwise don't need to record anything about the games.

After a sufficient number of games have been simulated, you should be able to substitute PP with NN and it should continue to always win or draw. You may wish to occasionally substitute R with another instance of PP during training - it's important that NN learn how to deal with R, but it'll become a better player faster if it watches PP against PP every now and then. NN itself wouldn't make a good substitute for R, because it'll start shifting from R's behaviour to PP's behaviour, and as a result will be less likely to teach itself how to deal with "bad" moves performed by its opponent.

Both PP and R could be imitated by human players, but the number of matches they'd need to play would make that somewhat prohibitive. It's also important that every move NN is taught is a move that PP would make; you don't want to teach it "mistakes". Moves that aren't "perfect play" may win under certain circumstances, but that doesn't mean they should be encouraged.

PP's AI would be coded according to these rules:
  • There are three possible opening moves; side, corner, or middle. Everything else is a reflection/rotation of one of those.
  • Unless the opponent has already taken a corner before it can, PP should attempt the following:
    X| |   X| |   X| |X  X| |X
    -+-+-  -+-+-  -+-+-  -+-+-
     | |    | |    | |    | |X
    -+-+-  -+-+-  -+-+-  -+-+-
     | |    | |X   | |X   | |X
  • If the opponent has already taken a corner, PP should instead attempt the following:
     | |    |X|    |X| 
    -+-+-  -+-+-  -+-+-
     |X|    |X|    |X| 
    -+-+-  -+-+-  -+-+-
     | |    | |    |X| 
  • If PP's chosen pattern is blocked, then it should simply attempt to create lines of three, making use of whatever it's already placed on the board.
  • PP should stop its current tactic and attempt to block the opponent if the opponent would otherwise win on their next turn.
I'm fairly sure that's sufficient for perfect play.

Edited by Bomb Bloke, 17 October 2015 - 07:03 AM.






1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users