C++

Forum

 
Tictactoe

pacman169 (374)
Hello,

I really haven`t programmed much lately because just finishing my college, anyway here was my project some weeks ago:

Write a tic-tac-toe - using a bitboard to represent the choices.

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
#include <iostream>
#include <bitset>

class TicTacToe
{
public:

  void newGame()
  {

    struct bitboard
    {


   enum { N = 3 } ;
   bitset<N*N>board ;

   enum player_t { PLAYER_X = 'X', PLAYER_O = 'O', AVAILABLE=0 };

   static inline size_t offset( col_t col, int row )
     { return col*N + row ; }

    }

  }


   void play()
   {

       for (int turns = 0; turns < 9; ++turns)          

       char player = ( PLAYER_X : PLAYER_O);
       bool legal=false;
       int Square= 0;

       cout << "\nPlayer " << player << " -- Choose a move..." << std::endl;
       cout << "Enter row and col (e.g. 1 2): ";
       cin  >> row >> col;


   bool getSquare(board, int square_num)

   {

   return (board & (1 <<square_num));

   }

  void Square_state (int square_num)
  {

  in_use = (board ^ (0 <<square_num));

  }

  if(! in_use) { bool legal=true; }

  }



Actually I`m quite uncertain how to continue/ what areas of programming I`m

missing here beside bitboards so any suggestions how I could improve my

skills here would be welcomed... Maybe I need to learn data structures first?

JLBorges (13770)
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
#include <iostream>
#include <bitset>

namespace tictactoe
{
    constexpr std::size_t N = 3 ;
    using board = std::bitset<N*N> ;

    const board wins[] = {
                             board("111000000"), board("000111000"), board("000000111"), // rows
                             board("100100100"), board("010010010"), board("001001001"), // cols
                             board("100010001"), board("001010100") // diagonals
                         } ;

    board noughts ; // bit board for first player
    board crosses ; // bit board for second player

    constexpr char NOUGHT = 'O' ;
    constexpr char CROSS = 'X' ;
    bool curr_move_noughts = true ;

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

    bool valid( std::size_t row, std::size_t col ) { return row<N && col<N ; }
    std::size_t pos( std::size_t row, std::size_t col ) { return row*N + col ; } // map row, col to bit position

    bool occupied( std::size_t row, std::size_t col ) { return valid(row,col) && combined()[ pos(row,col) ] ; }
    bool free( std::size_t row, std::size_t col ) { return valid(row,col) && !occupied(row,col) ; }

    void make_move( std::size_t row, std::size_t col, board& b ) { if( free(row,col) ) b[ pos(row,col) ] = true ; }
    void make_move( std::size_t row, std::size_t col )
    { if(curr_move_noughts) make_move(row,col,noughts) ; else make_move(row,col,crosses) ; }

    bool is_win( board b )
    {
        for( board w : wins ) if( (w&b) == w ) return true ;
        return false ;
    }
    bool is_win() { return is_win( curr_move_noughts ? noughts : crosses ) ; }

    std::ostream& print_board( std::ostream& stm = std::cout, board b = combined() )
    {
        stm << "------\n" ;
        for( std::size_t i = 0 ; i < N ; ++i )
        {
            for( std::size_t j = 0 ; j < N ; ++j )
            {
                const std::size_t k = pos(i,j) ;
                if( b[k] ) stm << ( noughts[k] ? NOUGHT : CROSS ) << ' ' ;
                else stm << ". " ;
            }
            stm << '\n' ;
        }
        return stm << "------\n" ;
    }
}

int main()
{
    using namespace tictactoe ;

    make_move(1,2) ;
    print_board() ;
    curr_move_noughts = !curr_move_noughts ;

    // for testing: let the same player make three consecutive moves
    make_move(2,0) ; make_move(1,1) ; make_move(0,2) ;
    print_board() ;
    std::cout << "win? " << std::boolalpha << is_win() << '\n' ;
}

http://coliru.stacked-crooked.com/a/48cae935c428c00d

Take it up from there.
pacman169 (374)
Really nice, though there are some points I need to make.

1) I find it more teaching to write my own code and then move on after having done something that works rather than trying to figure out how should I improve someone elses code to serve my purposes.

2) When thinking about that, couldn`t I implement line 9 differently?

I found a function to check if a player has a winning board for a connect four game

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 

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



If you can explain me the above function, I can try to implement the function for a tic-tac-toe game.


Cheers

JLBorges (13770)
> I find it more teaching to write my own code

So do that, assuming that now, you know how bitboards could be used.


> If you can explain me the above function

I can't; I've no idea what the bitboard representation is or what that particular game is.
In any case, I wouldn't fancy looking at code with (uncommented) magic numbers liberally sprinkled all over the place.
pacman169 (374)
Ok, I don`t undrstand all but I will try to do my best.

Starting from line 39:

bool is_win() { return is_win( curr_move_noughts ? noughts : crosses ) ; }

Comment // win becomes nought if current move is nought and crosses otherwise.

Line 41 is mysterious and

1
2
3
4
5
 
 bool is_win( board b )
    {
        for( board w : wins ) if( (w&b) == w ) return true ;
        return false ;
    }


I don`t understand.
Last edited on
JLBorges (13770)
> bool is_win() { return is_win( curr_move_noughts ? noughts : crosses ) ; }
> Comment // win becomes nought if current move is nought and crosses otherwise.

There are two bitboards: one containing bits set for noughts and the other containing bits set for crosses.
If the player who has just moved is noughts, check for a win in the bitboard for noughts;
otherwise check for a win in the bitboard for crosses.


> Line 41 is mysterious

std::ostream& print_board( std::ostream& stm = std::cout, board b = combined() )

Print a bitboard.
The default is print to stdout: std::ostream& stm = std::cout
The default board to be printed is the combined bitboard. board b = combined()
The combined bitboard board combined() { return noughts | crosses ; } has bits set for both noughts and crosses.


> I don`t understand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
bool is_win( board b ) // check for a win in board b
{
    // the array wins[8] has bitboards with bits set for each win possibility 
    // each of the (three rows, three cols, and two diagonals)
    
    for( board w : wins ) // for each win possibility 
        if( (w&b) == w ) return true ;
        // if the bitwise AND of the bitboard b and the win possibility w is equal to w
        // then the board has all the bits set for that win possibility; it is a win
        // eg. 010111001 & 000111000 == 000111000
        //          b    &      w    ==      w       (the check for row two)

    return false ; // no win was found
}

pacman169 (374)
Nice, I think I have another idea how wins could be checked. Now, however, the question is

do I really want to use bitboards, when considering more complex applications.

Here is something that I put together:

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
42
43
44
45
46
47
48
49
50
51
52
53
54
 

#include <iostream>
#include <matrix.h>

namespace tictactoe

{
    constexpr size_t row = 3 ;
    constexpr size_t column = 3; 
    constexpr char NOUGHT = 'O' ;
    constexpr char CROSS = 'X' ;
    bool curr_move_noughts = true ; 

   void board()

   {
        void init(Matrix<int,2>&a)
              {
                for (int r=0; r<a.3 ++r)
                for (int c=0; c<a.3 ++c)
              }
  }


void play()

  {

for (int turns = 0; turns < 9; ++turns) { turns % 2 == 0 ? CROSS : NOUGHT }


 bool valid( size_t row, size_t col ) { return row<3 && column<3 ; }

}


 bool checkwin(char player) {

  if (board a(2,0)==player && board a(1,1)==player && board a(0,2)==player)

     return true;                                                   

   if (board a(2,0)==player && board a(2,1)==player && board a(2,2)==player)

     return true;                                                  

  if (board a(2,0)==player && board a(1,0)==player && board a(0,0)==player)

  return              true;                                                                                                

 }

bool is_win() { return is_win( curr_move_noughts ? noughts : crosses ) ; }



I have a book that contains the matrix library, so I thought that would be easier to understand now for starters.

Topic archived. No new replies allowed.