|
|
| Line 1: |
Line 1: |
| local rational = require( "Module:Rational" )
| |
| local yesno = require( "Module:Yesno" )
| |
| local G = require( "Module:G" )
| |
|
| |
|
| local T_NUMBER = 0
| |
| local T_STRING = 1
| |
| local T_SYMBOL = 2
| |
| local T_LBRACE = 3
| |
| local T_RBRACE = 4
| |
| local T_COMMA = 5
| |
| local T_EOF = 6
| |
|
| |
| local p = {}
| |
|
| |
| -- NFG parsing based on https://github.com/gambitproject/gambit/blob/master/library/src/file.cc
| |
|
| |
| p._nfgLexer = function(nfg)
| |
| local i = 1
| |
| local line = 1
| |
| local len = string.len( nfg )
| |
| local fail = function (reason)
| |
| if reason == nil then reason = "Invalid NFG syntax" end
| |
| error(reason .. " at line " .. line
| |
| .. "\nc=" .. string.sub( nfg, i, i )
| |
| .. " around=" .. string.sub(nfg, i-5, i+5))
| |
| end
| |
| local currToken = nil
| |
| local nextToken = nil
| |
| local prevToken = nil
| |
| local step = function ()
| |
| -- Consume any space chars
| |
| local _, r, spaces = string.find( nfg, "(%s+)", i )
| |
| if r ~= nil then
| |
| i = r+1
| |
| for space in string.gmatch( spaces, "\n" ) do
| |
| line = line+1
| |
| end
| |
| end
| |
|
| |
| -- End of string
| |
| if i > len then return { T_EOF, "" } end
| |
|
| |
| local c = string.sub( nfg, i, i )
| |
| if c == "{" then
| |
| i = i+1
| |
| return { T_LBRACE, c }
| |
| elseif c == "}" then
| |
| i = i+1
| |
| return { T_RBRACE, c }
| |
| elseif c == "," then
| |
| i = i+1
| |
| return { T_COMMA, c }
| |
| elseif string.match(c, "%d") or c == "-" or c == "+" or c == "." then
| |
| -- Number
| |
| local _, r = string.find( nfg, "^[-+]?%d*", i )
| |
| if r == nil then
| |
| fail("Invalid number")
| |
| end
| |
|
| |
| if string.sub( nfg, r+1, r+1 ) == "." then
| |
| local p, q = string.find( nfg, "^%d+", r+2 )
| |
| if p == nil then
| |
| fail("Decimal with no digits")
| |
| end
| |
| r = q
| |
| elseif ((c == "-" or c == "+") and i == r) then
| |
| fail("Sign with no number")
| |
| end
| |
|
| |
| if string.match( nfg, "^[eE]", r+1 ) then
| |
| local p, q = string.find( nfg, "^%d+", r+2 )
| |
| if p == nil then
| |
| fail("Invalid exponent")
| |
| end
| |
| r = q
| |
| end
| |
|
| |
| if string.sub( nfg, r+1, r+1 ) == "/" then
| |
| local p, q = string.find( nfg, "^%d+", r+2 )
| |
| if p == nil then
| |
| fail("Invalid quotient")
| |
| end
| |
| r = q
| |
| end
| |
|
| |
| local ret = string.sub( nfg, i, r )
| |
| i = r+1
| |
| return { T_NUMBER, ret }
| |
| elseif c == '"' then
| |
| -- String
| |
| if string.sub( nfg, i+1, i+1 ) == '"' then
| |
| i = i+2
| |
| return { T_STRING, "" }
| |
| else
| |
| local l, r = string.find( nfg, '^".-[^\\]"', i)
| |
| if l == nil then
| |
| fail("Invalid string")
| |
| end
| |
| i = r+1
| |
| return { T_STRING, string.sub(nfg, l+1, r-1):gsub('\\"', '"') }
| |
| end
| |
| else
| |
| -- Symbol, consume all non-space chars
| |
| local l, r = string.find( nfg, "^%S+", i )
| |
| if r ~= nil then
| |
| i = r+1
| |
| return { T_SYMBOL, string.sub( nfg, l, r ) }
| |
| else
| |
| return { T_EOF, "" }
| |
| end
| |
| end
| |
| end
| |
|
| |
| return {
| |
| peek = function ()
| |
| if nextToken == nil then
| |
| nextToken = step()
| |
| end
| |
| return nextToken
| |
| end,
| |
| next = function ()
| |
| if currToken ~= nil then
| |
| prevToken = currToken
| |
| end
| |
| if nextToken ~= nil then
| |
| currToken = nextToken
| |
| nextToken = nil
| |
| else
| |
| currToken = step()
| |
| end
| |
| return currToken
| |
| end,
| |
| curr = function () return currToken end,
| |
| prev = function () return prevToken end,
| |
| }
| |
| end
| |
|
| |
| p._ratParse = function (s)
| |
| local r = mw.text.split(s, "/")
| |
| n = r[1]+0
| |
| d = (r[2] ~= nil and r[2] ~= 0) and (r[2]+0) or 1
| |
| return rational(n,d)
| |
| end
| |
|
| |
| p._nfgParse = function (nfg)
| |
| local lexer = p._nfgLexer(nfg)
| |
| local fail = function (reason)
| |
| if reason == nil then reason = "Invalid NFG" end
| |
| curr = lexer.curr()
| |
| error(reason .. " on token type " .. curr[1] .. ": " .. curr[2])
| |
| end
| |
| local game = {
| |
| players = {},
| |
| outcomes = {},
| |
| map = {},
| |
| strats = {},
| |
| comment = "",
| |
| }
| |
| local token
| |
|
| |
| -- Heading
| |
| token = lexer.next()
| |
| if token[1] ~= T_SYMBOL or token[2] ~= "NFG" then
| |
| fail("NFG missing from start of NFG")
| |
| end
| |
| token = lexer.next()
| |
| if token[1] ~= T_NUMBER or token[2] ~= "1" then
| |
| fail("NFG version 1 not specified")
| |
| end
| |
| token = lexer.next()
| |
| if token[1] ~= T_SYMBOL or token[2] ~= "R" then
| |
| fail("Number type R not specified")
| |
| end
| |
| token = lexer.next()
| |
| if token[1] ~= T_STRING then
| |
| fail("Title missing from header")
| |
| end
| |
| game.title = token[2]
| |
|
| |
| -- Players
| |
| if lexer.next()[1] ~= T_LBRACE then
| |
| fail("Expecting { before players")
| |
| end
| |
| while lexer.peek()[1] == T_STRING do
| |
| table.insert( game.players, lexer.next()[2] )
| |
| end
| |
| if #game.players ~= 2 then
| |
| fail("Game has " .. #game.players .. " players, only 2 are supported")
| |
| end
| |
| if lexer.next()[1] ~= T_RBRACE then
| |
| fail("Expecting } after players")
| |
| end
| |
|
| |
| -- Strats
| |
| if lexer.next()[1] ~= T_LBRACE then
| |
| fail("Expecting { before strategies")
| |
| end
| |
| for i, p in ipairs(game.players) do
| |
| if lexer.next()[1] ~= T_LBRACE then
| |
| fail("Expecting { for player " .. i .. " strategies")
| |
| end
| |
| game.strats[i] = {}
| |
| while lexer.peek()[1] == T_STRING do
| |
| table.insert(game.strats[i], lexer.next()[2])
| |
| end
| |
| if lexer.next()[1] ~= T_RBRACE then
| |
| fail("Expecting } for player " .. i .. " strategies")
| |
| end
| |
| end
| |
| if lexer.next()[1] ~= T_RBRACE then
| |
| fail("Expecting } after strategies")
| |
| end
| |
|
| |
| -- Comment
| |
| if lexer.peek()[1] == T_STRING then
| |
| game.comment = lexer.next()[2]
| |
| end
| |
|
| |
| -- Outcomes
| |
| if lexer.next()[1] ~= T_LBRACE then
| |
| fail("Expecting { before outcomes")
| |
| end
| |
| while lexer.next()[1] == T_LBRACE do
| |
| if lexer.next()[1] ~= T_STRING then
| |
| fail("Expecting string for outcome")
| |
| end
| |
| local outcome = {}
| |
| for i = 1,2 do
| |
| token = lexer.next()
| |
| if token[1] == T_COMMA then token = lexer.next() end
| |
| if token[1] ~= T_NUMBER then
| |
| fail("Expecting number for outcome")
| |
| end
| |
| table.insert(outcome, p._ratParse(token[2]))
| |
| end
| |
| if (outcome[1] + outcome[2]).num ~= 0 then
| |
| local sum = outcome[1] + outcome[2]
| |
| fail("Expecting only zero-sum outcomes, "
| |
| .. outcome[1].num .. "/" .. outcome[1].den .. " - "
| |
| .. outcome[2].num .. "/" .. outcome[2].den .. " = "
| |
| .. sum.num .. "/" .. sum.den
| |
| )
| |
| end
| |
| if lexer.next()[1] ~= T_RBRACE then
| |
| fail("Expecting } after outcome")
| |
| end
| |
| table.insert(game.outcomes, outcome[1])
| |
| end
| |
| if lexer.prev()[1] ~= T_RBRACE then
| |
| fail("Expecting } after outcomes")
| |
| end
| |
|
| |
| -- If an outcome hasn't been filled in, it has index 0
| |
| -- Hopefully making a 0-indexed array here doesn't break anything >,<
| |
| game.outcomes[0] = rational(0,1)
| |
|
| |
| -- Outcome mapping
| |
| for j,p2 in ipairs(game.strats[2]) do
| |
| local row = {}
| |
| for i,p1 in ipairs(game.strats[1]) do
| |
| if lexer.next()[1] ~= T_NUMBER then
| |
| fail("Expecting number for outcome index")
| |
| end
| |
| local index = lexer.curr()[2] + 0
| |
| if game.outcomes[index] == nil then
| |
| fail("Index to undefined outcome")
| |
| end
| |
| table.insert(row, index)
| |
| end
| |
| table.insert(game.map, row)
| |
| end
| |
|
| |
| return game
| |
| end
| |
|
| |
| p.render = function(frame)
| |
| local page = frame.args[1]
| |
| local collapsed = yesno( frame.args["collapsed"] )
| |
| return p._render(page, collapsed)
| |
| end
| |
|
| |
| p._render = function(page, collapsed)
| |
| -- All .gbt files belong in the Mixup: namespace
| |
| local title = mw.title.makeTitle('Mixup', page)
| |
| local gbt = title:getContent()
| |
| if gbt == nil then
| |
| error("[[Mixup:" .. page .. "]] doesn't exist", 0)
| |
| end
| |
|
| |
| local nfg = string.match(gbt, "<nfgfile[^>]->(.-)</nfgfile[^>]->")
| |
| local game = p._nfgParse(nfg)
| |
| --mw.logObject(game)
| |
|
| |
| --
| |
| -- Create HTML for payoffs table
| |
| --
| |
| local h_payoffs = mw.html.create('table')
| |
| local h_payoffs_cols = mw.html.create('tr'):node(
| |
| mw.html.create('th'):addClass('bg-white')
| |
| :node(mw.html.create('div'):attr('class', 'border-hack bottom border-black'))
| |
| :node(mw.html.create('div'):attr('class', 'border-hack right border-black'))
| |
| )
| |
| for i,strat in ipairs(game.strats[2]) do
| |
| h_payoffs_cols:node(
| |
| mw.html.create('th'):attr('class', 'fg-p2 bg-white'):wikitext(strat)
| |
| :node(mw.html.create('div'):attr('class', 'border-hack bottom border-black'))
| |
| )
| |
| end
| |
| h_payoffs:node(h_payoffs_cols)
| |
| for i,strat in ipairs(game.strats[1]) do
| |
| local h_row = mw.html.create('tr'):node(
| |
| mw.html.create('th'):attr('class', 'fg-p1 bg-white'):wikitext(strat)
| |
| :node(mw.html.create('div'):attr('class', 'border-hack right border-black'))
| |
| )
| |
| for j,_ in ipairs(game.strats[2]) do
| |
| local rat = game.outcomes[ game.map[j][i] ]
| |
| h_row:node(mw.html.create('td')
| |
| :attr( 'class', G._main(rat.num / rat.den, -100, 100) )
| |
| :wikitext(string.format("%.1f", rat.num / rat.den))
| |
| )
| |
| end
| |
| h_payoffs:node(h_row)
| |
| end
| |
|
| |
| --
| |
| -- Create HTML for equilibrium, if it exists
| |
| --
| |
| local profile = string.match(gbt, "<profile[^>]->(.-)</profile[^>]->")
| |
| local h_profile = nil
| |
| if profile ~= nil then
| |
| local r_profile = {}
| |
| local split = mw.text.split(mw.text.trim(profile), ",")
| |
| if #split ~= #game.strats[1] + #game.strats[2] then
| |
| error("Profile has mismatched number of probabilities: "
| |
| .. #split .. " vs " .. (#game.strats[1] + #game.strats[2]))
| |
| end
| |
| local n = 1
| |
| for q = 1,2 do
| |
| r_profile[q] = {}
| |
| for i,v in ipairs(game.strats[q]) do
| |
| r_profile[q][i] = p._ratParse(split[n])
| |
| n = n+1
| |
| end
| |
| end
| |
|
| |
| local F = function (rat)
| |
| if rat == nil then return "0" end
| |
| -- Turn e.g. 15/-4 into -15/4
| |
| local n,d = rat.num, rat.den
| |
| if d < 0 then
| |
| n = n * -1
| |
| d = d * -1
| |
| end
| |
| return mw.getCurrentFrame():expandTemplate{
| |
| title = "F",
| |
| args = { n, d }
| |
| }
| |
| end
| |
|
| |
| -- Calculate the payoff for p1 of this equilibrium
| |
| --
| |
| -- I believe you can get the payoff of any individual non-dominated
| |
| -- outcome, since for an equilibrium they're all the same, but I'm not
| |
| -- entirely surely this is a guaranteed property.
| |
| local payoff = 0
| |
| for i = 1,#game.strats[1] do
| |
| for j = 1,#game.strats[2] do
| |
| local outcome = game.outcomes[ game.map[j][i] ]
| |
| payoff = payoff + outcome * r_profile[2][j] * r_profile[1][i]
| |
| end
| |
| end
| |
|
| |
| -- Calculate the payoff of each strategy of this equilibrium
| |
| --
| |
| -- Used to display the payoff of the dominated options
| |
| local s_payoff = {}
| |
| for p = 1,2 do
| |
| local q = (p == 1 and 2 or 1)
| |
| s_payoff[p] = {}
| |
| for i = 1,#game.strats[p] do
| |
| local payoff = 0
| |
| for j = 1,#game.strats[q] do
| |
| local outcome = (p == 1)
| |
| and game.outcomes[ game.map[j][i] ]
| |
| or (game.outcomes[ game.map[i][j] ] * -1)
| |
| payoff = payoff + outcome * r_profile[q][j]
| |
| end
| |
| s_payoff[p][i] = payoff
| |
| end
| |
| end
| |
| --mw.logObject(s_payoff)
| |
|
| |
| h_profile = mw.html.create('div'):attr('class', 'profile')
| |
| local h_elib = mw.html.create('div'):attr('class', 'equilibrium')
| |
| :node( mw.html.create('p'):wikitext(
| |
| "Nash equilibrium with payoff " .. F(payoff)) )
| |
| local h_pair = mw.html.create('div'):attr('class', 'strategy-pair')
| |
| local dominated_strats_exist = false
| |
| local h_dominated = {}
| |
| local n = 1
| |
| for p = 1,2 do
| |
| h_dominated[p] = mw.html.create('dl'):attr('class', 'strategy')
| |
| local h_strat = mw.html.create('dl'):attr('class', 'strategy')
| |
| for i,s in ipairs(game.strats[p]) do
| |
| local prob = r_profile[p][i]
| |
| local h_prob = mw.html.create('dd')
| |
| local h_option = mw.html.create('div')
| |
| :node(mw.html.create('dt'):attr('class', 'fg-p' .. p):wikitext(s))
| |
| :node(h_prob)
| |
| if prob.num == 0 then
| |
| dominated_strats_exist = true
| |
| h_prob:wikitext( F(s_payoff[p][i]) )
| |
| h_dominated[p]:node(h_option)
| |
| else
| |
| h_prob:wikitext( F(prob) )
| |
| h_strat:node(h_option)
| |
| end
| |
| end
| |
| h_pair:node(h_strat)
| |
| end
| |
| h_profile:node(h_elib:node(h_pair))
| |
| if dominated_strats_exist then
| |
| local h_pair = mw.html.create('div'):attr('class', 'strategy-pair')
| |
| for p = 1,2 do
| |
| h_pair:node(h_dominated[p])
| |
| end
| |
| h_profile:node(mw.html.create('div'):attr('class', 'dominated')
| |
| :node(mw.html.create('p'):wikitext("Payoff for dominated options"))
| |
| :node(h_pair)
| |
| )
| |
| end
| |
| end
| |
|
| |
| -- Put it together
| |
| local header = mw.html.create('div'):attr('class', 'mixup-header')
| |
| :node(mw.html.create('div'):attr('class', 'mixup-title')
| |
| :wikitext(
| |
| "[[" .. title.fullText .. "]]" ..
| |
| " ([" .. title:fullUrl() .. "?action=raw download])" ..
| |
| " <sup>[[Template:Mixup#Explanation|What is this?]]</sup>"
| |
| )
| |
| )
| |
|
| |
| local body = mw.html.create('div')
| |
| :attr('class', 'mixup-body mw-collapsible-content border-blue-30')
| |
| :node(mw.html.create('div'):attr('class', 'payoffs'):node(h_payoffs))
| |
| :node(h_profile)
| |
|
| |
| local ret = mw.html.create('div')
| |
| :attr('class', 'mixup mw-collapsible border-blue-30')
| |
| :node(header)
| |
|
| |
| if collapsed then
| |
| ret:addClass('mw-collapsed')
| |
| end
| |
|
| |
| if game.comment ~= "" then
| |
| ret:node(mw.html.create('div')
| |
| :attr('class', 'mixup-descr')
| |
| :wikitext( mw.getCurrentFrame():preprocess( "\n" .. game.comment .. "\n" ) )
| |
| )
| |
| end
| |
|
| |
| ret:node(body)
| |
|
| |
| --mw.logObject(ret)
| |
| return ret
| |
| end
| |
|
| |
| return p
| |
