# linear programming

## Primary tabs

Defines:
linear programming problem, objective function, feasible region, feasible
Keywords:
linear programming
Synonym:
LP
Type of Math Object:
Topic
Major Section:
Reference

## Mathematics Subject Classification

### Algorithm

I need an urgent help on below mentioned problem. I need an algorithm to find out the best possible move.

Game of Tic-Tack-Toe is a well-known game. It is a simple board with 9 squares arranged as a three by three matrix. There are two players. One of them ticks the squares and the other crosses the squares. The aim of the two players is to place their symbol (tick or cross) on three consecutive squares, either horizontal, vertical or diagonal. The player who places his symbol in three consecutive squares wins the game. The players place their symbol on the board by taking turns. One symbol at a time. You have to place your symbol on an empty square. Initially (at the start of the game) all the squares are empty. Who makes the first move of the game is decided by the two players themselves. There is no rule governing this aspect of the game.

This problem is to find your best move, given a position of this board.

### Re: Algorithm

Tic tac toe is a simple game.

The computer can enumerate ALL variants. Just enumerate all variants.
--
Victor Porton - http://www.mathematics21.org
* Algebraic General Topology and Math Synthesis
* 21 Century Math Method (post axiomatic math logic)
* Category Theory - new concepts

### Re: Algorithm

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.