admin管理员组

文章数量:1402560

What is the best way to check 4 in a row in connect 4?

I won't copy the code for the array but it is basically an array of length 42. Each array element holds the X, Y position for drawing and the color

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

and looks like this:

Initially I took this approach. Here are all the different possible ways someone can win the game. It's not all the possible 4 in a row positions but all the different ways someone can win vertically, horizontally and vertically - you still need to check using some sort of nested for loop

// 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);

If you think of the board_array as this:

//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

I used a 3-layer for loop and a counter to check wins array against board_array but to no avail. I just wondered if there is a simpler way.

What is the best way to check 4 in a row in connect 4?

I won't copy the code for the array but it is basically an array of length 42. Each array element holds the X, Y position for drawing and the color

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

and looks like this:

Initially I took this approach. Here are all the different possible ways someone can win the game. It's not all the possible 4 in a row positions but all the different ways someone can win vertically, horizontally and vertically - you still need to check using some sort of nested for loop

// 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);

If you think of the board_array as this:

//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

I used a 3-layer for loop and a counter to check wins array against board_array but to no avail. I just wondered if there is a simpler way.

• javascript
• algorithm
• pseudocode

Share Improve this question Follow edited Jul 5, 2017 at 22:07 Erazihel 7,61566 gold badges3434 silver badges5656 bronze badges asked Jul 5, 2017 at 22:06 jimbo123jimbo123 28733 gold badges77 silver badges1414 bronze badges 5

• 1 My approach would be to loop through token placed. For every token I look to the left 3, right 3, up 3, down 3 and diagonal in every direction 3. I would check to see if they were all the same color. – Gary Holiday Commented Jul 5, 2017 at 22:20
• What if you get array out of bounds types of errors – jimbo123 Commented Jul 5, 2017 at 22:28
• You would have to check for going out of bounds. Start with something simple like only checking if there is a vertical win. Then apply that logic to a horizontal. Then diagonal. – Gary Holiday Commented Jul 5, 2017 at 22:37
• You should definitely use a two-dimensional approach: index = y*7+ y. Then just check the four possible directions around the coordinate of the new chip. – Bergi Commented Jul 6, 2017 at 8:30
• "…but to no avail" - what exactly did not work as expected? Please post the code you tried. – Bergi Commented Jul 6, 2017 at 8:31

Add a ment  | 

3 Answers 3

Sorted by: Reset to default 2

There are a lot of ways to do so. If you want to get rid of the loops, you can use a dynamic-programming-algorithm and calculate the result every time you add a coin.

To do so you must save 4 values per field: horizontal-, vertical-, diagonally-left- and diagonally-right-value

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

At the beginning, all fields are initialized with 0 (all values of the field). If you add a coin to Field, you can calculate the values like that:

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]

If one of the four calculated values is >= 4, you have a winner.

To handle two player, you can either make a field-Array for each player, or you can use positive and negative values

If you want to avoid checking the bounds (i and j) all the time, you can add a border to your field (so you have left and right one additional column and at the top and at the bottom one additional row)

"What is the best way to check 4 in a row in connect 4?"

I wouldn't claim that this is "the best way", but it is a way.

Mostly ignoring the UI gubbins, the process is (somewhat) simply to read the grid each time a counter is dropped in a dynamically created search pattern of strips which could contain a connection of four.

Each row, column and forward and backward leaning diagonal strip is a string concatenated from the values of the color found at each point along it.
The strips are tested against a simple RegEx to see if the same four counter colors (red or yellow) are mentioned consecutively.

Although it's quite loopy, the objects are trivially short, and the first nested loop(s) in check4Winner() (which reads the grid) collates all the data needed to finish checking whilst simultaneously checking the rows for winning connections.
The following loop of loops checks the columnal and diagonal strips only if a winner hasn't been found.

An optimization not included (hardly worth the extra code to be honest) could be to remove twelve diagonal strips (three in each corner) it is unnecessary to check, as they're too short.

If it were desired to export or import game data, the temporary object of arrays of strings (being console.logged for demo) could be easily utilized.

The UI gubbins, although not strictly important regarding the algorithm to find a winner, was designed with the algorithm in mind, and as such the state of the DOM is the source of the data being read.
I purposefully turned off the console output in the snippet, but you can see in your browser's console the data generated by reading the DOM (in this specific way).

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>

P.S. I enjoyed building this, so thanks for asking :-)

You could use a regular expression.

Convert the game representation to a string and perform a regular expression on it to find a win.

If for instance a column is stringified as "121000", it means that player 1 has two discs in this column, and player 2 has one disc in-between those two. The whole board could be stringified by concatenating such column strings, using a separator. For instance,

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

Given such a string, you can detect a win with this regular expression:

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

The first character of the match will identify the player that wins, so you don't even need to know who played the last move; it follows.

Here is an implementation of that idea. I shamelessly borrowed the wonderful CSS of @FredGandt's answer:

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>

本文标签： Connect 4 algorithm in javascriptStack Overflow