用JavaScript实现四子棋算法

Question

如何在四连棋中检查四个相连的棋子？

我不会复制数组的代码，但它基本上是一个长度为42的数组。每个数组元素都保存着绘图的X、Y位置和颜色。

var board_array = [{x:60, y:55, c:"Red"}, // ... and so on

并且看起来像这样：

最初我采用了这种方法。以下是所有可能赢得游戏的不同方式。这不是所有可能的四个连续位置，但所有垂直、水平和对角线获胜的不同方式 - 您仍然需要使用某种嵌套for循环进行检查。

// Winning vertically
wins[0]  = new Array(0, 7,  14, 21, 28, 35);
wins[1]  = new Array(1, 8,  15, 22, 29, 36);
wins[2]  = new Array(2, 9,  16, 23, 30, 37);
wins[3]  = new Array(3, 10, 17, 24, 31, 38);
wins[4]  = new Array(4, 11, 18, 25, 32, 39);
wins[5]  = new Array(5, 12, 19, 26, 33, 40);
wins[6]  = new Array(6, 13, 20, 27, 34, 41);
// Winning horizontally
wins[7]  = new Array(0,   1,  2,  3,  4,  5,  6);
wins[8]  = new Array(7,   8,  9, 10, 11, 12, 13);
wins[9]  = new Array(14, 15, 16, 17, 18, 19, 20);
wins[10] = new Array(21, 22, 23, 24, 25, 26, 27);
wins[11] = new Array(28, 29, 30, 31, 32, 33, 34);
wins[12] = new Array(35, 36, 37, 38, 39, 40, 41);
// Winning diagonally, left to right
wins[13] = new Array(14, 22, 30, 38);
wins[14] = new Array(7, 15, 23, 31, 39);
wins[15] = new Array(0, 8, 16, 24, 32, 40);
wins[16] = new Array(1, 9, 17, 25, 33, 41);
wins[17] = new Array(2, 10, 18, 26, 34);
wins[18] = new Array(3, 11, 19, 27);
//Winning diagonally, right to left
wins[19] = new Array(20, 26, 32, 38);
wins[20] = new Array(13, 19, 25, 31, 37);
wins[21] = new Array(6,  12, 18, 24, 30, 36);
wins[22] = new Array(5,  11, 17, 23, 29, 35);
wins[23] = new Array(4,  10, 16, 22, 28);
wins[24] = new Array(3,   9, 15, 21);

如果你将board_array看作是这样的：

//0  1  2  3  4  5  6
//7  8  9  10 11 12 13
//14 15 16 17 18 19 20
//21 22 23 24 25 26 27
//28 29 30 31 32 33 34
//35 36 37 38 39 40 41

我尝试使用一个三层循环和一个计数器来检查胜利数组与棋盘数组是否匹配，但是没有成功。我想知道是否有更简单的方法。

- jimbo123

---

我的方法是遍历放置的标记。对于每个标记，我向左、右、上、下和对角线方向分别检查3个位置，看它们是否都是相同的颜色。 - Gary Holiday

如果您遇到数组越界类型的错误，该怎么办？ - jimbo123

你需要检查是否越界。从简单的开始，比如只检查是否有垂直赢法。然后将该逻辑应用到水平和对角线上。 - Gary Holiday

你应该绝对采用二维方法：index = y*7+ y。然后只需检查新芯片坐标周围四个可能的方向。 - Bergi

“…但是没有成功” - 到底哪些部分没有按预期工作？请发布您尝试过的代码。 - Bergi

Answer 1

有很多方法可以实现。如果你想摆脱循环，可以使用动态规划算法，在添加硬币时每次计算结果。

为此，您必须保存每个字段的4个值：水平值、垂直值、向左对角线值和向右对角线值。

class Field {
       int horiz;
       int vert;
       int diagLeft;
       int diagRight;
}

一开始，所有的领域都被初始化为0（该领域的所有值）。 如果你往该领域添加一个硬币，可以按以下方式计算出其值：

fields[i][j].horiz = fields[i][j+1].horiz + fields[i][j-1].horiz + 1;
fields[i][j].vert = fields[i+1][j].vert + fields[i-1][j].vert + 1;
fields[i][j].diagLeft = fields[i+1][j+1].diagLeft + fields[i-1][j-1].diagLeft +1;
fields[i][j].diagRight = fields[i-1][j-1].diagRight + fields[i+1][j+1]

如果四个计算值中有一个大于等于4，那么你就获胜了。

对于两个玩家的情况，你可以为每个玩家创建一个场地数组，或者你可以使用正负值。

如果你想避免一直检查边界（i和j），你可以给你的场地添加一个边框（因此你在左边和右边各有一列，在顶部和底部也各有一行）。

- Andreas

---

除非您为每个移动保存整个状态，否则在撤回移动时可能很难维护。 - trincot

谢谢。我没想过这个角度。 - Andreas

Answer 2

"如何最好地检查连接4中的四个棋子？"

我不会声称这是“最好的方法”，但这是一种方法。

忽略UI部分，该过程（有点）简单，每次放置一个计数器时，读取网格并动态创建搜索模式的条带，它们可能包含四个连接。

每行、每列和前后倾斜的对角线条带都是从沿着其每个点找到的颜色的值串联而成的字符串。
将正则表达式应用于条带，以查看是否连续提到了相同的四个计数器颜色（红色或黄色）。

虽然它很循环，但对象非常短，check4Winner()中的第一个嵌套循环（读取网格）收集完成检查所需的所有数据，同时检查获胜连接的行。
接下来的循环循环只检查列和对角线条带，如果没有找到赢家。

未包括的优化（老实说，几乎不值得额外的代码）可以删除十二个对角线条带（每个角落三个），因为它们太短而无需检查。

如果需要导入或导出游戏数据，可以轻松地利用字符串数组的临时对象（用于演示的console.log）。

尽管UI小部件对于查找胜者的算法并不是严格重要的，但是它是根据该算法设计的，并且因此DOM状态是被读取的数据的来源。我故意关闭了片段中的console输出，但是您可以在浏览器控制台中看到通过以这种特定方式读取DOM而生成的数据。

var player = "red";
const players = { "red": "yellow", "yellow": "red" },
  output = document.querySelector( "output" ),
  tbody = document.querySelector( "tbody" ),
  rows = tbody.querySelectorAll( "tr" ),
  prepArray = ( n ) => {
    return Array( n ).fill( "" );
  },
  connect4 = ( strip ) => {
    const rslt = /(?:(red){4}|(yellow){4})/.exec( strip );
    if ( !!rslt ) {
      output.classList.add( rslt[ 1 ] || rslt[ 2 ] );
      return true;
    }
    return false;
  },
  check4Winner = () => {
    var strips = {
          h: [],
          v: prepArray( 7 ),
          f: prepArray( 12 ),
          b: prepArray( 12 )
        },
        strip, color, winner, dir;
    rows.forEach( ( row, ri ) => {
      strip = "";
      row.querySelectorAll( "td" ).forEach( ( cell, ci ) => {
        color = cell.getAttribute( "class" ) || " ";
        strips.b[ ci - ri + rows.length - 1 ] += color;
        strips.f[ ci + ri ] += color;
        strips.v[ ci ] += color;
        strip += color;
      } );
      strips.h.push( strip );
      winner = winner || connect4( strip );
    } );
    
    console.log( strips ); // game data object
    
    for ( dir in strips ) {
      if ( !winner && strips.hasOwnProperty( dir ) ) {
        strips[ dir ].forEach( ( s ) => {
          winner = winner || connect4( s );
        } );
      }
    }
  },
  dropCounter = ( ci ) => {
    var cell, pc;
    rows.forEach( ( row ) => {
      if ( !( pc = row.childNodes[ ci ] ).getAttribute( "class" ) ) {
        cell = pc;
      }
    } );
    if ( cell ) {
      cell.classList.add( player = players[ player ] );
      check4Winner();
    }
  };
output.addEventListener( "click", () => {
  output.removeAttribute( "class" );
  tbody.querySelectorAll( "td" ).forEach( ( c ) => {
    c.removeAttribute( "class" );
  } );
}, false );
tbody.addEventListener( "click", ( evt ) => {
  const trg = evt.target;
  if ( !output.getAttribute( "class" ) && trg.tagName.toLowerCase() === "td" ) {
    dropCounter( trg.cellIndex );
  }
}, false );

table,
output {
  box-shadow: .5vh .5vh 2vh .5vh rgba( 0, 0, 0, .5 );
}
table {
  width: 90vh;
  border-collapse: collapse;
  border: 2vh solid royalblue;
}
td {
  width: calc( 90vh / 7 );
  background: royalblue;
  cursor: default;
  user-select: none;
}
td:before {
  content: "";
  display: block;
  width: calc( 90vh / 7 );
  height: calc( 90vh / 7 );
  border-radius: 50%;
  box-shadow: inset .5vh .5vh 2vh .5vh rgba( 0, 0, 0, .5 );
  background: white;
}
td.red:before {
  background: red;
}
td.yellow:before {
  background: yellow;
}
output {
  position: fixed;
  display: none;
  width: 90vh;
  height: 10vh;
  top: 10vh;
  left: 5vh;
  background: white;
  text-align: center;
  font: 5vh sans-serif;
  line-height: 10vh;
  cursor: pointer;
}
output:before {
  content: attr( class );
}
output.red,
output.yellow {
  display: block;
}

<table><tbody>
  <tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
  <tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
  <tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
  <tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
  <tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
  <tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
</tbody></table>
<output> wins!</output>

顺便说一句，我很喜欢构建这个项目，感谢你的提问 :-)

- Fred Gandt

Answer 3

你可以使用正则表达式。

将游戏表示转换为字符串，并在其上执行正则表达式以查找胜利。

例如，如果一列被字符串化为"121000"，这意味着玩家1在此列中有两个棋子，而玩家2在这两个棋子之间有一个棋子。整个棋盘可以通过连接这样的列字符串来进行字符串化，使用分隔符。例如，

"100000,212121,212000,121211,212100,000000,200000"

给定这样一个字符串，您可以使用以下正则表达式检测胜利：

([12])(\1{3}|(.{5}\1){3}|(.{6}\1){3}|((.{7}\1){3}))

比赛中第一个字符将标识获胜的玩家，因此您甚至不需要知道谁打了最后一步；它会自动跟随。

以下是该想法的实现。我毫不客气地借用了@FredGandt's answer的精美CSS：

const game = {
    reset(onchange) {
        this.columns = Array.from({length:7}, () => Array(6).fill(0)); // 2D array
        this.moveCount = 0;
        (this.onchange = onchange)(-1); // callback that can be used for rendering
    },
    drop(column) {
        let i = this.columns[column].indexOf(0);
        if (i < 0 || this.result() >= 0) return; // cannot move here
        this.columns[column][i] = this.moveCount++ % 2 + 1;
        this.onchange(this.result());
    },
    result() { // 0=draw, 1=yellow wins, 2=red wins, -1=undecided
        return +this.columns.map(col => col.join("")).join()
                    .match(/([12])(\1{3}|(.{5}\1){3}|(.{6}\1){3}|((.{7}\1){3}))/)?.[1]
            || -(this.moveCount < 42);
    }
};

// I/O handling
const container = document.querySelector("#container");
const display = result =>
    container.innerHTML = "<table>" + game.columns[0].map((_, rowNo) =>
            "<tr>" + game.columns.map(column => 
                `<td class="${['', 'yellow', 'red'][column[5-rowNo]]}"><\/td>`
            ).join("") + "</tr>"
        ).join("") + 
        `<\/table><out class="${["nobody", "yellow", "red"][result]??""}"><\/out>`;
container.addEventListener("click", e => 
    e.target.tagName == "TD"  ? game.drop(e.target.cellIndex) 
  : e.target.tagName == "OUT" ? game.reset(display) : null
);
game.reset(display);

/* Taken from @FredGandt's answer */
table,
output {
  box-shadow: .5vh .5vh 2vh .5vh rgba(0, 0, 0, .5);
}
table {
  width: 90vh;
  border-collapse: collapse;
  border: 2vh solid royalblue;
}
td {
  width: calc(90vh / 7);
  background: royalblue;
  cursor: default;
  user-select: none;
}
td:before {
  content: "";
  display: block;
  width: calc(90vh / 7);
  height: calc(90vh / 7);
  border-radius: 50%;
  box-shadow: inset .5vh .5vh 2vh .5vh rgba(0, 0, 0, .5);
  background: white;
}
td.red:before {
  background: red;
}
td.yellow:before {
  background: yellow;
}
out {
  position: fixed;
  display: none;
  width: 90vh;
  height: 10vh;
  top: 10vh;
  left: 5vh;
  background: white;
  text-align: center;
  font: 5vh sans-serif;
  line-height: 10vh;
  cursor: pointer;
}
out:before {
  content: attr(class) " wins";
}
out.red,
out.yellow,
out.nobody {
  display: block;
}

<div id="container"></div>

- trincot