-- This is a tic-tac-toe thing I made in one day, on 2009-09-08 to try as a
-- part of Reddit's developer hiring round 3. I was stupid to try to do this in
-- one day, but at least it hopefully excuses me from the awful looks and
-- unoptimized code. I am proud to say that I think the AI is quite impressive,
-- though. I've never coded tic-tac-toe before.
--
-- I'll let you guys know if I start improving things so you don't think I
-- actually made some awesome code in one day.
--
-- Released into the public domain by Teran McKinney (sega01).
-- PS: If you're crazy enough to actually want to run this, you need WebLua 0.3
-- from http://go-beyond.org/weblua/
-- PPS: If you wish to find me, I'm sega01 on Reddit, or you can see my
-- website: http://go-beyond.org/
-- 2010-09-09 14:41 Update:
-- So the 486 survived the night quite well, but it wasn't well tested. Only
-- 1500 hits or so :-(. I did do one tiny optimization, just removing some
-- duplicity, and one small bug fix. I could barely find a spot where it would
-- run differently, but sure enough, ?s=4&t=2211012000000000 was it.
--
-- The nature of this code makes bugs really hard to spot, at least via using
-- it, rather than looking at the code. You could probably take out one
-- direction and it'd still run quite well, with how recursive the tests are.
--
-- And it looks like there's another: ?s=10&t=2000000001000000000000000000000000000000000000000000000000000000000000000000000000000000001000000002
--
-- Search for BUGFIX, or OPTIMIZATION, if you're curious.
-- 2010-09-09 16:11 Update:
-- So it looks like it is beatable, believe it or not. You have to start
-- yourself, which requires some URL tweaking. Start with:
-- http://foureightysix.go-beyond.org/?s=3&t=000000100
-- and do top right, bottom right, and then middle right, and you win.
--
-- Seems to only work on a 3x3 board. I might have to add an opposite corner
-- factor for that.
-- This is not fully commented, so beware.
-- Old ideas and concepts. You can ignore this bit.
-- i=slot on the board
-- s=square root of board size
-- Obviously only works with non-edge pieces, would need work. Not using anyways
--[[
function whichtoucheswhich(i,s)
print(i+1)
print(i-1)
print(i+s)
print(i-s)
print(i+s+1)
print(i+s-1)
print(i-s+1)
print(i-s-1)
end
--]]
-- To help with debugging.
--[[if not wl_send_headers then
wl_send_headers=function() print "You\'re on the console and I need to get working!" end
write=function(i) print(i) end
wl={get={}}
wl.get["s"]="3"
wl.get["t"]="210210210"
else--]]
wl_send_headers()
wl.get={}
wl_decode_get()
--end
--Board: 0 is blank, 1 is them, 2 is us.
--[[board={ 0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0}
--]]
--s=10
--ss=s^2
-- To the real stuff, and yes, I know this is ugly.
-- This is the ?s= bit. It's the board size in one dimension.
if wl.get["s"] then
-- Ugly, rushed coding.
if (string.len(wl.get["s"])) <= 2 and (wl.get["s"]:match("^%d+$")) then
s=tonumber(wl.get["s"])
if (s > 10) then
return
end
ss=s^2
-- t for tic-tac-toe?
if wl.get["t"] then
board={}
if (string.len(wl.get["t"])) == ss and (wl.get["t"]:match("^%d+$")) then
--Thanks to someone on Stackoverflow, via google. I can't believe I haven't asked on IRC for help tonight. --MODIFY if changes <- Yeah, it changed
for c in wl.get["t"]:gmatch"." do
local n=tonumber(c)
if (n >= 0 and n <= 2) then
table.insert(board,n)
else
return --MODIFY is return the right thing to use?
end
end
else
return
end
end
end
end
--for k,v in pairs(board) do write(k.." "..v) end --MODIFY
function resetTheScores()
freedom=true
friendlyScore=0
enemyScore=0
end
function checkTheSpot()
-- These may need tweaking.
if (board[spotInQuestion] == 1) then
enemyScore=enemyScore+2
freedom=false
elseif (board[spotInQuestion] == 2) then
friendlyScore=friendlyScore+1
end
end
function totalTheScores()
if freedom then
--Freedom modifier
score=score+1+friendlyScore
else
if (friendlyScore == 0) then
--Enemy modifier, if not blocked.
score=score+enemyScore
end
end
end
-- Main AI loop
function doTheAI()
weightedPossibilities={}
for i=1,ss do
local spot=i
score=0
-- Lua seriously needs a continue statement :-/. Ugly hack:
if (board[i] == 0) then
-- Order of directions doesn't really matter, so let's make it easy on
-- ourselves and start horizontally.
--
-- Sadly, we have to scan in *all* directions, else we get issues, or so
-- I think.
resetTheScores()
local startScan=spot-((spot-1)%s)
for i=startScan,startScan+s-1 do
spotInQuestion=i
checkTheSpot()
end
totalTheScores()
-- Now that wasn't so bad, was it?
-- Vertically
resetTheScores()
local startScan=spot%s
if (startScan == 0) then
startScan=s
end
-- I think these are symptoms of this being coded in one day.
spotInQuestion=startScan
checkTheSpot()
for i=1,s-1 do
spotInQuestion=startScan+(i*s)
checkTheSpot()
end
totalTheScores()
-- Diagonally
-- I don't know of a good way to do this, so I'd prefer to avoid it :-/.
-- Left to right (top to bottom)
-- s+2 is the minimum second multiple for a 3x3 or larger board.
leftDiagonal=false
local leftDiagonalMultiples={}
--OPTIMIZATION: We don't need local leftDiagonalMultiples={1 or s} in
-- these, with the test below. Still not good, but it's a slight
-- improvement, nonetheless.
for i=2,s do
local multiple=1+(s+1)*(i-1)
if (multiple == spot) then
leftDiagonal=true
else
leftDiagonalMultiples[i]=multiple
end
end
-- Right to left (top to bottom)
-- s+2 is the minimum second multiple for a 3x3 or larger board.
rightDiagonal=false
local rightDiagonalMultiples={}
for i=2,s do
local multiple=s+(s-1)*(i-1)
if (multiple == spot) then
rightDiagonal=true
else
rightDiagonalMultiples[i]=multiple
--BUGFIX: was rightDiagonalMultiples[i-1]=multiple
end
end
-- Covering all bases. I'm sure we could combine this with ^ if my
-- brain was working right now.
if (spot == 1) then
leftDiagonal=true
elseif (spot == s) then
rightDiagonal=true
end
if leftDiagonal then
resetTheScores()
for i=1,s do
if not (leftDiagonalMultiples[i] == spot) then
spotInQuestion=leftDiagonalMultiples[i]
checkTheSpot()
end
end
totalTheScores()
end
if rightDiagonal then
resetTheScores()
for i=1,s do
if not (rightDiagonalMultiples[i] == spot) then
spotInQuestion=rightDiagonalMultiples[i]
checkTheSpot()
end
end
totalTheScores()
end
table.insert(weightedPossibilities,{spot,score})
end -- If statement
end
table.sort(weightedPossibilities, function(lhs, rhs) return lhs[2] > rhs[2] end)
-- Might want to random up the top ones if they are equal, eventually.
end
function printTheBoard()
local textBoard=""
for k,v in pairs(board) do
-- Basically the w.get["t"], but with my AI's improvements :-).
-- This must be slow.
textBoard=textBoard..v
end
-- Yes, we have to do this twice :-/.
for k,v in pairs(board) do
if (v == 0) then
-- Huge thanks to Dylan on #lua for this.
local chosenBoard=textBoard:sub(1,k-1).."1"..textBoard:sub(k+1)
write ("0")
elseif (v == 2) then
write "2"
else
write "1"
end
if (k%s == 0) then
write"
"
end
end
end
-- Ugly, ugly, ugly
write [[
Tic Tac Toe on a 486
Tic Tac Toe
So it looks like I've made the world's ugliest tic-tac-toe. You'll have to pretend that 2 is the computer and 1 is you. 0 is a free spot that you can click on, if you haven't noticed. If you make the final move and it clears up the board, you'll get a blank page; I may fix that later. And here's the source code, if you're curious.
3x3
4x4
9x9
10x10
]]
if s then
doTheAI()
-- Claim our spot.
board[weightedPossibilities[1][1]]=2
printTheBoard()
end
write [[
PS: This is hosted on a 40Mhz 486DX2. I wrote this whole code in a day, have barely tested it, and it's not optimized at all. It does between 13 and 1.2~ Tic Tac Toe calculations per second, depending on how large of a board you're using. Hopefully, it'll survive Reddit. Latency will be higher than you're probably used to, especially over IPv4, as I'm proxying to it over my main server, through IPv6 (which, ironically, is tunneled, itself). --Teran]]
if not wl.hits then
wl.hits=0
end
wl.hits=wl.hits+1
write ([[Total hits since 2009-09-09T06:32Z: ]]..wl.hits..[[
]])