Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2013-07-27 20:38:00

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 16,251
Website

How does Minimax search work?

?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Humanity is still kept intact. It remains within.' -Alokananda

Offline

#2 2013-07-27 20:46:53

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 85,338

Re: How does Minimax search work?

The algorithm for two player game to find the best move in a tree such as chess? Or, minimax approximation in curve fitting?


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

#3 2013-07-28 02:42:28

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 16,251
Website

Re: How does Minimax search work?

The one that is not for posting at the Computer Math section.


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Humanity is still kept intact. It remains within.' -Alokananda

Offline

#4 2013-07-28 02:44:04

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 85,338

Re: How does Minimax search work?

Then you are out of luck. I used to be able to program it quickly and in tight code but that was a long time ago. I am afraid I have forgotten almost all of it.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

#5 2013-07-28 02:48:29

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 16,251
Website

Re: How does Minimax search work?

OMG! What did you do with Minimax search?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Humanity is still kept intact. It remains within.' -Alokananda

Offline

#6 2013-07-28 02:57:07

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 85,338

Re: How does Minimax search work?

Seems I forgot everything about that and alpha beta pruning, razoring, singular extensions... I just remember the names now.

I do remember it is a way of pruning a tree. It was invented I think by the American genius Claude Shannon. He designed it for 2 player zero sum games.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

#7 2013-07-29 02:52:35

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 16,251
Website

Re: How does Minimax search work?

The algorithm for two player game to find the best move in a tree such as chess? Or, minimax approximation in curve fitting?

Which one are you talking about?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Humanity is still kept intact. It remains within.' -Alokananda

Offline

#8 2013-07-29 04:44:43

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 85,338

Re: How does Minimax search work?

The one you wanted, "The algorithm for two player game to find the best move in a tree such as chess."


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

#9 2013-07-29 13:50:45

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 16,251
Website

Re: How does Minimax search work?

oh. Did you know it?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Humanity is still kept intact. It remains within.' -Alokananda

Offline

#10 2013-07-29 15:28:16

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 85,338

Re: How does Minimax search work?

Programmed it on a TI - 92 with 256 k of ram. It was awfully slow but it worked.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

#11 2013-07-30 00:24:33

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,535

Re: How does Minimax search work?

I have used it before too. And I am also a bit rusty in it ... it is one of those coding algorithms you apply to a specific situation, and when it works you go "wow, cool", and then move on to the next bit of coding and forget about it afterwards.

Your game needs to be able to assign a score after each move, higher scores are better for you.

And then (sorry if I get this wrong), for each move you can make you imagine your opponent chooses their best move (your min score), and then you choose the best of those (max of the min scores). It is like choosing the "best of the worst".

So if you have 3 possible moves: A, B , C
* after move A your opponent can have 2 moves, scoring -3 and +2 (remember higher is better for you), so they will probably do the move with score -3 (worst for you),
* after move B your opponent can have 2 moves, scoring -9 and +7, so they will probably do the move with score -9
* after move C your opponent can have 2 moves, scoring -1 and +9, so they will probably do the move with score -1

Your best choice is move C (the max of the min scores)


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

#12 2013-07-30 01:48:42

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 16,251
Website

Re: How does Minimax search work?

Thanks. But isn't this something very obvious?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Humanity is still kept intact. It remains within.' -Alokananda

Offline

Board footer

Powered by FluxBB