-1

I'm writing a tic-tac-toe game in C++ and now I found a function to check if a player has a winning board for a connect four game.

The function looks like this:

bool haswon(int64_t board)
{
    int64_t y = board & (board >> 7);
    if (y & (y >> 2 * 7)) // check \ diagonal
        return true;
    y = board & (board >> 8);
    if (y & (y >> 2 * 8)) // check horizontal -
        return true;
    y = board & (board >> 9);
    if (y & (y >> 2 * 9)) // check / diagonal
        return true;
    y = board & (board >> 1);
    if (y & (y >> 2))     // check vertical |
        return true;
    return false;
}

I would be looking for an explanation of the above function.

Then I could perhaps try to implement the same thing for my tic-tac-toe. I'm fairly OK with the bitwise operators

#include <iostream> 
#include <bitset> 

namespace tictactoe { 

    constexpr std::size_t N = 3;

    using board = std::bitset<N*N>;

    constexpr char NOUGHT = 'O'; 
    constexpr char CROSS = 'X';

    bool curr_move_noughts = true;

    board combined() { 
        return noughts | crosses;    // combined bit board for both players
    } 

}

closed as unclear what you're asking by user40980, Doc Brown, user53019, Robert Harvey, user22815 Nov 22 '14 at 7:46

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 5
    Urk! I would avoid that! If I guess correctly, the programmer is using the 64 bits in "board" to represent the 64 squares on an 8x8 connect 4 board, 1 bit for each and doing some fancy bit shifting. It is efficient; it is the sort of thing I would have done 30 years ago, but on today's PCs, you an afford to declare a two dimensional array to represent your board. That will make your code much easier to read, test and maintain. Start from scratch, then post what you have and we will help you. – Mawg Nov 20 '14 at 12:11
  • As Mawg's comment implies, this question is unanswerable if you do not know or do not tell what board is supposed to contain. – Jan Doggen Nov 20 '14 at 12:12
  • 2
    @coder111: you hate it because you misunderstood it. PSE is not a discussion forum, it is an Q & A site. When you want to add something to your question, don't post it here as a comment, instead edit your original question (but please, don't just throw the code above into your question without telling us in plain, clear english what you want to know about it). – Doc Brown Nov 20 '14 at 12:51
  • 2
    "An array doesnt know its size" - you can declare fixed size arrays. As to "significant" slowing, when your CPU executes billions of instructions per second, that will no be "significant". Don't worry about it, no human could ever notice your program "thinking" :-) – Mawg Nov 20 '14 at 12:59
  • 3
    First, implement the function without any bit twiddling tricks. Ideally, don't even implement it as a bitset. When you understand the underlying logic how it works, then consider if there is a bit hack that can apply to the code though consider that you shouldn't try being clever. "Everyone knows that debugging is twice as hard as writing a program in the first place. So if you're as clever as you can be when you write it, how will you ever debug it?" - Brian Kernighan. – user40980 Nov 20 '14 at 16:08
14

The pure fact you don't understand this function should be a big warning sign not to implement your Tic-Tac-Toe winning test in a similar manner. If you do, you will probably not understand your own code in a few weeks any more.

Instead, use a two-dimensional array or vector, and some loops to check the winning conditions. And don't think too much about speed or memory space as long as you don't experience any significant, measurable bottlenecks.

  • 2
    And document your code, use meaningful variable names, make it maintainable, write automated unit tests, and keep it in a version control system. Happy coding! – Mawg Nov 20 '14 at 13:01
4

Using bits to represent a Tic-Tac-Toe board is perfectly fine and is as easy and maintainable as using two dimensional array. Since there are only 8 possibilities for winning condition, you can just check the board against every cases.

1 0 0       0 1 0      0 0 1     1 1 1    0 0 0
1 0 0       0 1 0      0 0 1     0 0 0    1 1 1
1 0 0       0 1 0      0 0 1     0 0 0    0 0 0

0 0 0       1 0 0      0 0 1
0 0 0       0 1 0      0 1 0
1 1 1       0 0 1      1 0 0

To keep the clean-ness of the code, try to abstract the implementation of the board away from the your game logic. It is easier to change the board implementation later if you dislike the bitboard representation.

class Board
{
    private:
        uint32_t board;

    public:
        Board() { board = 0; }

        /* Check if there is any of our piece
           placed in this (x, y) location */
        bool Check(int x, int y) {
            return (board & (1 << y * 3 + x)) > 0;
        }

        /* Make a move in this (x, y) location */
        void Move(int x, int y) {
            board = board | (1 << y * 3 + x);
        }

        /* Check if we have won */
        bool IsWin()
        {
            return (board & 292) == 292 || (board & 146) == 146 ||
                   (board & 73) == 73 || (board & 448) == 448 ||
                   (board & 56) == 56 || (board & 7) == 7 ||
                   (board & 273) == 273 || (board & 84) == 84;
        }
};

Keep two boards for player 1 and player2.

Board player1;
Board player2;

Check if (x, y) location is unoccupied

if (!player1.Check(x, y) && !player2.Check(x, y)) {
    // unoccupied slot
}

Check if player 1 has won

if (player1.isWin()) {
    // player 1 has won.
}
3

Think of it as a binary number where all the ones are your pieces. To simplify my explanation, I'll just consider one row of 8. The rest all work similarly.

Consider a winning case of four in a row: 11110000. board && (board >> 1) gives you 1110000, which is all the ones with a one immediately adjacent to the left. Doing this again with y & (y >> 2) does the same check, but for two to the left. The combination of the two yields a non-zero value when you get four in a row.

The other offsets do the same thing, but wrapping to the next row instead of checking immediately adjacent squares. 8 wraps immediately below, 7 wraps below but one to the left, and 9 wraps below but one to the right.

This happens to be possible because of the powers of two involved. In a 3x3 grid you can't do something similar. You can use it to check for two in a row or four in a row, but not three.

That being said, even if the bit-shifting did work for tic-tac-toe, you shouldn't use it. Connect four has 4,531,985,219,092 possible games, so it makes sense to optimize this function as much as possible, to be able to compute a deeper tree in a reasonable time, even if that means sacrificing some readability. Tic-tac-toe has only 255,168 possible games, which means you can recalculate every combination on every move in a naïve way, and still have time to spare. In such cases, readability should be paramount.

There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies.

—Turing award winner Tony Hoare

The reason you don't optimize when you don't have to is the bugs are no longer obvious. For example, the following board is incorrectly reported as a win:

10000001
00000010
00000100
00000000
00000000
00000000
00000000
00000000
  • 1
    In fact, the false positive in the last position should not happen because only 7 columns are used in connect four. The leftmost column and the top 2 rows should always be empty. So there is no wrapping around. But you are right to warn about it because coder111 proposes a bitset of 3*3 bits. Without an additional empty column, that problem can happen. – Florian F Nov 22 '14 at 2:04
2

Forget that connect 4 function. Apart from being unnecessarily cryptic, checking for a win in connect 4 is more complex than in tac-tac-toe.

In tic-tac-toe there are eight lines to check for - three rows, three columns and two diagonals. The first thing I'm going to suggest is using a single-dimensional array for the board, so the array indexes are as follows...

+---+---+---+
| 0 | 1 | 2 |
+---+---+---+
| 3 | 4 | 5 |
+---+---+---+
| 6 | 7 | 8 |
+---+---+---+

The reason for using a two-dimensional array would be to make it easier to identify locations and easier to loop over them. In this case, I'm going to argue that because the board is so small, it's actually easier to avoid the two dimensions issue. I'm also going to avoid loops, at least for a first attempt, since the scale of the problem is small enough to allow that. So...

bool line_is_full (Board* p_board, char p_player, int p1, int p2, int p3)
{
  return (   (p_board [p1] == p_player)
          && (p_board [p2] == p_player)
          && (p_board [p3] == p_player));
}

bool board_has_win (Board* p_board, char p_player)
{
  return (   line_is_full (p_board, p_player, 0, 1, 2)
          || line_is_full (p_board, p_player, 3, 4, 5)
          || line_is_full (p_board, p_player, 6, 7, 8)

          || line_is_full (p_board, p_player, 0, 3, 6)
          || line_is_full (p_board, p_player, 1, 4, 7)
          || line_is_full (p_board, p_player, 2, 5, 8)

          || line_is_full (p_board, p_player, 0, 4, 8)

          || line_is_full (p_board, p_player, 2, 4, 6));
}

Only checking for one player winning is valid because the only player you need to check for is the player who has just made a move. I'm also not checking for a draw here - just keep count of how many moves have been made to handle that.

Obvious things that could be improved...

  1. The blank lines in board_has_win are there to emphasize groups of similar cases. You could have a loop over the three rows and a loop over the three columns.

  2. Alternatively, board_has_win is an "unwound" loop over all eight lines. There are several ways this could be expressed using a loop. Possibly the most sensible is to have a data table (giving the three cell numbers for each of the eight lines), so you can directly loop over the eight lines.

  3. line_is_full could obviously be rewritten as a loop over the three cells if only those cells were passed as an array.

  4. Alternatively, for each line (given the way I've specified them), (p2-p1) == (p3-p2) - there's a constant stepping distance between cells. Also (p1+p3)/2 == p2 - the position of the middle cell is the average of the two end cells. That means given any two cells (provided you know which two) you can determine the first and the stepping distance and loop over all three.

Personally I'd ignore points 3 and 4 - having a loop rather than three cases isn't really worth even that small amount of extra complexity. I'd probably focus on point 2 - that table of cell-numbers for each row could have other uses in the program.

Here's a tip I think I first saw back in ye olden days when computer magazines would print listings in BASIC. Each of the lines has three cells. What happens if you assign O the value 1 and X the value 4 (and zero for empty)? Consider the total of the values for the three cells in a line - here's a table...

 0 .... All three cells empty
 1 .... One O, two empty cells
 2 .... Two Os, one empty cell
 3 .... Three Os - O wins

 4 .... One X, two empty cells
 5 .... One X, one O, one empty cell
 6 .... One X, two Os
 7 .... Impossible

 8 .... Two Xs, one empty cell
 9 .... Two Xs, one O
10 .... Impossible
11 .... Impossible

12 .... Three Xs - X wins
13+ ... Impossible

This is a kind of special-case hash table. This is useful not only for spotting a win but also for a very simple AI.

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