Archive: 13 posts

---

I plan on making a perfect Tic-Tac-Toe AI that never loses. The objective of the game will be to make as many ties as you can, since you cannot win against him. I might need opinions about what to do to end game between these options -Timed game : you lose points for losing games and win points for ties -Timed game : you die after 3 mistakes or time ends and win points for ties -Survival game : you die after one mistake and win points for ties -Waves : you win points with ties, lose points by for losing games. Game ends after a preset number of games (or there could be lives) -Endless, stop when you are tired In timed games, you could also not lose points for mistakes, as you already lose time.

2011-02-17 00:16:00 Author: Unknown User

---

A strange game. The only winning move is not to play.

2011-02-17 00:28:00 Author: Ayneh Posts: 2454

---

i agree with ayneh, seems a little pointless. also i think making an unbeatable AI is beyond most gadders abilities. im sure i could make an AI that knows the rules of noughts and crosses, but making it decide where to go intelligently... i wouldnt know where to begin...

2011-02-17 00:35:00 Author: Skalio- Posts: 920

---

Yeah, it was just a random I dea I had when I saw a tic tac toe level with a dumb AI. I just read an article about how to never loose tic tac toe, but I guess the only way to make a perfect AI in lbp2 would be to program every different game, and it would be over 10 000... I'll just forget that...

2011-02-19 20:00:00 Author: Unknown User

---

i agree with ayneh, seems a little pointless. No, no, I wasn't saying it's pointless. It's a quote from the movie WarGames which pivottt's idea reminded me of. http://www.youtube.com/watch?v=NHWjlCaIrQo I just read an article about how to never loose tic tac toe, but I guess the only way to make a perfect AI in lbp2 would be to program every different game, and it would be over 10 000... You don't need to program every possible game. You just need to program a winning algorithm.

2011-02-19 20:49:00 Author: Ayneh Posts: 2454

---

You just need to program a winning algorithm Yeah, what she said. You only need to do some switches that are like "when player X's here, AI O's here." (Yes, I used X and O as a verb. Deal with it XD) But to make sure you don't lose, the player ALWAYS has to go first, as if you know what you're doing, you can always win if you go first, and always tie if you go second.

2011-03-03 23:27:00 Author: BloodShot9001 Posts: 116

---

Well this should not be too difficult. TicTacToe is unfortunatelly the game, where you can not loose if you kow what you are doing. :-/ So if two people knows the good strategy, it will be alway tie :-/ But it can drag some attention from people not aware of this. They can try to beat it anyway :-D

2011-03-04 09:15:00 Author: Agarwel Posts: 207

---

If you manage to make the input really speedy you'd have one great minigame going

2011-03-04 17:25:00 Author: ll_ye Posts: 236

---

If you manage to make the input really speedy you'd have one great minigame going Yeah, could be multiplayer, like that story-mode minigame where you have to press the right button matching the symbols... See which player can complete the most games against the "AI" before the timer ends... And if you're looking at timed modes you could take another cue from that level: instead of ending after so many failed tries, just make a failed game delay the start of the next one... Of course, who says the "AI" should always play perfectly? Obviously it's a very easy game to play successfully, but if the player's playing speed games, you could throw in a bad "AI" move here and there, and give the player a bonus if they successfully exploit it. Obligatory XKCD (http://xkcd.com/832/) A problem like this would be perfect for a finite state machine... I really must spend some time trying to figure out how to build one of those nicely...

2011-03-04 17:41:00 Author: tetsujin Posts: 187

---

i agree with ayneh, seems a little pointless. also i think making an unbeatable AI is beyond most gadders abilities. im sure i could make an AI that knows the rules of noughts and crosses, but making it decide where to go intelligently... i wouldnt know where to begin... You don't need to program every possible game. You just need to program a winning algorithm. The general approach to this kind of problem is to search through the possible move sequences, trying to find the one that gives you the best shot at winning. In a relatively complicated game like chess, you would need to pare down the search space, try to consider just the (apparently) best moves each player could perform at each turn (this is known as the "minimax" algorithm, because when calculating your own moves you look at the moves which maximize your advantage, while when considering the opponent's moves you consider mainly those that maximize their advantage (minimizing yours)) But Tic-Tac-Toe is such a small game, it's not worth writing an algorithm to solve it. You can just check the current board state and know where your reasonable moves are. One way you could do it is to look at the map of possible tic-tac-toe games (for instance, the XKCD I linked earlier) and look at what the cases are where going in a particular square is a valid, non-losing move - and try to set up a minimal set of logic gates that correctly identify that case. Alternately, as I suggested in my previous post, the whole game tree could be implemented as a finite state machine, and any time a move is made, it's reflected as a state transition. The logic at any given state is very simple (just output those states that are valid, non-losing moves) - the main challenge would be exhaustively covering all the cases. Another thing you can do to simplify the problem is rotate or flip the board. If the human player goes first, and they go in a corner: it doesn't matter which corner it was, you can treat the problem exactly the same if you rotate the AI's view of the board to match its search table. if you know what you're doing, you can always win if you go first, and always tie if you go second. Well, you can't always win if you go first if you can always tie if you go second... Either player can win if the other makes a mistake, otherwise, both players can force a tie. If pivottt's not going to implement this, maybe I will...

2011-03-04 18:20:00 Author: tetsujin Posts: 187

---

also i think making an unbeatable AI is beyond most gadders abilities. In the Tic Tac Toe it is easier than you might think. There are really just few possibel games. Bear min mind, that even if the first player can place his mark to 9 fields - it is technically just start of three different games - just on rotated board. You can use this to your advantage. Place AI on the invisible holoboard and use tag sensorz and tags to palce new pieces. Then after frist move, you just rotate this holo making it much easier for yourself. And if you will make the AI to tak ethe first turn (to the middle), then palyer can make just 2 moves. And actually then you can force him to play your game - he will eighter follow (block you) or loose. If the AI will take first turn - there are only 2 game sequences how to unfold the match. So this should not be so dificult to program by two sequencers. If the palyers will move first, than it might take a little big more sequencers. But it is also just a few possible matches. When I was younger and bored I actually try to draw all possibile games to paper just to see if there is winning strategy. I used just A5 paper and it was more than enough to draw all possible games. So as you can see - programing unbeatable AI should not be so difficult. Its just matter of patience. If you wont do it, maybe when I will be bored, I can try it :-D

2011-03-04 20:02:00 Author: Agarwel Posts: 207

---

What's Tic-Tac-Toe?

2011-03-04 20:24:00 Author: Unknown User

---

So I've been playing around with an implementation... If anybody else is doing the same, the Wikipedia page (http://en.wikipedia.org/wiki/Tic_Tac_Toe) has a very simple set of static rules for playing an optimal game: Make a winning play if one's available. Block an opponent's winning play if one exists Create a fork to win in 2 moves If the opponent has a chance for a fork, block it, either directly or by a forced play Play center if it's available. If the opponent has a corner, play the opposite one Else, play any corner Else, play any side. So there's no need to implement board flipping/rotation or a game tree of possible moves... In my early attempts at implementing these rules, I had a total of 18 wires running to each "rule handler" - 9 for where player 1 has played and 9 for where player 2 has played... Let me tell you, wiring up 18 wires to multiple things on a circuit board is no fun. I cut it down to 9 wires (using direction splitters to tell who played in a place) and that turned out to be much simpler. (Initially I hadn't wanted to go that route 'cause it seemed like it'd lead to a lot of redundant splitting - but I'll take that over the wire routing lag in create mode...) These were two separate posts - joined here. I don't think the text really reads nicely without that break, so I guess this is my way of reintroducing it... -------------------------- So I've been working on my implementation... The "Block a fork play" rule was the most complicated one so far: to calculate whether any given square wasn't a viable fork-blocker play, I had to test to see whether any of the opponent's viable fork plays didn't intersect that point... So the whole "direct fork blocker" takes in in almost the 3x3 grid of "opponent's fork plays", a the 3x3 grid of the current game state, and 8 cells showing which rows, columns, and diagonals are possible "forced plays" for the opponent. Each of the 9 outputs had to be computed from almost the enitre "fork map", between 2-4 of the "forced plays", and one of the "game state" wires... (I had initially implemented "direct fork blocker" as "if the opponent has exactly one fork play, play there" - but it's possible to block multiple forks simultaneously if they all overlap at some vacant square...) This means wiring up a circuit board with 26 inputs and 9 outputs, 13 + 4 * 11 + 4 * 12 + 9 = 114 wires total. After a fair number of wires were hooked up, connecting each additional wire took between 1-2 minutes. Do the math and, apparently, I must have spent close to a couple hours just connecting wires for this thing. I'm really hating the wiring layout lag issue right now... Half-second intervals of UI responsiveness broken up by much longer periods of non-responsiveness... But I think that was the worst of it. I have these four different play rules implemented, and it'll be relatively easy to implement the remainder (possibly as a single rule) - so I need to add some combining logic and then I'll have a working Tic-Tac-Toe player. Combining logic could be a little bit of a headache (each rule needs to be considered in order, so I need a combiner that takes the 3x3 output of the first rule if there's at least one play selected - otherwise it takes the 3x3 output of the second rule... And then just repeat, combining with the next rule, and next rule until everything's included...) - that means a circuit taking in 18 wires and putting out three. But each cell for the rule combiner's output will only need to take in three wires (A[x] OR (NOR(A) AND B[x]) : put NOR(A) somewhere on the board, and its result becomes the third wire into each rule...) so it shouldn't be nearly as bad as the other stuff... Plus a bit of logic for things like knowing when it's his turn, picking randomly from the favorable moves, etc... So far the work I've done takes about 1/8 of the thermo. I'm hoping the needs of the circuit don't grow too much as I'm finishing it up. I want to make this into a multiplayer level, decorate, include instructions, various embellishments, and so on... (EDIT): Got it working! It's a real bear to play against... It never screws up, but I do. So now I'm mostly working on turning it into a level that's (hopefully) fun to play...

2011-03-11 17:37:00 Author: tetsujin Posts: 187

Posts: 1077139    Threads: 69970    Members: 9661    Archive-Date: 2019-01-19

Aus dem Archiv wurden alle persönlichen Daten wie Name, Anschrift, Email etc. - aber auch sämtliche Inhalte wie z.B. persönliche Nachrichten - entfernt.
Die Nutzung dieser Webseite erfolgt ohne Speicherung personenbezogener Daten. Es werden keinerlei Cookies, Logs, 3rd-Party-Plugins etc. verwendet.