Module:MixupTest

Documentation for this module may be created at Module:MixupTest/doc

local rational = require( "Module:Rational" )
local yesno = require( "Module:Yesno" )
local G = require( "Module:GTest" )

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
		token = lexer.next()
		if token[1] ~= T_STRING then
			fail("Expecting string for outcome")
		end
		local outcome = {}
		outcome_label = token[2]
		
		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
		table.insert(outcome, outcome_label)
		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)
	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), 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)
	local minVal = math.huge
    local maxVal = -math.huge
	for i,strat in ipairs(game.strats[1]) do
		for j,_ in ipairs(game.strats[2]) do
			local rat = game.outcomes[ game.map[j][i] ][1]
			local val = rat.num / rat.den
			minVal = math.min(minVal, val)
        	maxVal = math.max(maxVal, val)
		end
	end
	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] ][1]
			local label = game.outcomes[ game.map[j][i] ][3]
			h_row:node(mw.html.create('td')
				:attr( 'class', G._main(rat.num / rat.den, minVal, maxVal) )
				:node(mw.html.create('abbr'):attr('title', label)
					:wikitext(string.format("%d", math.floor(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] ][1]
				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] ][1]
						or (game.outcomes[ game.map[i][j] ][1] * -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(
				"[TEST] " ..
				"[[" .. 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