Making a tic tac toe game difficult to win

[shadow427]

I have a fully fuctional java tic tac toe game i created. I have it
now so that the human player can play against a computer player,
however it is too easy to win. The computer player always chooses the
last open space on the board and then goes up to the first space, I
don't know how to make it so that the computer player either always
beats or ties the human player. Basically I need to make the computer
player smarter. Below is the code any help would be greatly
appreciated.


public class TicTacToeBoard {
//data fields
char[][] ticTacToe = new char[3][3];

//constructor
public TicTacToeBoard(){
for (int i=0; i < ticTacToe.length; i++){
for (int j=0; j < ticTacToe.length; j++){
ticTacToe[j]='_';
}
}
}

//set the position on the board to the indicated symbol
public void makeMove(int row, int col, char symbol){
if(ticTacToe[row][col] == '_'){
ticTacToe[row][col] = symbol;
} else {
JOptionPane.showMessageDialog(null, "Illegal Move - Lose a
turn");
}
}

//provide logic for computer to choose its next move
public int[] chooseMove(char symbol){
int[] move = new int[2];
int blockRow = 0;
int blockCol = 0;
int progressRow = 0;
int progressCol = 0;

//THIS IS WHERE IM STUCK
for (int i=0; i < ticTacToe.length; i++){
for (int j=0; j < ticTacToe.length; j++){
if (ticTacToe[j] == '_'){
progressRow = i;
progressCol = j;
} else if (ticTacToe[j] != symbol){ //my opponent has it

} else { //it is mine, see if space around it

}
}
}

if(blockRow != 0 || blockCol != 0){
move[0] = blockRow;
move[1] = blockCol;
} else {
move[0] = progressRow;
move[1] = progressCol;
}
return move;
}

 

[Chris Smith]

I have a fully fuctional java tic tac toe game i created. I have it
now so that the human player can play against a computer player,
however it is too easy to win. The computer player always chooses the
last open space on the board and then goes up to the first space, I
don't know how to make it so that the computer player either always
beats or ties the human player. Basically I need to make the computer
player smarter.

You have too options:

1. Attempt to come up with some game-specific intelligence. For
example, in tic-tac-toe, you might program these rules:

- If the computer player has two symbols in a row, it MUST play
the remaining square to win the game.

- If the human player has two symbols in a row, the computer
MUST play the remaining square to prevent the win.

- Given a choice, it's better to play in the center than elsewhere.
It's also better to play in a corner than on a side.

2. Or, you can program general forethought. Do a google search for
"minimax". There are also optimizations such as alpha-beta, scout,
etc... but you really don't need them for a game as trivial as your
basic tic-tac-toe project.

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[jeanlutrin]

Tic-tac-toe is a turn based game including a board, "pieces" and
two players. Just like chess. Just like chess, there are three
possible outcomes if both players play optimally:

1. player A wins
2. player B wins
3. neither A nor B wins

In the case of Tic-tac-toe, which has been "solved", we know that it'
choice three: neither A nor B wins and, it this case, it is called a
draw.

In the case of chess, "we don't know". We know that it's one of those
three possible outcomes, but we can't tell which one (and depending
on the rules, "neither A nor B wins" is not necessarely a draw [it can
be an "infinite" game], but I disgress).

Whatever, if you really want your computer opponent to play Tic-tac
optimally, he'll never make a mistake and hence he'll never lose. The
human player will probably sometimes make a mistake and hence
sometimes loose (but never win).

Is that what you want?

If that's what you want, it's very simple: you write a method that
plays optimally (for each player, not just for "your" computer).
This can be done very simply using recursivity (at least if you're
comfortable with recursivity).

However, to make it less "boring", you could add some ramdoness:
make the computer play optimally only 80% of the time, so the
human player at least has some chance to sometimes win the game.

If you can't manage to write the recursive method that plays
optimally every time, I'll gladly do it for you.

See you soon on c.l.j.p.,

Jean


P.S : another game that has been solved is "6x7" ("Puissance 4" in
French, where you have to align 4 pieces in a grid made of 42 spots).

 

[shadow427]

Jean,
I am not sure how to create the method to make it play optimally. Can
you please help? Thanks so much!

 

[Patrick May]

I am not sure how to create the method to make it play optimally.
Can you please help? Thanks so much!

Tic-tac-toe is trivial enough that you can pre-compute all
possible games and do a table lookup to select a move that leads to a
win or, at worst, a draw. If you note the rotational symmetry of the
board, you can reduce the size of the lookup table significantly.

Alternatively, look up "alpha-beta pruning" for another approach.

Regards,

Patrick

 

[Stefan Ram]

Tic-tac-toe is trivial enough that you can pre-compute all
possible games and do a table lookup to select a move that
leads to a win or, at worst, a draw.

Here is tic-tac-toe written in pure HTML:

http://www.geocities.com/flo_kreidler/tictactoe.html

 

[Mickey Segal]

Here is tic-tac-toe written in pure HTML:

http://www.geocities.com/flo_kreidler/tictactoe.html

There was a version of Tic Tac Toe that would never lose impleneted on the
HP67 programmable calculator. The HP67 had 224 lines of machine language as
the maximum for programs.

 

[Chris Smith]

In the case of chess, "we don't know". We know that it's one of those
three possible outcomes, but we can't tell which one (and depending
on the rules, "neither A nor B wins" is not necessarely a draw [it can
be an "infinite" game], but I disgress).

Are you sure of this? I have always been under the impression that
there exist proofs that the game theoretic value of chess, like that of
tic-tac-toe, is zero (that is, given perfect play, the game will result
in a draw). I can't find any reference to this fact now, though.

It's definitely the case that no player may force a game to continue
indefinitely without cooperation from the other player; that's a trivial
consequence of the rules. So, the infinite game outcome is not
possibility.

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[Luc The Perverse]

In the case of chess, "we don't know". We know that it's one of those
three possible outcomes, but we can't tell which one (and depending
on the rules, "neither A nor B wins" is not necessarely a draw [it can
be an "infinite" game], but I disgress).

Are you sure of this? I have always been under the impression that
there exist proofs that the game theoretic value of chess, like that of
tic-tac-toe, is zero (that is, given perfect play, the game will result
in a draw). I can't find any reference to this fact now, though.

It's definitely the case that no player may force a game to continue
indefinitely without cooperation from the other player; that's a trivial
consequence of the rules. So, the infinite game outcome is not
possibility.

If your AI is too stupid though, it could easily result in an infinite game

 

[Roedy Green]

If your AI is too stupid though, it could easily result in an infinite game

there are only 9 squares, so at most a game has 9 moves.

 

[jeanlutrin]

Hi Chris,

I'm pretty sure of this. There have been many controversies
regarding this, and many approximative (and wrong)
traductions of a very important text on the subject (by
Zermelo in 1913).

People mis-translated his writing concluding that it was
always possible, for both players, to force a draw in chess.
Which is wrong (I *may* be true, but we don't know it "yet").

Basically (I'm quoting here):

Zermelo DID prove that either white has a winning
position, black has a winning position, or neither
does, that is, both players can stave off defeat
indefinitely (because he was ignoring the xxx move
rule). It's in the penultimate paragraph of the proof.
It's just that, as Schwalbe and Walker emphasize,
this wasn't his main concern; he was more interested
in putting a bound on the number of moves
it takes to win GIVEN that someone has a winning position.

and another quoting:

No. This is an entirely open question. My guess is that a "perfect" game
of chess is a draw with KRP vs. KR (ie White has a material advantage
but can't force a win). But that is only a guess. The simple fact is that
we don't know, and never will know (the problem size is way, way, way,
way, way beyond knowing) the value of a "perfect" game of chess.

Today, that's where things are at: we don't know the value of a
perfect game of chess.

Regarding the "infinite game" only possible if both player agree: it
would not turn a loosing position into a winning one and if both
player had to play optimally (because they want to play a perfect
game), then if playing "infinitely" is the only way not too lose, then
it's not that "they agree", it's just that they *have* to play
indefinitely not too loose the game (I'm talking about when the
rules are "simplified" and allow this).

So it's really: white wins, black wins or neither black nor withe wins
(which may, or may not, be considered a draw).

Maybe advances in mathematics (is P == NP ? or science (quantum
cryptography ? no idea...) will one day solve the chess game.



Talk to you soon on c.l.j.p.,

Jean

 

[zero]

In the case of chess, "we don't know". We know that it's one of
those three possible outcomes, but we can't tell which one (and
depending on the rules, "neither A nor B wins" is not necessarely a
draw [it can be an "infinite" game], but I disgress).

Are you sure of this? I have always been under the impression that
there exist proofs that the game theoretic value of chess, like that
of tic-tac-toe, is zero (that is, given perfect play, the game will
result in a draw). I can't find any reference to this fact now,
though.

It's definitely the case that no player may force a game to continue
indefinitely without cooperation from the other player; that's a
trivial consequence of the rules. So, the infinite game outcome is
not possibility.

If your AI is too stupid though, it could easily result in an infinite
game

Not if the rules are implemented correctly. The 3 times repitition(1) rule
and the 50-move(2) rule were devised specifically to avoid infinate games.

(1) the game is drawn if the exact same position has been reached 3 times
(2) if there have been 50 consecutive moves without a pawn push and without
check, the game is drawn

 

[Luc The Perverse]

there are only 9 squares, so at most a game has 9 moves.

I was referring to chess

 

[Chris Smith]

Not if the rules are implemented correctly. The 3 times repitition(1) rule
and the 50-move(2) rule were devised specifically to avoid infinate games.

Or more accurately, they were devised to avoid necessary infinite games.
Players may choose to force a draw in those situations, and the other is
required to accept. However, if both players continue playing, they may
do so. The only situation in which a draw is required by the rules is
if neither player has enough pieces to reach checkmate even if the other
player played the WORST possible move at every choice.

Not that this is particularly relevant.

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[IchBin]

I have a fully fuctional java tic tac toe game i created. I have it
now so that the human player can play against a computer player,
however it is too easy to win. The computer player always chooses the
last open space on the board and then goes up to the first space, I
don't know how to make it so that the computer player either always
beats or ties the human player. Basically I need to make the computer
player smarter. Below is the code any help would be greatly
appreciated.

There is a demo program for TicTacToe on any of the JDK distributions.

For me ..\jdk1.5.0_05\demo\applets\TicTacToe

--

Thanks in Advance...
IchBin, Pocono Lake, Pa, USA
http://weconsultants.servebeer.com/JHackerAppManager
__________________________________________________________________________

'If there is one, Knowledge is the "Fountain of Youth"'
-William E. Taylor, Regular Guy (1952-)

 

[clarke.jonathan]

Anyone see "Wargames". Interesting film about Biothermalnuclear war.
oh and tic tac toe. The computer can not be beaten. You could proove
it very simply by setting the computer to play against itself at 100%
optimality,

Regards

 

[Andrew Thompson]

Anyone see "Wargames". Interesting film about Biothermalnuclear war.

Apparently not interesting enough for you to notice there was
no 'biologocal' element to those thermonuclear weapons. ;-)

'bioweapons' only came back into 'fashion' relatively recently.
[ Probably mostly as a result of the ever rising paranoia/pressure
against thermonuclear weapons. ]

 

[Oliver Wong]

The easiest solution is probably to:

1) Figure out the optimal strategy for tic tac toe.
2) Hard-code the optimal strategy into your computer opponent.
3) ... ?
4) Profit.

- Oliver

 

[mrandywarner]

Yeah, your computer basically has three priorities for it's moves, you
just have to make it smart enough to realize which situation it's in.

1. If the computer can win on this move.
2. The player will win on their next move unless the computer blocks
3. Each open space has a value, choose the most best one.

 

[Larry Coon]

I have a fully fuctional java tic tac toe game i created. I have it
now so that the human player can play against a computer player,
however it is too easy to win. The computer player always chooses the
last open space on the board and then goes up to the first space, I
don't know how to make it so that the computer player either always
beats or ties the human player. Basically I need to make the computer
player smarter. Below is the code any help would be greatly
appreciated.

As others have said, the general approach to this type of problem
involves the Minimax algorithm or one of its variants -- although
it can be argued that Tic-Tac-Toe is so small that Minimax is
overkill. Still, it's useful to understand how Minimax works even
if it is overkill here.

I wrote a TTT program some time ago that allowed the user to switch
between "easy," "medium" and "hard" engines. The "hard" engine
used minimax (and since it exhaustively searches the game tree,
it could not be beaten). Below is the code for the "hard" engine.
I didn't bother including the supporting classes -- you should be
able to understand the algorithm by reading what's here, without
having detailed knowledge of classes like TTTPosition.

Note that this solution is effective, but the code was quickly
written and is rather inelegant. The first improvement would be to
use negamax rather than minimax, which eliminates the "if X do this
but if O do that" stuff.

package ttt;

import java.util.*;

public class TTTEngineHard extends TTTEngine {
public int eval(TTTPosition position) {
int bestPos = 0;
char turn = position.getTurn();
int bestVal = (turn == X ? -1 : 1);

for (int i = 0; i < 9; i++) {
if (position.isEmpty(i)) {
TTTPosition newPos = new TTTPosition(position);
newPos.putSquare(i);
int value = miniMax(newPos);
if ((turn == X && value > bestVal) || (turn == O && value <
bestVal)) {
bestVal = value;
bestPos = i;
}
}
}

return bestPos;
}

private int miniMax(TTTPosition position) {
int staticEval = evaluate(position);

if (staticEval != 0) return staticEval;

ArrayList successors = getSuccessors(position);

if (successors.isEmpty()) return 0;

int turn = position.getTurn();
int best = (turn == X ? -1 : 1);
ListIterator i = successors.listIterator();
while (i.hasNext()) {
TTTPosition newPos = (TTTPosition) i.next();

int value = miniMax(newPos);

if ((turn == X && value > best) ||
(turn == O && value < best))
best = value;
}

return best;
}

private ArrayList getSuccessors(TTTPosition position) {
ArrayList arrayList = new ArrayList();

for (int i = 0; i < 9; i++) {
if (position.isEmpty(i)) {
TTTPosition newPosition = new TTTPosition(position);
newPosition.putSquare(i);
arrayList.add(newPosition);
}
}

return arrayList;
}

private int evaluate(TTTPosition position) {
TTTWinResult winResult = position.checkForWinner();

if (winResult == null) return 0;

return (position.getSquare(winResult.getStartSquare()) == X ? 1 :
-1);
}
}


Larry Coon
University of California