Win a copy of Zero to AI - A non-technical, hype-free guide to prospering in the AI era this week in the Artificial Intelligence and Machine Learning forum!
  • 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 all forums
this forum made possible by our volunteer staff, including ...
  • Campbell Ritchie
  • Liutauras Vilda
  • Paul Clapham
  • Bear Bibeault
  • Jeanne Boyarsky
  • Ron McLeod
  • Tim Cooke
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Jj Roberts
  • Stephan van Hulst
  • Carey Brown
  • salvin francis
  • Scott Selikoff
  • fred rosenberger

Minimax and Tic Tac Toe

Posts: 6
  • Mark post as helpful
  • send pies
  • 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.
Don't get me started about those stupid light bulbs.
    Bookmark Topic Watch Topic
  • New Topic