Minimax

En teoria de jocs, 'minimax' és un método de decisió per a minimisar la pèrdua màxima esperada en jocs en adversari i en informació perfecta. Minimax és un algoritme recursivo.

El funcionament de minimax pot resumir-se en cóm elegir el millor moviment per a tu mateix suponent que el teu contrincant triarà el pijor per a tu.

Història

Encara que existixen evidències de que Charles Babbage ya havia treballat abans sobre una idea similar, va ser el matemàtic francés Émile Borel el primer en oferir en 1921 un tractament rigorós als jocs competitius i en estudiar les estratègies aplicables als jocs de suma zero. No obstant sol atribuir-se a John von Neumann el principal mèrit de la concepció del principi minimax, ya que va ser ell qui, en el seu artícul de 1928 «Zur Theorie der Gesellschaftsspiele» («Sobre la teoria dels jocs de societat») publicat en la revista Mathematische Annalen, va posar les bases de la moderna teoria de jocs i va provar el teorema fonamental del minimax, pel que es demostra que per a jocs de suma zero en Informació perfecta entre dos competidors existix una única solució òptima.

Teorema minimax

John von Neumann

John von Neumann és el creador de la teorema minimax, qui va donar la següent noció de lo que era un joc:

També va afirmar que:

La demostració a eixa afirmació es diu teoria minimax i sorgix en 1928.

Esta teorema establix que en els jocs bipersonales de suma zero, a on cada jugador coneix de bestreta l'estratègia del seu oponent i les seues conseqüències, existix una estratègia que permet a abdós jugadors minimisar la pèrdua màxima esperada. En particular, quan s'examina cada possible estratègia, un jugador deu considerar totes les respostes possibles del jugador adversari i la pèrdua màxima que pot carrejar. El jugador juga, llavors, en l'estratègia que resulta en la minimisació de la seua màxima pèrdua. Tal estratègia és cridada òptima per a abdós jugadors només en cas que els seus minimaxes siguen iguals (en valor absolut) i contraris (en signe). Si el valor comú és zero el joc es convertix en un sinsentido.

En els jocs de suma no nula, existix tant l'estratègia minimax com la maximin. La primera intenta minimisar el guany del rival, és dir, busca que el rival tinga el pijor resultat. La segona intenta maximizar el guany propi, o siga busca que el jugador obtinga el millor resultat.

Vore també

• poda alfa-beta
• negamax
• Montecarlo