function new_node()
	return { state = nil, actions = nil, parent = nil, children = {}, value = 0, visits = 0 };
end

function roulette(node)
	return (node.actions)[math.random(#(node.actions))]
end

state_counter = 0;

function MonteCarlo(game, iterations)

	tree = { root = new_node() };
	tree.root.state = state_counter;
	state_counter = state_counter + 1;
	savestate.save(tostring(0))

	for i=1,iterations,1
	do
		curNode = tree.root;
		while (curNode.actions ~= nil) do
			nextAct = roulette(curNode);
			nextNode = curNode.children[nextAct];
			if (nextNode.visits == 0) then
				savestate.load(tostring(curNode.state))
				game.perform(nextAct);
				nextNode.state = state_counter;
				savestate.save(tostring(state_counter));
				state_counter = state_counter + 1;
			end
			nextNode.visits = nextNode.visits + 1;
			nextNode.parent = curNode;
			curNode = nextNode;
		end
		curNode.actions = game.expand(curNode)
		curNode.actions = {"R", "A"}
		score = game.rollout();
		while (curNode ~= nil) do
			curNode.value = curNode.value + score;
			curNode = curNode.parent;
		end
	end
end

SuperMarioBros = {
	name = "Super Mario Bros.",

	expand = function(node)
		acts = {"R", "A"}
		for i, act in ipairs(acts) do
			node.children[act] = new_node()
		end
		node.actions = {"R", "A"}
	end,

	perform = function(act)
		if     (act == "R") then
			--print("R")
			joypad.set({B = true, Right = true}, 1)
			emu.frameadvance()
			joypad.set({B = true, Right = true}, 1)
			emu.frameadvance()
			joypad.set({B = true, Right = true}, 1)
			emu.frameadvance()
			joypad.set({B = true, Right = true}, 1)
			emu.frameadvance()
			joypad.set({B = true, Right = true}, 1)
			emu.frameadvance()
		elseif (act == "A") then
			--print("A")
			joypad.set({B = true, Right = true, A = true}, 1)
			emu.frameadvance()
			joypad.set({B = true, Right = true, A = true}, 1)
			emu.frameadvance()
			joypad.set({B = true, Right = true, A = true}, 1)
			emu.frameadvance()
			joypad.set({B = true, Right = true, A = true}, 1)
			emu.frameadvance()
			joypad.set({B = true, Right = true, A = true}, 1)
			emu.frameadvance()
		end

	end,

	rollout = function()
		score = 0
		for i = 0,4,1 do
			score = score + math.pow(10,i) * mainmemory.readbyte(0x7DC - i)
		end
		return score;
	end,
}

MonteCarlo(SuperMarioBros, 10000)