h0tk3y

p2: [A, B, C, D]; p3: [A, B, C, D]; result: [B, A, A, A]
p2: [A, B, C, D]; p3: [A, B, D, C]; result: [B, A, A, A]
p2: [A, B, C, D]; p3: [A, C, B, D]; result: [B, A, A, A]
p2: [A, B, C, D]; p3: [A, C, D, B]; result: [C, A, A, A]
p2: [A, B, C, D]; p3: [A, D, B, C]; result: [B, A, A, A]
p2: [A, B, C, D]; p3: [A, D, C, B]; result: [C, A, A, A]
p2: [A, B, C, D]; p3: [B, A, C, D]; result: [B, A, A, A]
p2: [A, B, C, D]; p3: [B, A, D, C]; result: [B, A, A, A]
p2: [A, B, C, D]; p3: [B, C, A, D]; result: [B, A, A, B]
p2: [A, B, C, D]; p3: [B, C, D, A]; result: [B, C, B, B]

h0tk3y

digraph S {
	node0 [label = "S", shape = box];
	node0 -> {node1, node6, node7}
	node1 [label = "S", shape = box];
	node1 -> {node2}
	node2 [label = "T"];
	node2 -> {node3, node5}
	node3 [label = "N"];
	node3 -> {node4}
	node4 [label = "a", shape = plaintext];

h0tk3y

Вопрос: что считать выигрышем? (кроме случая с деньгами)

Вводится понятие полезности и ставится вопрос, как в рамках полезности измерять выигрыш игроков.

Рассмотрим игру, похожую на покер. На текущем этапе есть возможность продолжить играть или спасовать. Если игрок пасует, то его выигрыш составляет -20. Если играем, то либо выигрываем, либо проигрываем, соответственно, +90 (1/3) и -60 (2/3). Самое простое решение -- посчитать матожидание.

90 * 1/3 - 60 * 2/3 = -10

-10 -- явно больше, чем -20, матожидание выигрыша у варианта "играть" выше, логично предположить, что в среднем и на большой дистанции это выгоднее.

h0tk3y

Сегодня посмотрим, как задача ЛП используется в ТИ.

Была теорема Фон Неймана о том, что в смешанных стратегиях седловая точка есть всегда.

max {x} min {y} xAy = min {y} max {x} xAy = v

Посмотрим, как свести игру к задаче линейного программирования.

О двойственных задачах

h0tk3y

Динамические игры

    Отличаются от статических ("камень-ножницы-бумага").
    
    Пример. Выбор градоначальника, четыре кандидата -- A, B, C, D.
    Есть три коммуны, и в силу традиций они делают выбор по очереди.
    Сначала представители первой вычёркивают одного из кандидатов, потом второй, потом третьей, оставшийся кандидат считается выбранным.
    У каждой коммуны есть предпочтения:
    
    I   II   III

h0tk3y

import java.util.*
import kotlin.system.measureTimeMillis

fun main(args: Array<String>) {
    val nTests = 20000
    val testLength = 10000

    val random = Random()

h0tk3y

import kotlin.system.measureTimeMillis

class Matrix<T>(val items: Array<Array<T>>) {
    val rows: Int get() = items.size
    val cols: Int get() = items.size
    operator fun get(i: Int, j: Int): T = items[i][j]
}

data class MutableCell<T>(var i: Int, var j: Int, var value: T)

h0tk3y

    @Test
    fun test10() {
        """\x.x""" shouldBeNormalFor
                """(\f.\x.f (f x)) (\f.\x.f (f x)) (\f.\x.f (f x)) (\f.\x.f (f x)) (\f.\x.f (f x)) (\f.\x.f (f x))"""
    }

h0tk3y

fun fibonacci(n) {
    fibI, fibPrev = 1, 1
    for (i 3..n)
        fibPrev, fibI = fibI, fibPrev + fibI
    fibI
}

from, to = 1, 30
from, x, y, z = fibonacci(5)

h0tk3y

fun main(args: Array<String>) {
    val arrayInt: Any = Array(1) { 123 }

    val bytes = ByteArrayOutputStream()
    val o = ObjectOutputStream(bytes)
    o.writeObject(arrayInt)

    val i = ObjectInputStream(bytes.toByteArray().inputStream())
    val result = i.readObject() as Array<Int>