HTML5 and JavaScript, 12.72 + 50 + 50 + 50 = 162.72 points
Hi, this is my very first code golf, but I think, the following code works quite well (it's a full HTML page, 3848 bytes).
<html><head><meta charset="utf-8"><title>Hex</title><script type="text/javascript">var r=20;var w=r*2*(Math.sqrt(3)/2);var ctx;var s=[-1,-1];var b=new Array(14);var h=[];var p=0;var m=false;var t=true;function H(c,x,y,r){c.beginPath();c.moveTo(x,y-r);for(var i=0;i<6;i++)c.lineTo(x+r*Math.cos(Math.PI*(1.5+1/3*i)),y+r*Math.sin(Math.PI*(1.5+1/3*i)));c.closePath();c.fill();c.stroke();}function P(c,p){c.lineWidth=10;c.beginPath();c.moveTo((p[0][0]+p[0][1])*w-(p[0][1]-4)*(w/2),(p[0][1]+2)*1.5*r);for(var i=1;i<p.length;i++)c.lineTo((p[i][0]+p[i][1])*w-(p[i][1]-4)*(w/2),(p[i][1]+2)*1.5*r);c.stroke();}function S(e){var l=ctx.getImageData(e.clientX-20,e.clientY,1,1).data;l[0]-=l[2]==38||l[2]==178 ? 241 : 0;l[1]-=l[2]==178 ? 220 : (l[2]==38 ? 0 : 140);if(l[0]>=0&&l[0]<=13&&l[1]>=0&&l[1]<=13&&(l[2]==38||l[2]==171||l[2]==178))s=[l[0],l[1]];else s=[-1,-1];}function Ai(){var pos;do pos=[Math.floor(Math.random()*14),Math.floor(Math.random()*14)];while(b[pos[0]][pos[1]]!=-1);h.push([pos[0],pos[1],1]);b[pos[0]][pos[1]]=1;}function Fa(a,d){for(var i=0;i<a.length;i++)if(JSON.stringify(a[i])==JSON.stringify(d))return i;return -1;}function C(x,y,c,o,s){var a=[-1,0,1,0,0,-1,0,1,1,-1,-1,1];var r=[];for(var i=0;i<6;i++)if(x+a[i*2]>=0&&x+a[i*2]<14&&y+a[i*2+1]>=0&&y+a[i*2+1]<14)if(b[x+a[i*2]][y+a[i*2+1]]==c&&Fa(o,[x+a[i*2],y+a[i*2+1]])==-1&&Fa(s,[x+a[i*2],y+a[i*2+1]])==-1)r.push([x+a[i*2],y+a[i*2+1]]);return r;}function W(c){var o=[],op=[],s=[],sp=[];for(var a=0;a<14;a++){if(b[c==0?a:0][c==0?0:a]==c){o.length=op.length=s.length=sp.length=0;var pf=false;o.push([c==0?a:0,c==0?0:a]);op.push(-1);while(o.length>0){var u=o[0];o.splice(0,1);var uI=op.splice(0,1);s.push(u);sp.push(uI);if(u[c==0?1:0]==13){pf=true;break;}var n=C(u[0],u[1],c,o,s);for(var i=0;i<n.length;i++){o.push(n[i]);op.push(s.length-1);}}if(pf){var p=[];var u=s.length-1;while(sp[u]!=-1){p.push(s[u]);u=sp[u];}p.push([c==0?a:0,c==0?0:a]);p.reverse();t=false;return p;}}}return false;}function Md(e){S(e);if(t){if(s[0]!=-1&&s[1]!=-1){h.push([s[0],s[1],p]);b[s[0]][s[1]]=p;if(m)p=p==0 ? 1 : 0;else Ai();D();var p0=W(0),p1=W(1);if(p0!=false){P(ctx,p0);alert((m?"The red player":"You")+" won!");}else if(p1!=false){P(ctx,p1);alert((m?"The blue player":"The computer")+" won!");}}}}function Mm(e){S(e);if(t)D();}function D(){ctx.clearRect(0,0,850,600);ctx.lineWidth=1;ctx.fillStyle="rgb(0,154,172)";ctx.beginPath();ctx.moveTo(w*15.65,r);ctx.lineTo(w*23.5,24.5*r);ctx.lineTo(0,r);ctx.lineTo(w*7.85,24.5*r);ctx.closePath();ctx.fill();ctx.fillStyle="rgb(255,0,39)";ctx.beginPath();ctx.moveTo(0,r);ctx.lineTo(w*15.65,r);ctx.lineTo(w*7.85,24.5*r);ctx.lineTo(w*23.5,24.5*r);ctx.closePath();ctx.fill();var num=0;ctx.strokeStyle="white";for(var y=0;y<14;y++){for(var x=0;x<14;x++){if(b[x][y]==0)ctx.fillStyle="rgb(255,0,39)";else if(b[x][y]==1)ctx.fillStyle="rgb(0,154,172)";else if(x==s[0]&&y==s[1])ctx.fillStyle="rgb("+(x+(p==0?241:0))+","+(y+(p==0?0:140))+","+(p==0?38:171)+")";else ctx.fillStyle="rgb("+(x+241)+","+(y+220)+",178)";H(ctx,(x+y)*w-(y-4)*(w/2),(y+2)*1.5*r,r);num++;}}}function Mp(){m=!m;p=0;I();}function U(){if(t){var a;if(h.length>0){a=h[h.length-1];b[a[0]][a[1]]=-1;h.pop();}if(!m){a=h[h.length-1];b[a[0]][a[1]]=-1;h.pop();}p=a[2];D();}}function I(){for(var i=0;i<14;i++){b[i]=new Array(14);for(var j=0;j<14;j++)b[i][j]=-1;}history.length=0;t=true;D();}function L(){var a=document.getElementById("o");ctx=a.getContext("2d");document.getElementById("mp").checked=false;a.onmousedown=Md;a.onmousemove=Mm;I();}</script></head><body onload="L()"><canvas style="position:absolute;top:0px;left:20px" width="850" height="600" id="o"></canvas><div style="position:absolute;top:250px;left:20px"><input type="button" onClick="I()" value="New game"><br><br>Multiplayer: <input id="mp" type="checkbox" onClick="Mp()"><br><input type="button" onClick="U()" value="Undo"></div></body></html>
Expanded
<html>
<head>
<meta charset="utf-8">
<title>Hex</title>
<script type="text/javascript">
var r = 20;
var w = r*2*(Math.sqrt(3)/2);
var ctx;
var sel = [-1, -1];
var board = new Array(14);
var hist = [];
var player = 0;
var multiplayer = false;
var active = true;
function drawHexagon(c, x, y, r)
{
c.beginPath();
c.moveTo(x, y-r);
for(var i=0; i<6; i++)
c.lineTo(x+r*Math.cos(Math.PI*(1.5+1/3*i)), y+r*Math.sin(Math.PI*(1.5+1/3*i)));
c.closePath();
c.fill();
c.stroke();
}
function drawPath(c, p)
{
c.lineWidth = 10;
c.beginPath();
c.moveTo((p[0][0]+p[0][1])*w - (p[0][1]-4)*(w/2), (p[0][1]+2)*1.5*r);
for(var i=1; i<p.length; i++)
c.lineTo((p[i][0]+p[i][1])*w - (p[i][1]-4)*(w/2), (p[i][1]+2)*1.5*r);
c.stroke();
}
function getSel(e)
{
var color = ctx.getImageData(e.clientX-20, e.clientY, 1, 1).data;
color[0] -= color[2]==38||color[2]==178 ? 241 : 0;
color[1] -= color[2]==178 ? 220 : (color[2]==38 ? 0 : 140);
if(color[0] >= 0 && color[0] <= 13 && color[1] >= 0 && color[1] <= 13 && (color[2] == 38 || color[2] == 171 || color[2] == 178))
sel = [color[0], color[1]];
else
sel = [-1, -1];
}
function aiMove()
{
var pos;
do
pos = [Math.floor(Math.random()*14), Math.floor(Math.random()*14)];
while(board[pos[0]][pos[1]] != -1);
hist.push([pos[0],pos[1],1]);
board[pos[0]][pos[1]] = 1;
}
function findArr(a, b)
{
for(var i=0; i<a.length; i++)
if(JSON.stringify(a[i]) == JSON.stringify(b))
return i;
return -1;
}
function getConnections(x, y, c, open, closed)
{
var a = [-1, 0, 1, 0, 0, -1, 0, 1, 1, -1, -1, 1];
var ret = [];
for(var i=0; i<6; i++)
if(x+a[i*2] >= 0 && x+a[i*2] < 14 && y+a[i*2+1] >= 0 && y+a[i*2+1] < 14)
if(board[x+a[i*2]][y+a[i*2+1]] == c && findArr(open, [x+a[i*2],y+a[i*2+1]]) == -1 && findArr(closed, [x+a[i*2],y+a[i*2+1]]) == -1)
ret.push([x+a[i*2],y+a[i*2+1]]);
return ret;
}
function checkWin(c)
{
var open = [], openPrev = [], closed = [], closedPrev = [];
for(var a=0; a<14; a++)
{
if(board[c==0?a:0][c==0?0:a] == c)
{
open.length = openPrev.length = closed.length = closedPrev.length = 0;
var pathFound = false;
open.push([c==0?a:0, c==0?0:a]);
openPrev.push(-1);
while(open.length > 0)
{
var u = open[0];
open.splice(0, 1);
var uI = openPrev.splice(0, 1);
closed.push(u);
closedPrev.push(uI);
if(u[c==0?1:0] == 13)
{
pathFound = true;
break;
}
var connections = getConnections(u[0], u[1], c, open, closed);
for(var i=0; i<connections.length; i++)
{
open.push(connections[i]);
openPrev.push(closed.length-1);
}
}
if(pathFound)
{
var path = [];
var u = closed.length-1;
while(closedPrev[u] != -1)
{
path.push(closed[u]);
u = closedPrev[u];
}
path.push([c==0?a:0, c==0?0:a]);
path.reverse();
active = false;
return path;
}
}
}
return false;
}
function mouseDown(e)
{
getSel(e);
if(active)
{
if(sel[0] != -1 && sel[1] != -1)
{
hist.push([sel[0],sel[1],player]);
board[sel[0]][sel[1]] = player;
if(multiplayer)
player = player==0 ? 1 : 0;
else
aiMove();
draw();
var p0 = checkWin(0), p1 = checkWin(1);
if(p0 != false)
{ drawPath(ctx, p0); alert((multiplayer?"The red player":"You") + " won!"); }
else if(p1 != false)
{ drawPath(ctx, p1); alert((multiplayer?"The blue player":"The computer") + " won!"); }
}
}
}
function mouseMove(e)
{
getSel(e);
if(active)
draw();
}
function draw()
{
ctx.clearRect(0, 0, 850, 600);
ctx.lineWidth = 1;
ctx.fillStyle = "rgb(0,154,172)";
ctx.beginPath();
ctx.moveTo(w*15.65, r);
ctx.lineTo(w*23.5, 24.5*r);
ctx.lineTo(0, r);
ctx.lineTo(w*7.85, 24.5*r);
ctx.closePath();
ctx.fill();
ctx.fillStyle = "rgb(255,0,39)";
ctx.beginPath();
ctx.moveTo(0, r);
ctx.lineTo(w*15.65, r);
ctx.lineTo(w*7.85, 24.5*r);
ctx.lineTo(w*23.5, 24.5*r);
ctx.closePath();
ctx.fill();
var num = 0;
ctx.strokeStyle = "white";
for(var y=0; y<14; y++)
{
for(var x=0; x<14; x++)
{
if(board[x][y] == 0)
ctx.fillStyle = "rgb(255,0,39)";
else if(board[x][y] == 1)
ctx.fillStyle = "rgb(0,154,172)";
else if(x == sel[0] && y == sel[1])
ctx.fillStyle = "rgb(" + (x+(player==0?241:0)) + "," + (y+(player==0?0:140)) + "," + (player==0?38:171) + ")";
else
ctx.fillStyle = "rgb(" + (x+241) + "," + (y+220) + ",178)";
drawHexagon(ctx, (x+y)*w - (y-4)*(w/2), (y+2)*1.5*r, r);
num++;
}
}
}
function chgMP()
{
multiplayer = !multiplayer;
player = 0;
init();
}
function undo()
{
if(active)
{
var a;
if(hist.length > 0)
{
a = hist[hist.length-1];
board[a[0]][a[1]] = -1;
hist.pop();
}
if(!multiplayer)
{
a = hist[hist.length-1];
board[a[0]][a[1]] = -1;
hist.pop();
}
player = a[2];
draw();
}
}
function init()
{
for(var i=0; i<14; i++)
{
board[i] = new Array(14);
for(var j=0; j<14; j++)
board[i][j] = -1;
}
hist.length = 0;
active = true;
draw();
}
function load()
{
var canvas = document.getElementById("output");
ctx = canvas.getContext("2d");
document.getElementById("mp").checked = false;
canvas.onmousedown = mouseDown;
canvas.onmousemove = mouseMove;
init();
}
</script>
</head>
<body onload="load()">
<canvas style="position:absolute; top:0px; left:20px" width="850" height="600" id="output">Canvas not supported...</canvas>
<div style="position:absolute; top:250px; left:20px"><input type="button" onClick="init()" value="New game"><br><br>Multiplayer: <input id="mp" type="checkbox" onClick="chgMP()"><br><input type="button" onClick="undo()" value="Undo"></div>
</body>
</html>
Explanation
The code uses the HTML5's canvas-tag to display the game (14x14 board). You can undo the last step and play against another player (enable Multiplayer) or the computer, but its AI is still very weak (it just uses a random position to place the next field). The entire graphical design is based on your screenshot.
Why is the best move prediction 75 points but the unbeatable bot 150 points? Don't these two tasks amount to solving and implementing the same problem? Also, if we don't go for these bonuses, can the bot just be entirely stupid? Like making random moves or flood-filing the board from one corner? – Martin Ender – 2015-06-04T23:29:05.690
1@MartinBüttner I believe the 75 point may refer to the capability of the program to output what would be the best move for you, according to it's AI, it doesn't require it to truly be the best theoretical possible move. – rorlork – 2015-06-04T23:31:28.943
@MartinBüttner Yes, the bot can make completely stupid moves. Telling the user, their next best move takes some additional code. Based on your AI this may or may not be a separate thing. – Renae Lider – 2015-06-05T00:15:40.047
@MartinBüttner I forgot to mention that the "stupid moves" will not count as "Best Moves" even though they can be a regular move. "Best Moves" are those moves that, when played consecutively, will maximize the user's winning probability to its highest value. – Renae Lider – 2015-06-05T00:28:06.787
It can be proved that an unbeatable strategy exists. Therefore any code that can give the optimal next move is automatically unbeatable when playing first. Since you have confirmed that "best move" does mean an optimal move, Martin Büttner's point about best move and unbeatable bot being the same task does appear to be true.
– trichoplax – 2015-06-09T17:17:03.000@trichoplax Yes, you are correct, but there is 25 point difference because the additional code required to add the prediction feature would take way some points (golfing points), even though the algorithms may be the same. So it is a balance between golfing points and prediction points. – Renae Lider – 2015-06-09T21:18:43.917
What are the restrictions on size? Is making a 1x1 board allowed? How about 3x3? 9x9 (the largest board for which an explicit solution has been found)? – 2012rcampion – 2015-06-10T12:55:11.650
@2012rcampion See coding rules #3 – Renae Lider – 2015-06-10T15:14:43.117
Well then, that makes the "super bot challenge" pretty trivial... – 2012rcampion – 2015-06-10T15:15:57.727
@2012rcampion What if the user moves first? They will beat your bot. – Renae Lider – 2015-06-10T15:19:50.397
You do not specify the order of the players, or that we must let the user choose the order. Also, since it has been (nonconstructively) proven that the first player can always force a win (on any size board), then if you require that the bot must be able to win when it moves second, then it is impossible for anybody to get the 150 point bonus. – 2012rcampion – 2015-06-10T15:44:11.297
@2012rcampion You are allowed to make a 1x1 grid and you are qualified for the super bot challenge. You'll get 150 points. (even though it won't be very fun to play) – Renae Lider – 2015-06-10T16:12:55.747