Determining the winning condition for Tic-Tac-Toe [closed]

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
    } 

}

13

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.

1

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.
}

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 3×3 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

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.

Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa Dịch vụ tổ chức sự kiện 5 sao Thông tin về chúng tôi Dịch vụ sinh nhật bé trai Dịch vụ sinh nhật bé gái Sự kiện trọn gói Các tiết mục giải trí Dịch vụ bổ trợ Tiệc cưới sang trọng Dịch vụ khai trương Tư vấn tổ chức sự kiện Hình ảnh sự kiện Cập nhật tin tức Liên hệ ngay Thuê chú hề chuyên nghiệp Tiệc tất niên cho công ty Trang trí tiệc cuối năm Tiệc tất niên độc đáo Sinh nhật bé Hải Đăng Sinh nhật đáng yêu bé Khánh Vân Sinh nhật sang trọng Bích Ngân Tiệc sinh nhật bé Thanh Trang Dịch vụ ông già Noel Xiếc thú vui nhộn Biểu diễn xiếc quay đĩa Dịch vụ tổ chức tiệc uy tín Khám phá dịch vụ của chúng tôi Tiệc sinh nhật cho bé trai Trang trí tiệc cho bé gái Gói sự kiện chuyên nghiệp Chương trình giải trí hấp dẫn Dịch vụ hỗ trợ sự kiện Trang trí tiệc cưới đẹp Khởi đầu thành công với khai trương Chuyên gia tư vấn sự kiện Xem ảnh các sự kiện đẹp Tin mới về sự kiện Kết nối với đội ngũ chuyên gia Chú hề vui nhộn cho tiệc sinh nhật Ý tưởng tiệc cuối năm Tất niên độc đáo Trang trí tiệc hiện đại Tổ chức sinh nhật cho Hải Đăng Sinh nhật độc quyền Khánh Vân Phong cách tiệc Bích Ngân Trang trí tiệc bé Thanh Trang Thuê dịch vụ ông già Noel chuyên nghiệp Xem xiếc khỉ đặc sắc Xiếc quay đĩa thú vị
Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa
Thiết kế website Thiết kế website Thiết kế website Cách kháng tài khoản quảng cáo Mua bán Fanpage Facebook Dịch vụ SEO Tổ chức sinh nhật