4 Replies - 14603 Views - Last Post: 05 February 2009 - 04:09 AM Rate Topic: -----

#1 Decelo  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 03-February 09

Implementing the minimax algorithm into C++ code

Post icon  Posted 03 February 2009 - 02:55 PM

Hey all, new user here in need of some guidance!

I've recently been making a Tic Tac Toe game in C++ for learning purposes (I know I'm sooo original! =P). Anyways I've got the game sorted for 2 player mode however I want to go a step further implement some AI, however I want a version of this AI to be unbeatable, thus I did some googling and found out about the minimax algorithm.

I think I understand how it works; going through each combination of moves and then returning a number based on the outcome, in my case it would be 1 for a win, 0 for a draw and -1 for a loose. However I don't know where to start on putting this into C++ code I understand that I would need to use a recursive function (a function within a function?), but from there I get stuck.
I've looked at some examples of minimax in other languages but couldn't find an example of it in C++ so therefore didn't fully understand what was happening.

If anyone would be kind enough to point me in the right direction or some me some examples in C++ I would very much appreciate it.

Many thanks for your time!

Decelo =)

Is This A Good Question/Topic? 0
  • +

Replies To: Implementing the minimax algorithm into C++ code

#2 bodom658  Icon User is offline

  • Villiage Idiom
  • member icon

Reputation: 113
  • View blog
  • Posts: 1,123
  • Joined: 22-February 08

Re: Implementing the minimax algorithm into C++ code

Posted 03 February 2009 - 05:28 PM

recursive function (a function within a function?),

A recursive function is a function that calls itself.
Was This Post Helpful? 0
  • +
  • -

#3 Plus  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 41
  • View blog
  • Posts: 414
  • Joined: 24-November 08

Re: Implementing the minimax algorithm into C++ code

Posted 04 February 2009 - 06:06 AM

:: to make a game where computer is Stupid -> use Random
:: or computer is smart (AI),
:: a basic AI would consist the computer to do a special process
:: where the computer decide the better choice,

:: simple games doesn't need AI, because result are not meant
:: but other games like cards game and chess certainly need,
Was This Post Helpful? 0
  • +
  • -

#4 Decelo  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 03-February 09

Re: Implementing the minimax algorithm into C++ code

Posted 05 February 2009 - 02:09 AM

View PostPlus, on 4 Feb, 2009 - 05:06 AM, said:

:: to make a game where computer is Stupid -> use Random
:: or computer is smart (AI),
:: a basic AI would consist the computer to do a special process
:: where the computer decide the better choice,

:: simple games doesn't need AI, because result are not meant
:: but other games like cards game and chess certainly need,


Well I'm not quite sure I understand what your trying to say, that TicTacToe doesn't need any AI?

If your saying that you could just make the computer move randonly then that wouldn't work and would only win/draw by luck >.<
Was This Post Helpful? 0
  • +
  • -

#5 David W  Icon User is offline

  • DIC supporter
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,788
  • Joined: 20-September 08

Re: Implementing the minimax algorithm into C++ code

Posted 05 February 2009 - 04:09 AM

You might like to start with a simpler game, perhaps X's and O's where there are fewer combinations to consider ...

only 9 possible positions to consider
only 8 winning patterns
a win in at least 3 moves or at most 5?

A goes first, 9 choices, but is there a 'best' first choice?
B goes next, 8 choices, but ...
A goes next, 7 choices, but ...
B goes next, 6 choices? but perhaps only 1 real 'blocking' choice
A goes next, 5 choices? but perhaps only 1 real 'blocking' choice
Has A a winning pattern?
If yes done
else
B goes next, 4 choices? but ...
Has B a winning pattern?
if yes done
else
A goes next, 3 choices? but ...
Has A a winning pattern? Or is it a draw?
if yes done
else
B goes next 2, choices? but ...
Has B a winning pattern? Or is it a draw?
if yes done
else
A goes next, only 1 and the last choice
Has A a winning pattern? Or is it a draw?
Was This Post Helpful? 1

Page 1 of 1