Win a copy of TensorFlow 2.0 in Action 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 ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Paul Clapham
  • Bear Bibeault
  • Jeanne Boyarsky
Sheriffs:
  • Ron McLeod
  • Tim Cooke
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Jj Roberts
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • salvin francis
  • Scott Selikoff
  • fred rosenberger

Minimax and Tic Tac Toe

 
Greenhorn
Posts: 8
  • 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.
 
Marshal
Posts: 7791
536
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It seems we missed your thread. Apologies. Somebody potentially will have a look now that we bumped it
 
Rancher
Posts: 218
16
  • Mark post as helpful
  • send pies
  • 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.
 
when your children are suffering from your punishment, tell your them it will help them write good poetry when they are older. Like this tiny ad:
the value of filler advertising in 2020
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic