Algoritmo de Reparto

[Gand-Alf]

Imaginemos un juego en que hay distintos bandos, por ejemplo el Here I Stand y no los queremos repartir de forma aleatoria, sino que cada jugador pueda escoger.

¿Cual sería el mejor método para que a cada jugador le tocara una facción entre sus preferencias?

Por ejemplo cada jugador podría hacer una lista en que pone en primer lugar la facción que más le interesa y en último la que menos:

Habsburgo
Francia
Inglaterra
Papado
Otomano
Reformista

Bien, un sistema podría ser que primero se intenta dar a cada jugador la primera opción que ha escogido y si no hay nadie más que haya escogido lo mismo, ya se le asigna. En caso de que dos jugadores empataran en primera opción, podría sortearse y luego intentar dar la segunda opción a los demás. Eso tiene un problema:

Imaginad que un solo jugador ha escogido Habsburgo como primera opción y nadie más la ha cogido pero ha puesto Francia como segunda opción y el resto de jugadores han puesto Francia como última. ¿No debería recibir ese jugador Francia? Y darle Habsburgo a alguien que lo haya cogido como segunda opción. Ya que en otro caso, Francia debería llevarla un jugador que la puso como última opción.

Supongo que es un tema de mucha complejidad pero me gustaría oir la voz de los expertos en estadística, combinatoria y programación.

¿Cual es la forma en que hay que repartir unos bandos para que todos queden bastante contentos con lo que les ha tocado?

[Wkr]

Programación lineal.

Este es un caso típico de Investigación Operativa (o de Operaciones)
http://es.wikipedia.org/wiki/Investigaci%C3%B3n_de_operaciones

Hay varios métodos para ello, posiblemente con aplicar un Simplex te valdría.
http://es.wikipedia.org/wiki/Algoritmo_s%C3%ADmplex

Solver:
http://www.simplexme.com/es/

[Gand-Alf]

¿Alguien me lo explica con marionetas?

A ver... creo que sería capaz de hacerlo. Supongo que todo se basa en dar unos valores, decidir en cuanto valoras tu que un jugador quede en cada posición y luego el algoritmo se encargará de encontrar la combinación en que salga un valor total más alto. ¿Lo he entendido bien?

[Maeglor]

¿Cual es la forma en que hay que repartir unos bandos para que todos queden bastante contentos con lo que les ha tocado?

El planteamiento no es del todo correcto, porque se puede dar el caso de que siempre tenga que quedar algún descontento del todo (con su última elección) si todos ponen por ejemplo el Papado en ultima opción. Sería más correcto decir 'maximizar el contento general'.


Y para maximizar hay que cuantificar. Un método simple sería asignar un valor numérico de modo inverso a la opción elegida (o sea si pones el Protestante como el que más quieres le asignas un 6, y si es el Habsburgo el que menos un 1) y tratar de maximizar ese número. Y a mí se me ocurre por la fuerza bruta, haciendo todas las combinaciones (que para eso están los ordenadores) y sumando el valor que salga y eligiendo al azar entre los empates. En el HIS estaríamos hablando de 6! = 720 combinaciones.

Si quieres afinar puedes decir que una última opción es todavía peor que un 1, por ejemplo un -1, y una primera todavía mejor que un 6, por ejemplo un 7. La solución puede variar pero el método es el mismo.

Supongo que lo que ha dicho Wkr de la programación lineal es eso: llevar un problema de la vida real a números y hallar la mejor solución, pero reconozco que me he perdido antes de entenderlo en condiciones.

[Ferris]

El HiS, ¿no os parece ya suficientemente largo? 

[Zorro]

Como ya señala Wkr, esos temas estan bastante estudiados, pero claro, para escoger bandos en un juego, igual no necesitas tanta potencia. Si es solo para eso, me da a mi que el metodo mas sencillo es decir las preferencias de cada uno

Siempre puedes buscar "metodos" chorrillas para sistematizarlo... rollo minijuegos, por ejemplo, que cada jugador, en ronda, diga una potencia que NO quiere llevar... cuando todos menos uno hayan dicho, por ejemplo, que no quieren llevar al papado, pues el que falta se lo queda, y se siguen diciendo.

Tambien puedes dar "puntos" de puja... cada jugador tiene X puntos, y se subastan los bandos. Si juegas varias partidas, pues puedes incluso despues de cada partyida dar X/5 puntos a cada jugador, que se suman a los que ya tuviera.

Y bueno, si dais mucha importancia a la elección de bandos, lo mejor sería un duelo a garrotazos.



Si alguien no quiere participar, pues seguro que no le importa demasiado el bando

Pero vamos, que si realmente es solo para elegir bando... un metodo tradicional, como "dejamos que el mas novato elija primero", "dejamos que el que perdio elija primero" o similar, debería ser mas que suficiente, no?

[Gand-Alf]

No si por métodos de repartir a mi se me ocurren cientos:

- Una competición por ver quien come más flanes.

- Jugar una partida de Here I Stand, en la que se determinará quien será el primero en escoger bando en una partida de Here I Stand.

- Meter a un pulpo en una pecera, poner 6 mejillones en distintas cajas con los dibujos de las facciones y que escoja en orden.

- Montar un debate teológico televisado acerca de las tesis de Ulrico Zwinglio. Los espectadores pueden mandar sms para votar quien creen que ha ganado el debate. El ganador escogerá facción.

- Jugar una partida de Here I Stand, en la que se determinará quien será el primero en escoger bando en una partida de Here I Stand, en la que se determinará quien será el primero en escoger bando en una partida de Here I Stand, en la que se determinará quien será el primero en escoger bando en una partida de Here I Stand... (riesgo de entrar en un bucle infinito).


Ahora bien, la gracia es dar con el sistema en que se obtiene una satisfacción óptima como matiza Maeglor (a eso me refería yo, logicamente si todos cogieran como última opción la misma facción, alguien debería jugar con la última opción que puso). En este caso sí es cierto que podría hacerse "a fuerza bruta". Se valoran las distintas posiciones y se intenta buscar cual es la posición o posiciones en que el valor global es más alto. Pero hay algoritmos para llegar a eso sin tener que desglosar todas las combinaciones. Lo que falta es entenderlos bien

[Maeglor]

Ahora bien, la gracia es dar con el sistema en que se obtiene una satisfacción óptima como matiza Maeglor (a eso me refería yo, logicamente si todos cogieran como última opción la misma facción, alguien debería jugar con la última opción que puso). En este caso sí es cierto que podría hacerse "a fuerza bruta". Se valoran las distintas posiciones y se intenta buscar cual es la posición o posiciones en que el valor global es más alto. Pero hay algoritmos para llegar a eso sin tener que desglosar todas las combinaciones. Lo que falta es entenderlos bien

Yo ayer me puse a jugar con esto y me hice una matriz de 6x6 con el número de eleccción a boleo como dije ayer, un 6 a la potencia más deseada, un 1 a la menos. Y lo que hacía era ir tachando los números bajos (primero el 1, luego el 2...) y viendo si eso dejaba primero elecciones posibles y si no volvía para atrás (que se pudieran elegir todos los paises por algún jugador) y después si dejaba alguna elección obligada, es decir que una potencia estuviera sólo con un jugador. Entonces asignaba esa o esas potencias y reducía el rango de la matriz y seguía tachando.

Salir salía y en poco tiempo porque con esas dimensiones se ve de un vistazo, y aunque no sería el 'mejor' método sí era uno muy aproximado que primaba eliminar las opciones menos deseadas.

[Bru]

Nada...ya se la manera de romper el bucle infinito ese

Se juegan 720 partidas de Here I Stand que son (creo) las combinaciones posibles que puede haber de elección de países.  Se hace la media de puntos de victoria y el que haya sacado más elige.

Lo bueno es que ya no se necesitará jugar la partida porque sea cual sea la elección se habrá jugado así que... con esa nos vale.

Por supuesto habrá que elegir un criterio para decidir el orden de esas 720 partidas... propongo una tirada de dados.

Je.

[winston smith]

Igual meto la pata, pero tendría ésto algo que ver con el algoritmo que se aplica en las mathtrades?? Quicir, si son 6 facciones ofrezco la/s q menos me interesen y hago una wishlist con la/s q deseo liderar?? O nada más lejos de la realidad?? De letras q es uno.

[negroscuro]

vosotros... teneis pesadillas por las noches?  
 

[JavideNuln-Beren]

Hola a Tod@s:

Yo he tenido esos problemas....

Pero lo he solucionado porque al final hay uno o dos jugadores que están dispuesto a jugar con cualquiera de las 6 potencias (frase típica: "la que nadie quiera"). Por contra también hay un par de jugadores que quiere una única potencia.

Al final me pueden quedar un par de tiradas con dados de 5 o 9 caras (que los hay).

Una recomendación: Reparte las potencias poco a poco; si dos jugadores quiere el Protestante, lanzas un dado y el que gana se convierte en Lutero, ahora solo te quedan 5 potencias para repartir entre 5 jugadores, 5! = 120 combinaciones.