Making a tic tac toe game difficult to win

Discussion in 'Java' started by shadow427, Nov 13, 2005.

  1. shadow427

    shadow427 Guest

    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;
    }
     
    shadow427, Nov 13, 2005
    #1
    1. Advertising

  2. shadow427

    Chris Smith Guest

    shadow427 <> wrote:
    > 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
     
    Chris Smith, Nov 13, 2005
    #2
    1. Advertising

  3. shadow427

    Guest

    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).
     
    , Nov 13, 2005
    #3
  4. shadow427

    shadow427 Guest

    Jean,
    I am not sure how to create the method to make it play optimally. Can
    you please help? Thanks so much!
     
    shadow427, Nov 13, 2005
    #4
  5. shadow427

    Patrick May Guest

    "shadow427" <> writes:
    > 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

    ------------------------------------------------------------------------
    S P Engineering, Inc. | The experts in large scale distributed OO
    | systems design and implementation.
    | (C++, Java, Common Lisp, Jini, CORBA, UML)
     
    Patrick May, Nov 13, 2005
    #5
  6. shadow427

    Stefan Ram Guest

    Patrick May <> writes:
    >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
     
    Stefan Ram, Nov 13, 2005
    #6
  7. shadow427

    Mickey Segal Guest

    "Stefan Ram" <-berlin.de> wrote in message
    news:-berlin.de...
    > 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.
     
    Mickey Segal, Nov 13, 2005
    #7
  8. shadow427

    Chris Smith Guest

    <> wrote:
    > 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
     
    Chris Smith, Nov 13, 2005
    #8
  9. "Chris Smith" <> wrote in message
    news:...
    > <> wrote:
    >> 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
    :)

    --
    LTP

    :)
     
    Luc The Perverse, Nov 13, 2005
    #9
  10. shadow427

    Roedy Green Guest

    On Sun, 13 Nov 2005 11:26:48 -0700, "Luc The Perverse"
    <> wrote, quoted or indirectly
    quoted someone who said :

    >
    >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.
    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Java custom programming, consulting and coaching.
     
    Roedy Green, Nov 13, 2005
    #10
  11. shadow427

    Guest

    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:

    >> Chess is a drawn game by default. A "perfect" player could
    >> not beat you unless you made a mistake.

    > 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
     
    , Nov 13, 2005
    #11
  12. shadow427

    zero Guest

    "Luc The Perverse" <> wrote in
    news:43778575$0$8335$:

    > "Chris Smith" <> wrote in message
    > news:...
    >> <> wrote:
    >>> 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
     
    zero, Nov 13, 2005
    #12
  13. "Roedy Green" <> wrote in
    message news:p...
    > On Sun, 13 Nov 2005 11:26:48 -0700, "Luc The Perverse"
    > <> wrote, quoted or indirectly
    > quoted someone who said :
    >
    >>
    >>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.


    I was referring to chess :)

    --
    LTP

    :)
     
    Luc The Perverse, Nov 13, 2005
    #13
  14. shadow427

    Chris Smith Guest

    zero <> wrote:
    > 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
     
    Chris Smith, Nov 13, 2005
    #14
  15. shadow427

    IchBin Guest

    shadow427 wrote:
    > 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-)
     
    IchBin, Nov 13, 2005
    #15
  16. shadow427

    Guest

    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
     
    , Nov 14, 2005
    #16
  17. wrote:

    > 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. ]
     
    Andrew Thompson, Nov 14, 2005
    #17
  18. shadow427

    Oliver Wong Guest

    "IchBin" <> wrote in message
    news:...
    > shadow427 wrote:
    >> 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.


    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
     
    Oliver Wong, Nov 15, 2005
    #18
  19. shadow427

    Guest

    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.
     
    , Nov 15, 2005
    #19
  20. shadow427

    Larry Coon Guest

    shadow427 wrote:
    >
    > 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
     
    Larry Coon, Nov 18, 2005
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ted Harvard

    I write Tic-Tac-Toe in Java

    Ted Harvard, Jun 20, 2004, in forum: Java
    Replies:
    9
    Views:
    6,282
    Dan Barnet
    Jul 8, 2004
  2. Replies:
    5
    Views:
    6,814
  3. tomakated

    Tic Tac Toe Board

    tomakated, Dec 8, 2004, in forum: C++
    Replies:
    3
    Views:
    517
    Jonathan Turkanis
    Dec 8, 2004
  4. tomakated
    Replies:
    9
    Views:
    393
    tomakated
    Dec 14, 2004
  5. Replies:
    14
    Views:
    2,651
Loading...

Share This Page