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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
namespace Game
{
    public class ConnectFour
    {
        public long[] bitboards;
        public int[] heights;
        public int counter;
        public List<int> moves;

        public ConnectFour()
        {
            bitboards = [0, 0];
            heights = [0, 7, 14, 21, 28, 35, 42];
            counter = 0;
            moves = [];
        }

        public void Play(int column)
        {
            bitboards[counter & 1] ^= 1 << heights[column];

            moves.Add(column);

            heights[column] += 1;
            counter += 1;
        }

        public virtual void Undo()
        {
            counter -= 1;
            
            int prev = moves.ElementAt(counter);
            moves.RemoveAt(counter);

            heights[prev] -= 1;

            bitboards[counter & 1] ^= 1 << heights[prev];
        }

        public bool HasWon()
        {
            int[] directions = [1, 7, 6, 8];
            long current = bitboards[counter & 1];

            foreach (int direction in directions)
            {
                long bb = current & current >> direction;

                if ((bb & bb >> 2 * direction) != 0)
                {
                    return true;
                }
            }
            
            return false;
        }

        public List<int> NextMoves()
        {
            List<int> moves = new();

            for (int i = 0; i < 7; i++)
            {
                if (heights[i] < 7 * (i + 1) - 1)
                {
                    moves.Add(i);
                }
            }

            return moves;
        }

        public override string ToString()
        {
            List<string> board = [];

            for (int i = 0; i < 6; i++)
            {
                var line = "";

                for (int j = 0; j < 7; j++)
                {
                    long sq = 1;
                    sq <<= j * 7 + i;

                    if ((bitboards[0] & sq) != 0)
                    {
                        line += "1 ";
                    }
                    else if ((bitboards[1] & sq) != 0)
                    {
                        line += "2 ";
                    }
                    else
                    {
                        line += ". ";
                    }
                }

                board.Add(line);
            }

            board.Reverse();

            return string.Join('\n', board);
        }
    }

    public class Position : ConnectFour
    {        
        public static int[] maxHeights = [6, 13, 20, 27, 34, 41, 48];

        public Position FullCopy()
        {
            // Instantiate a new Position class
            Position copy = new();

            // Copy the bitboards
            Array.Copy(bitboards, copy.bitboards, 2);
            
            // Copy the moves
            copy.moves = new List<int>(moves);

            // Copy the counter
            copy.counter = counter;

            // Return the copy
            return copy;
        }

        public Position Copy()
        {
            // Instantiate a new Position class
            Position copy = new();
            
            // Shallow copy the class by only bothering to copy the state
            // of both bitboards and the counter, as these are the bare
            // minimum for playing a game of Connect Four. (The counter
            // is needed to know whose turn it is on the board.)
            copy.bitboards = [bitboards[0], bitboards[1]];
            copy.counter = counter;
            
            // Return the copy
            return copy;
        }

        public bool CanPlay(int column)
        {
            return heights[column] < maxHeights[column];
        }

        public bool CanWin(int column)
        {
            // Shallow copy the board and play the move
            Position copy = Copy();
            copy.Play(column);

            // Get whether or not someone has won
            bool hasWon = copy.HasWon();

            // Return the result of whether or not there is a winner
            return hasWon;
        }

        // Override the Undo function to prevent it from editing
        // the moves list (raises errors because shallow copy
        // of the instance doesn't include move history) 
        public override void Undo()
        {
            counter -= 1;
            
            int prev = moves.ElementAt(counter);
            moves.RemoveAt(counter);

            heights[prev] -= 1;

            bitboards[counter & 1] ^= 1 << heights[prev];
        }
    }
}