7
\$\begingroup\$

Introduction

Hex is a strategy board game played on a hexagonal grid, theoretically of any size and several possible shapes, but traditionally as an 11×11 rhombus. Other popular dimensions are 13×13 and 19×19 as a result of the game's relationship to the older game of Go. According to the book A Beautiful Mind, John Nash (one of the game's inventors) advocated 14×14 as the optimal size.

5x5 Hexboard, Blue wins

Game Rules

Each player has an allocated color, conventionally Red and Blue or White and Black. Players take turns placing a stone of their color on a single cell within the overall playing board. The goal for each player is to form a connected path of their own stones linking the opposing sides of the board marked by their colors, before their opponent connects his or her sides in a similar fashion. The first player to complete his or her connection wins the game. The four corner hexagons each belong to both adjacent sides.

Coding Rules

  1. You may use any program or language. Do not use any third party libraries or modules (full or in part) that implements the same game. The rest are fine.
  2. Players are computer and user.
  3. You may choose the size of the grid.
  4. You may use either CLI or GUI for output (see points).
  5. Your code should not exceed 5120 bytes.

Points

  • +(5120 - bytes) / 100 golfing points
  • +50 points for making GUI
  • +50 for two player mode
  • +75 for best-move-prediction#
  • +50 for undo-move

# Tell the user, if they wish, their next best move.

Super bot challenge

  • +150 points if your bot is undefeatable. Add this points ONLY IF you are absolutely certain of your bot's 100% winning capability. If any user defeats your bot and reports it all your points will be taken away (zero points). The person reporting this must either post a screenshot or input sequences based on the implementation of game. They will be awarded +150 points, if they have posted an answer.
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Martin Ender Jun 4 '15 at 23:29
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – rorlork Jun 4 '15 at 23:31
  • \$\begingroup\$ @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. \$\endgroup\$ – Renae Lider Jun 5 '15 at 0:15
  • \$\begingroup\$ @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. \$\endgroup\$ – Renae Lider Jun 5 '15 at 0:28
  • \$\begingroup\$ 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. \$\endgroup\$ – trichoplax Jun 9 '15 at 17:17
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Would this work as a Stack Snippet, so people can play the game direct from your answer? \$\endgroup\$ – trichoplax Jun 9 '15 at 17:52
  • \$\begingroup\$ There's an explanation of Stack Snippets here \$\endgroup\$ – trichoplax Jun 9 '15 at 18:07
  • \$\begingroup\$ ...and a sandbox for trying it out here \$\endgroup\$ – trichoplax Jun 9 '15 at 18:07
  • \$\begingroup\$ This question is not a code-golf; it's a code-challenge. You don't need to post your byte count, you need to post your score according to the scoring criteria listed by the OP. Thanks. \$\endgroup\$ – mbomb007 Jun 9 '15 at 18:49
  • 2
    \$\begingroup\$ Just so you know, your score is 160.54 (5120-4066/100 + 50 + 50 + 50). You should try and go for the unbeatable bot :) \$\endgroup\$ – Kade Jun 9 '15 at 19:50
0
\$\begingroup\$

Mathematica, 419.16 points

m = False;
Manipulate[
 ClickPane[
  Dynamic@Graphics[
    GraphicsComplex[
     Join @@ Array[{{2, 1}, {0, Sqrt[3]}}.{##} &, {9, 5}], {Red, 
      Polygon[{5, 25, 21, 41}], Blue, Polygon[{5, 21, 25, 41}], 
      EdgeForm[Gray], If[m, Red, Gray], 
      Polygon[{22, 27, 28, 24, 19, 18}]}], 
    PlotLabel -> 
     Column[{If[m, "Red Wins", "Red to Move"], 
       Row@{"Best move is: ", 
         Which[m, "(There are no legal moves remaining)", p == 1, 
          "(Computer's turn)", ! m, "1,1"]}}, Alignment -> Center]], 
  If[p == 2, m = True] &], {{p, 1, "# of players"}, {1, 2}}, 
 Row@{Button["Start", If[p == 1, m = True]], 
   Button["Undo", If[p == 2, m = False]], Button["Reset", m = False]}]

enter image description here

Except for the use of GraphicsComplex, this code is entirely ungolfed.

Controls

  • The # of players selector chooses the number of players. Note that there is a bug that allows you to change between 1-player (human vs. cpu) and 2-player (human vs. human) while a game is in progress.
  • Start lets the computer start playing in 1-player mode.
  • Undo takes back the last player's move in 2-player mode.
  • Reset sets the board back to the starting position.
  • Clicking on a hex when it is a human's turn plays in that hex. Note that there is a bug that allows a click outside the playing field to select hex 1,1.

Red always goes first, and in 1-player mode Red is always controlled by the computer. The computer always plays perfectly.

Points

  • 704 bytes: 44.16 points (This can be golfed down significantly.)
  • GUI: 50 points (It's worth it to add a gui if you can do it in under 5k (50 * 100) characters... yeah, Mathematica can do that.)
  • Two-player mode: 50 points (The second player never gets to go, but that's just too bad.)
  • Best-move display: 75 points (There is only one possible move, so this is trivial. Note that it is always displayed: the requirement is "if they wish" not "iff they wish.")
  • Undo: 50 points (Since there is only one possible move, there is only one possible action to undo: also trivial.)
  • Super bot challenge: 150 points (Since I have programmed the computer to always play first, there is no sequence of inputs that can cause it to lose.)
\$\endgroup\$
  • \$\begingroup\$ You rascal... you did it, didn't you! \$\endgroup\$ – Renae Lider Jun 10 '15 at 18:12
  • \$\begingroup\$ If only someone could find a bug that will bring your bot to the knees... Smithers, release the hounds... \$\endgroup\$ – Renae Lider Jun 10 '15 at 18:14
  • \$\begingroup\$ @Renae I did =) I might actually extend this to a 3x3 or 4x4 game if I have time later in the week. The gameplay would still be pretty trivially solved, but it might actually be 'fun' to play (the same way tic-tac-toe is 'fun'). \$\endgroup\$ – 2012rcampion Jun 10 '15 at 18:14
  • \$\begingroup\$ You may choose the size of the grid Invalid because a single cell is not a grid. \$\endgroup\$ – edc65 Jun 10 '15 at 18:54
  • \$\begingroup\$ @edc65 It is a grid... a trivial 1x1 grid, but a grid nonetheless. (If the OP wants to disallow this strategy I assume he will alter or add a requirement. Until then I'm counting it.) \$\endgroup\$ – 2012rcampion Jun 10 '15 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.