• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
  • Campbell Ritchie
  • Ron McLeod
  • Paul Clapham
  • Jeanne Boyarsky
  • Liutauras Vilda
  • Rob Spoor
  • Bear Bibeault
  • Tim Cooke
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Piet Souris
  • Frits Walraven
  • Himai Minh

Minimax and Tic Tac Toe

Posts: 9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello I am currently working with implementation of Minimax. I got a very small pseudocode and with that I am supposed to implement full game, I have no hints and no additional information. I cannot use any internet examples, all the code must be done on my own. However I found two good references to this topic:

Algorithms Explained – minimax and alpha-beta pruning
Minimax Algorithm in Game Theory | Set 3 (Tic-Tac-Toe AI – Finding optimal move)

First the pseudocode, do you think this is enough to code minimax function? Does this pseudocode provides enough information? I think it does not however the guy wants us to do it all with only this.

Function minimax(player, state):
    if state is terminal:
         return evaluation of state
    for each subState
         if player == MAX:
              return Maximum of minimax(MIN, subState)
         if not:
              return Minimum of minimax(MAX, subState)

Here the subState is when you expand all possible moves for current state, then you call for each one the function minimax recursively. The evaluation of state gives 1 if computer wins, -1 if human player wins and 0 if it's a tie. Based on this I got the following code, the problem is that CPU player isn't really that smart picking up the best move. I tried to do the pseudocode of the youtube video which I think is very clear. My app goes like this: A JFrame with a few panels, 9 buttons to pick a movement and an ActionListener that is checking for user input. Each time the player clicks a button to mark his/her position I call a method for the CPU movement, here the CPU is the maximizer so every time I call minimax I set isMaximizer to true.

Tic Tac Toe is a string array of size 9, I order elements ascending row by row. Then when I check if the state is terminal I do the following:

Finally when the user does the move it's computer's turn so I call:

I cannot see what I am doing wrong, I also ran the GeeksForGeeks code and I'm kinda understanding the algorithm but still can't see the problem. I hope you can help me out, greetings.
Posts: 7982
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
It seems we missed your thread. Apologies. Somebody potentially will have a look now that we bumped it
Posts: 242
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Difficult to say without stepping through the code and examining the states in a debugger (which is what I would recommend doing)

If I had to guess, the aplicarOperador method isn't generating all the states correctly. That method wasn't included in the post and it's not that easy to do.
Consider Paul's rocket mass heater.
    Bookmark Topic Watch Topic
  • New Topic