|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png) Viewing Message
|
|
|
| ``Re: Algorithm''
by Algeboy on 2008-01-04 10:52:09 |
|
| Victor is right that tic-tac-toe is a simple game and all the games can be enumerated, but there are still a lot of games. There actually is a little bit of math hidden in this that is fun to work out. (I made a chart once so I'm speaking from my own experience.) I wanted to do it without computers, it is more fun that way and teaches you something.
Moreover, it shows you how you might tackle a problem too big for brute force computer searches.
Things to keep in mind:
1. First choose a good way to encode a game with numbers. For instance, using 0,1,2 symbols in a 3 x 3 grid tell you have an upper bound of 3^9=19683 games. Clearly a computer can handle this but I've played tic-tac-tao and know the "best move" without having memorized all 19683 options. So there really is a simple algorithm hidden in there.
2. Many games are essentially equivalent because you can change the orientation and see that they are just permutations of one another. Taking this into account reduces the variablity. So try to right down an equivalence relation between two games. It is surprising how few combinations emerge after this.
3. I discovered it was easier to start from the end of the game and decode the ways I could get to that state. That is, there are many paths to get to the same conclusion but there really aren't that many final games. This is what thinking like math is like of course, work backwards. This meant I only had to consider games that could happen. (many "games" you can encode by a grid wont be actual games.)
4. Finally, if you play this game enough you soon realize that the best play always leads to a tie game. That is, it does not matter who starts, if both players play to win then they reach a tie. So one way to think of studying JUST the best plays is to start from the end of a tie game and remove plays until you see the pattern. (it turns out that in many cases there isn't just one "best" play but all you need is "one" best play to create an algorithm.)
In the end, instead of enumerating all possible plays, a huge number to humans, you only ONE way to make the best play to reach any one of the very few tie games. This is a human sized problem.
|
| | [ reply | up | top ] |
|
|
|
|
|
|
