Minimax

Minimax tshiū ê huān-lē

An animated pedagogical example that attempts to be human-friendly by substituting initial infinite (or arbitrarily large) values for emptiness and by avoiding using the negamax coding simplifications.

Minimax (ián-sǹg-huat), ia̍h ki̍k-sió ki̍k-tāi ti̍t (Hàn-jī: 極小極大值), ū-tang-sî-á mā siá-tsò Minmax, MM hi̍k-tsiá an-tiám (鞍點; saddle point)), sī jîn-kang tì-huī, kuat-tshik lí-lūn, tsoo-ha̍p phok-ī lí-lūn, thóng-kè ha̍k í-ki̍p thiat-ha̍k tang-tiong sú-iōng ê kuat-tshik kui-tsik; iōng teh siōng-hāi ê tsōng-hóng (khó-lîng ū siōng-tuā ê sún-si) tsi-hā siōng-sió huà ê khó-lîng sún-sit. Tng-teh tshú-lí siu-ik ê sî-tsūn, Minimax mā hőng kiò-tsò "maximin" (tsuè-tuā ki̍k-sió ti̍t), ì-sù tio̍h-sī tsuè-tuā huà tsuè-sió siu-ik. Minimax thâu-á sī-tio̍h to-hong ī-tsiá lîng-hô (多方奕者零和; several-player zero-sum) hâm phok-ī lí-lūn (game theory) jî-lâi thê-tshut, hâm-kài ī-tsiá (player) tshái-tshú lûn-liû hîng-tōng kah tông-sî hîng-tōng nn̄g-tsióng tsōng-hóng. Āu--lâi mâ-hőng khok-tián kàu koh-khah ho̍k-tsa̍p ê phok-ī í-ki̍p tsûn-tsāi bô khak-tīng sìng ê it-puann kuat-tshik būn-tê.

Tsoo-ha̍p sài-kio̍k lí-lūn

Hi-gí-bé

Ē-bīn sī tshim-tōo siū-hān ê minimax ián-sǹg-huat tsi guī-tài-bé (hi-gí tîng-sik bé; pseudocode):

function minimax(node, depth, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, minimax(child, depth − 1, FALSE))
        return value
    else (* minimizing player *)
        value := +∞
        for each child of node do
            value := min(value, minimax(child, depth − 1, TRUE))
        return value

(* Initial call *)
minimax(origin, depth, TRUE)

Minimax hâm-sòo uî hio̍h tsiat-tiám (tsiong-tuan tsiat-tiám hâm siōng-tuā tshiau-tshuē tshim-tōo tshù ê tsiat-tiám ) thuân-huê tsi̍t-ê "khé-huat sik ê ti̍t" (heuristic value). Hui hio̍h tsiat-tiám ê ti̍t kè-sîng uì i-ê āu-tāi ê hio̍h tsiat-tiám. Tsit-ê "khé-huat sik ê ti̍t" (heuristic value) sī tsi̍t-ê hun-sòo, iōng-teh hîng-liông tsiat-tiám tuì siōng-tuā huà ê sńg-ī-tsiá ê iú-lī tîng-tōo. In-tshú, tuì siōng-tuā huà sńg-ī-tsiá iú-lī (pí-jû tit-tio̍h sìng-lī) ê tsiat-tiám tit-hun kuân-kuè tuì siōng-tsió huà sńg-ī tsiá iú-lī ê tsiat-tiám. Tsiong-tuan (sńg-ī kiat-sok) hio̍h tsiat-tiám ê khé-huat sik ti̍t (heuristic value) tuì-ìng siōng-tuā huà sńg-ī tsiá ê iânn, su hi̍k-tsiá pênn-tshiú. Tuì-tio̍h tsuè-tuā tshiau-tshuē tshim-tōo sóo-tsāi ê hui tsiong-tuan hio̍h tsiat-tiám, phîng-kóo hâm-sòo ē kóo-kè tsit-ê tsiat-tiám ê "khé-huat sik ti̍t" (heuristic value). Tsit-ê phîng-kóo ti̍t ê phín-tsit hâm tshiau-tshuē tshim-tōo kuat-tīng tsuè-tsiong minimax kiat-kó ê phín-tsit hâm tsún-khak sìng.

Minimax ián-sǹg-huat teh i-ê tîng-sū bé lāi-té kā nn̄g-ê ī-tsiá (tsuè-tuā huà ī-tsiá hâm tsue-sió huà ī-tsiá) hun-khui tshú-lí. Khiā-tī tsit-ê kuan-tshat $\ \max(a,b)=-\min(-a,-b)$, minimax ián-sǹg-huat sòo-siông ē-tàng kán-huà tsò negamax ián-sǹg-huat.

Tsham-ua̍t

• Alpha–beta pruning
• Expectiminimax
• Maxn algorithm
• [Computer chess
• Horizon effect
• Lesser of two evils principle
• Minimax Condorcet
• Regret (decision theory)
• Monte Carlo tree search
• Negamax
• Negascout
• Sion's minimax theorem
• Tit for Tat
• Transposition table
• [Wald's maximin model
• Gamma-minimax inference
• Reversi Champion
• Artificial intelligence in video games

Guā-pōo liân-kiat

Wiktionary

Khì Wiktionary chhâ
Minimax chit ê sû.

• "Minimax principle", Encyclopedia of Mathematics, EMS Press, 2001 
• "Mixed strategies". cut-the-knot.org. Curriculum: Games.  — A visualization applet
• "Maximin principle". Dictionary of Philosophical Terms and Names. goân-loē-iông tī 2006-03-07 hőng khó͘-pih. 
• "Minimax". Dictionary of Algorithms and Data Structures. US NIST.