Теория игр — математическая дисциплина, рассматривающая моделирование действий игроков, которые имеют цель, заключающуюся в выбор оптимальных стратегий поведения в условиях конфликта. На Хабре эта тема уже освещалась, но сегодня мы поговорим о некоторых ее аспектах подробнее и рассмотрим примеры на Kotlin.
Так вот, стратегия – это совокупность правил, определяющих выбор варианта действий при каждом личном ходе в зависимости от сложившейся ситуации. Оптимальная стратегия игрока – стратегия, обеспечивающая наилучшее положение в данной игре, т.е. максимальный выигрыш. Если игра повторяется неоднократно и содержит, кроме личных, случайные ходы, то оптимальная стратегия обеспечивает максимальный средний выигрыш.
Задача теории игр – выявление оптимальных стратегий игроков. Основное предположение, исходя из которого находятся оптимальные стратегии, заключается в том, что противник (или противники) не менее разумен, чем сам игрок, и делает все для того, чтобы добиться своей цели. Расчет на разумного противника – лишь одна из потенциальных позиций в конфликте, но в теории игр именно она кладется в основу.
Существуют игры с природой в которых есть только один участник, максимизирующий свою прибыль. Игры с природой – математические модели, в которых выбор решения зависит об объективной действительности. Например, покупательский спрос, состояние природы и т.д. «Природа» – это обобщенное понятие не преследующего собственных целей противника. В таком случае для выбора оптимальной стратегии используется несколько критериев.
Различают два вида задач в играх с природой:
key
будем использовать для идентификации, а также при сравнении, а сравнение понадобится при реализации доминирования.import java.text.DecimalFormat
import java.text.NumberFormat
open class GameVector(name: String, values: List<Double>, key: Int = -1) : Comparable<GameVector> {
val name: String
val values: List<Double>
val key: Int
private val formatter:NumberFormat = DecimalFormat("#0.00")
init {
this.name = name;
this.values = values;
this.key = key;
}
public fun max(): Double? {
return values.max();
}
public fun min(): Double? {
return values.min();
}
override fun toString(): String{
return name + ": " + values
.map { v -> formatter.format(v) }
.reduce( {f1: String, f2: String -> "$f1 $f2"})
}
override fun compareTo(other: GameVector): Int {
var compare = 0
if (this.key == other.key){
return compare
}
var great = true
for (i in 0..this.values.lastIndex){
great = great && this.values[i] >= other.values[i]
}
if (great){
compare = 1
}else{
var less = true
for (i in 0..this.values.lastIndex){
less = less && this.values[i] <= other.values[i]
}
if (less){
compare = -1
}
}
return compare
}
}
open class GameMatrix(matrix: List<List<Double>>, alternativeNames: List<String>, natureStateNames: List<String>) {
val matrix: List<List<Double>>
val alternativeNames: List<String>
val natureStateNames: List<String>
val alternatives: List<GameVector>
val natureStates: List<GameVector>
init {
this.matrix = matrix;
this.alternativeNames = alternativeNames
this.natureStateNames = natureStateNames
var alts: MutableList<GameVector> = mutableListOf()
for (i in 0..matrix.lastIndex) {
val currAlternative = alternativeNames[i]
val gameVector = GameVector(currAlternative, matrix[i], i)
alts.add(gameVector)
}
alternatives = alts.toList()
var nss: MutableList<GameVector> = mutableListOf()
val lastIndex = matrix[0].lastIndex // нет провеврки на равенство длин всех строк, считаем что они равны
for (j in 0..lastIndex) {
val currState = natureStateNames[j]
var states: MutableList<Double> = mutableListOf()
for (i in 0..matrix.lastIndex) {
states.add(matrix[i][j])
}
val gameVector = GameVector(currState, states.toList(), j)
nss.add(gameVector)
}
natureStates = nss.toList()
}
open fun change (i : Int, j : Int, value : Double) : GameMatrix{
var mml = this.matrix.toMutableList()
var rowi = mml[i].toMutableList()
rowi.set(j, value)
mml.set(i, rowi)
return GameMatrix(mml.toList(), alternativeNames, natureStateNames)
}
open fun changeAlternativeName (i : Int, value : String) : GameMatrix{
var list = alternativeNames.toMutableList()
list.set(i, value)
return GameMatrix(matrix, list.toList(), natureStateNames)
}
open fun changeNatureStateName (j : Int, value : String) : GameMatrix{
var list = natureStateNames.toMutableList()
list.set(j, value)
return GameMatrix(matrix, alternativeNames, list.toList())
}
fun size() : Pair<Int, Int>{
return Pair(alternatives.size, natureStates.size)
}
override fun toString(): String {
return "Состояния природы:\n" +
natureStateNames.reduce { n1: String, n2: String -> "$n1;\n$n2" } +
"\nМатрица игры:\n" +
alternatives
.map { a: GameVector -> a.toString() }
.reduce { a1: String, a2: String -> "$a1;\n$a2" }
}
protected fun dominateSet(gvl: List<GameVector>, list: MutableList<String>, dvv: Int) : MutableSet<GameVector>{
var dSet: MutableSet<GameVector> = mutableSetOf()
for (gv in gvl){
for (gvv in gvl){
if (!dSet.contains(gv) && !dSet.contains(gvv)) {
if (gv.compareTo(gvv) == dvv) {
dSet.add(gv)
list.add("[$gvv] доминирует [$gv]")
}
}
}
}
return dSet
}
open fun newMatrix(dCol: MutableSet<GameVector>, dRow: MutableSet<GameVector>)
: GameMatrix{
var result: MutableList<MutableList<Double>> = mutableListOf()
var ralternativeNames: MutableList<String> = mutableListOf()
var rnatureStateNames: MutableList<String> = mutableListOf()
val dIndex = dCol.map { c -> c.key }.toList()
for (i in 0 .. natureStateNames.lastIndex){
if (!dIndex.contains(i)){
rnatureStateNames.add(natureStateNames[i])
}
}
for (gv in this.alternatives){
if (!dRow.contains(gv)){
var nr: MutableList<Double> = mutableListOf()
for (i in 0 .. gv.values.lastIndex){
if (!dIndex.contains(i)){
nr.add(gv.values[i])
}
}
result.add(nr)
ralternativeNames.add(gv.name)
}
}
val rlist = result.map { r -> r.toList() }.toList()
return GameMatrix(rlist, ralternativeNames.toList(), rnatureStateNames.toList())
}
fun dominateMatrix(): Pair<GameMatrix, List<String>>{
var list: MutableList<String> = mutableListOf()
var dCol: MutableSet<GameVector> = dominateSet(this.natureStates, list, 1)
var dRow: MutableSet<GameVector> = dominateSet(this.alternatives, list, -1)
val newMatrix = newMatrix(dCol, dRow)
var ddgm = Pair(newMatrix, list.toList())
val ret = iterate(ddgm, list)
return ret;
}
protected fun iterate(ddgm: Pair<GameMatrix, List<String>>, list: MutableList<String>)
: Pair<GameMatrix, List<String>>{
var dgm = this
var lddgm = ddgm
while (dgm.size() != lddgm.first.size()){
dgm = lddgm.first
list.addAll(lddgm.second)
lddgm = dgm.dominateMatrix()
}
return Pair(dgm,list.toList().distinct())
}
fun minClearPrice(): Double{
val map: List<Double> = this.alternatives.map { a -> a?.min() ?: 0.0 }
return map?.max() ?: 0.0
}
fun maxClearPrice(): Double{
val map: List<Double> = this.natureStates.map { a -> a?.max() ?: 0.0 }
return map?.min() ?: 0.0
}
fun existsClearStrategy() : Boolean{
return minClearPrice() >= maxClearPrice()
}
}
interface ICriteria {
fun optimum(): List<GameVector>
}
class WaldCriteria(gameMatrix : GameMatrix) : ICriteria {
val gameMatrix: GameMatrix
init{
this.gameMatrix = gameMatrix
}
override fun optimum(): List<GameVector> {
val mins = gameMatrix.alternatives.map { a -> Pair(a, a.min()) }
val max = mins.maxWith( Comparator { o1, o2 -> o1.second!!.compareTo(o2.second!!)})
return mins
.filter { m -> m.second == max!!.second }
.map { m -> m.first }
}
}
private fun matrix(): GameMatrix {
val alternativeNames: List<String> = listOf("Культура 1", "Культура 2", "Культура 3")
val natureStateNames: List<String> = listOf("Прохладное и дождливое", "Нормальное", "Жаркое и сухое")
val matrix: List<List<Double>> = listOf(
listOf(0.0, 2.0, 5.0),
listOf(2.0, 3.0, 1.0),
listOf(4.0, 3.0, -1.0)
)
val gm = GameMatrix(matrix, alternativeNames, natureStateNames)
return gm;
}
}
private fun testCriteria(gameMatrix: GameMatrix, criteria: ICriteria, name: String){
println(gameMatrix.toString())
val optimum = criteria.optimum()
println("$name. Оптимальная стратегия: ")
optimum.forEach { o -> println(o.toString()) }
}
@Test
fun testWaldCriteria() {
val matrix = matrix();
val criteria = WaldCriteria(matrix)
testCriteria(matrix, criteria, "Критерий Вальда")
}
criteria
.class WaldCriteria(gameMatrix : GameMatrix) : ICriteria {
val gameMatrix: GameMatrix
init{
this.gameMatrix = gameMatrix
}
override fun optimum(): List<GameVector> {
val mins = gameMatrix.alternatives.map { a -> Pair(a, a.min()) }
val max = mins.maxWith( Comparator { o1, o2 -> o1.second!!.compareTo(o2.second!!)})
return mins
.filter { m -> m.second == max!!.second }
.map { m -> m.first }
}
}
class PessimismCriteria(gameMatrix : GameMatrix) : ICriteria {
val gameMatrix: GameMatrix
init{
this.gameMatrix = gameMatrix
}
override fun optimum(): List<GameVector> {
val mins = gameMatrix.alternatives.map { a -> Pair(a, a.min()) }
val min = mins.minWith( Comparator { o1, o2 -> o1.second!!.compareTo(o2.second!!)})
return mins
.filter { m -> m.second == min!!.second }
.map { m -> m.first }
}
}
class SavageCriteria(gameMatrix: GameMatrix) : ICriteria {
val gameMatrix: GameMatrix
init {
this.gameMatrix = gameMatrix
}
fun GameMatrix.risk(): List<Pair<GameVector, Double?>> {
val maxStates = this.natureStates.map { n -> Pair(n, n.values.max()) }
.map { n -> n.first.key to n.second }.toMap()
var am: MutableList<Pair<GameVector, List<Double>>> = mutableListOf()
for (a in this.alternatives) {
var v: MutableList<Double> = mutableListOf()
for (i in 0..a.values.lastIndex) {
val mn = maxStates.get(i)
v.add(mn!! - a.values[i])
}
am.add(Pair(a, v.toList()))
}
return am.map { m -> Pair(m.first, m.second.max()) }
}
override fun optimum(): List<GameVector> {
val risk = gameMatrix.risk()
val minRisk = risk.minWith(Comparator { o1, o2 -> o1.second!!.compareTo(o2.second!!) })
return risk
.filter { r -> r.second == minRisk!!.second }
.map { m -> m.first }
}
}
class HurwitzCriteria(gameMatrix: GameMatrix, optimisticKoef: Double) : ICriteria {
val gameMatrix: GameMatrix
val optimisticKoef: Double
init {
this.gameMatrix = gameMatrix
this.optimisticKoef = optimisticKoef
}
inner class HurwitzParam(xmax: Double, xmin: Double, optXmax: Double){
val xmax: Double
val xmin: Double
val optXmax: Double
val value: Double
init{
this.xmax = xmax
this.xmin = xmin
this.optXmax = optXmax
value = xmax * optXmax + xmin * (1 - optXmax)
}
}
fun GameMatrix.getHurwitzParams(): List<Pair<GameVector, HurwitzParam>> {
return this.alternatives.map { a -> Pair(a, HurwitzParam(a.max()!!, a.min()!!, optimisticKoef)) }
}
override fun optimum(): List<GameVector> {
val hpar = gameMatrix.getHurwitzParams()
val maxHurw = hpar.maxWith(Comparator { o1, o2 -> o1.second.value.compareTo(o2.second.value) })
return hpar
.filter { r -> r.second == maxHurw!!.second }
.map { m -> m.first }
}
}
open class ProbabilityGameMatrix(matrix: List<List<Double>>, alternativeNames: List<String>,
natureStateNames: List<String>, probabilities: List<Double>) :
GameMatrix(matrix, alternativeNames, natureStateNames) {
val probabilities: List<Double>
init {
this.probabilities = probabilities;
}
override fun change (i : Int, j : Int, value : Double) : GameMatrix{
val cm = super.change(i, j, value)
return ProbabilityGameMatrix(cm.matrix, cm.alternativeNames, cm.natureStateNames, probabilities)
}
override fun changeAlternativeName (i : Int, value : String) : GameMatrix{
val cm = super.changeAlternativeName(i, value)
return ProbabilityGameMatrix(cm.matrix, cm.alternativeNames, cm.natureStateNames, probabilities)
}
override fun changeNatureStateName (j : Int, value : String) : GameMatrix{
val cm = super.changeNatureStateName(j, value)
return ProbabilityGameMatrix(cm.matrix, cm.alternativeNames, cm.natureStateNames, probabilities)
}
fun changeProbability (j : Int, value : Double) : GameMatrix{
var list = probabilities.toMutableList()
list.set(j, value)
return ProbabilityGameMatrix(matrix, alternativeNames, natureStateNames, list.toList())
}
override fun toString(): String {
var s = ""
val formatter: NumberFormat = DecimalFormat("#0.00")
for (i in 0 .. natureStateNames.lastIndex){
s += natureStateNames[i] + " = " + formatter.format(probabilities[i]) + "\n"
}
return "Состояния природы:\n" +
s +
"Матрица игры:\n" +
alternatives
.map { a: GameVector -> a.toString() }
.reduce { a1: String, a2: String -> "$a1;\n$a2" }
}
override fun newMatrix(dCol: MutableSet<GameVector>, dRow: MutableSet<GameVector>)
: GameMatrix{
var result: MutableList<MutableList<Double>> = mutableListOf()
var ralternativeNames: MutableList<String> = mutableListOf()
var rnatureStateNames: MutableList<String> = mutableListOf()
var rprobailities: MutableList<Double> = mutableListOf()
val dIndex = dCol.map { c -> c.key }.toList()
for (i in 0 .. natureStateNames.lastIndex){
if (!dIndex.contains(i)){
rnatureStateNames.add(natureStateNames[i])
}
}
for (i in 0 .. probabilities.lastIndex){
if (!dIndex.contains(i)){
rprobailities.add(probabilities[i])
}
}
for (gv in this.alternatives){
if (!dRow.contains(gv)){
var nr: MutableList<Double> = mutableListOf()
for (i in 0 .. gv.values.lastIndex){
if (!dIndex.contains(i)){
nr.add(gv.values[i])
}
}
result.add(nr)
ralternativeNames.add(gv.name)
}
}
val rlist = result.map { r -> r.toList() }.toList()
return ProbabilityGameMatrix(rlist, ralternativeNames.toList(), rnatureStateNames.toList(),
rprobailities.toList())
}
}
}
class BayesCriteria(gameMatrix: ProbabilityGameMatrix) : ICriteria {
val gameMatrix: ProbabilityGameMatrix
init {
this.gameMatrix = gameMatrix
}
fun ProbabilityGameMatrix.bayesProbability(): List<Pair<GameVector, Double?>> {
var am: MutableList<Pair<GameVector, Double>> = mutableListOf()
for (a in this.alternatives) {
var alprob: Double = 0.0
for (i in 0..a.values.lastIndex) {
alprob += a.values[i] * this.probabilities[i]
}
am.add(Pair(a, alprob))
}
return am.toList();
}
override fun optimum(): List<GameVector> {
val risk = gameMatrix.bayesProbability()
val maxBayes = risk.maxWith(Comparator { o1, o2 -> o1.second!!.compareTo(o2.second!!) })
return risk
.filter { r -> r.second == maxBayes!!.second }
.map { m -> m.first }
}
}
class LaplaceCriteria(gameMatrix: GameMatrix) : ICriteria {
val gameMatrix: GameMatrix
init {
this.gameMatrix = gameMatrix
}
fun GameMatrix.arithemicMean(): List<Pair<GameVector, Double>> {
return this.alternatives.map { m -> Pair(m, m.values.average()) }
}
override fun optimum(): List<GameVector> {
val risk = gameMatrix.arithemicMean()
val maxBayes = risk.maxWith(Comparator { o1, o2 -> o1.second.compareTo(o2.second) })
return risk
.filter { r -> r.second == maxBayes!!.second }
.map { m -> m.first }
}
}
class Solve(gamePriceObr: Double, solutions: List<Double>, names: List<String>) {
val gamePrice: Double
val gamePriceObr: Double
val solutions: List<Double>
val names: List<String>
private val formatter: NumberFormat = DecimalFormat("#0.00")
init{
this.gamePrice = 1 / gamePriceObr
this.gamePriceObr = gamePriceObr;
this.solutions = solutions
this.names = names
}
override fun toString(): String{
var s = "Цена игры: " + formatter.format(gamePrice) + "\n"
for (i in 0..solutions.lastIndex){
s += "$i) " + names[i] + " = " + formatter.format(solutions[i] / gamePriceObr) + "\n"
}
return s
}
fun itersect(matrix: GameMatrix): String{
var s = "Цена игры: " + formatter.format(gamePrice) + "\n"
for (j in 0..matrix.alternativeNames.lastIndex) {
var f = false
val a = matrix.alternativeNames[j]
for (i in 0..solutions.lastIndex) {
if (a.equals(names[i])) {
s += "$j) " + names[i] + " = " + formatter.format(solutions[i] / gamePriceObr) + "\n"
f = true
break
}
}
if (!f){
s += "$j) " + a + " = 0\n"
}
}
return s
}
}
open class Solver (gameMatrix: GameMatrix) {
val gameMatrix: GameMatrix
init{
this.gameMatrix = gameMatrix
}
fun solve(): Solve{
val goalf: List<Double> = gameMatrix.alternatives.map { a -> 1.0 }
val f = LinearObjectiveFunction(goalf.toDoubleArray(), 0.0)
val constraints = ArrayList<LinearConstraint>()
for (alt in gameMatrix.alternatives){
constraints.add(LinearConstraint(alt.values.toDoubleArray(), Relationship.LEQ, 1.0))
}
val solution = SimplexSolver().optimize(f, LinearConstraintSet(constraints), GoalType.MAXIMIZE,
NonNegativeConstraint(true))
val sl: List<Double> = solution.getPoint().toList()
val solve = Solve(solution.getValue(), sl, gameMatrix.alternativeNames)
return solve
}
}
val alternativeNames: List<String> = listOf("Культура 1", "Культура 2", "Культура 3")
val natureStateNames: List<String> =
listOf("Прохладное и дождливое", "Нормальное", "Жаркое и сухое", "Ветреное")
val matrix: List<List<Double>> = listOf(
listOf(2.0, 4.0, 8.0, 5.0),
listOf(6.0, 2.0, 4.0, 6.0),
listOf(3.0, 2.0, 5.0, 4.0)
)
val gm = GameMatrix(matrix, alternativeNames, natureStateNames)
val (dgm, list) = gm.dominateMatrix()
println(dgm.toString())
println(list.reduce({s1, s2 -> s1 + "\n" + s2}))
println()
val s: Solver = Solver(dgm)
val solve = s.solve()
println(solve)
К сожалению, не доступен сервер mySQL