As of today, there is one week remaining before the final submission deadline. I would like to encourage participants to submit their AIs early so that I can run trial rounds before the final tournament. If you submit an AI ahead of time, you can view the results of trial matches and see how your AI responds to different strategies. Participants are allowed to continue making submissions until the deadline of December 5th at 11:59:59pm ET.

Good luck to everyone involved. Very Happy
And now you have fewer than three days to complete your AI! If you haven't started yet, the problem is still tractable to solve in the time remaining, and if you have started, remember to upload your AI ahead of time if possible. Good luck to all of the participants!
The official TI-BASIC Connect Four AI Challenge winner is:

JWinslow23

Thank you for you participation, and congratulations on your accomplishment.
Congratulations for winning, JWinslow23! Can you (or he) tell us more about his solution, and how it worked? How was its performance?
KermMartian wrote:
Congratulations for winning, JWinslow23! Can you (or he) tell us more about his solution, and how it worked? How was its performance?

and when will the official game (utilizing the AI) be released?
...wait...already? Wow, I guess nobody else entered Razz

But yeah, how it was SUPPOSED to work was that it was supposed to check each column you can move in for a move to make that will build the most lines of your own pieces, and block the most lines of the other player's pieces.

How it DID work is...I dunno, but not that. My BASIC programming isn't the best. Sad
Now that the contest is over, I'd be interested to see both JWinslow23's source and yours, jonbush. Even though my approach didn't work out the first time, I think I may be able to rework it.

Here was an outline of my strategy:

I. Store a complete opening book of the optimal move in every reachable 6-ply position, and (as second player) every 7-ply position where the first player moved in the center.

The AI would make the same moves every time, so it only needs to store the *opponent's* possible moves. As first player going up to 6 ply, there are 3 opponent plies, so the AI would need to store 7^3 = 343 positions. Symmetries (first player always goes in the center, so the board can be flipped) cut this down to 4*7^2 = 196 positions.

As second player going to 5 ply, the same is true. Symmetries also work, since moves 5, 6, 7 are the same as 3, 2, 1.

As second player in a 7 ply position, no symmetries can be used, so 343 positions need to be stored.

Thus, in total, we need to store 735 positions, which is well within the 2000-byte budget, even without compression.

II. After the opening, use minimax to 3 ply, with a complicated heuristic function as well as checking for forced wins 1 and 2 ply past that (that is, on your opponent's second and your third move after the current board position).

The heuristic function would value the following:

* Winning; blocking. That is, placing a piece in a threat square.
* Not losing. Placing a piece in a space directly below a threat either loses or gives up your win.
* Placing the piece near the center of a board. Except for vertical 4s, all 4s in a row use a spot in the center board; therefore, the center spots are most valuable.
* Making threats and blocking the opponent from making threats.
* Making threats of the correct parity; on squares that you're likely to get. Similarly blocking opponents' threats of the correct parity.
* Making pairs and blocking opponents from making pairs.
* If I ever find out how to, some of the more advanced strategies like "control of zugzwang".

I didn't think about pruning, because (a) I have no idea how to do it yet, and (b) the initial time limit was 1 minute in the worst case, not the average case.

III. To get the required speed, precomputation is key. Things to be computed on the initial board:

* The heights of each column
* A list of "threats" (3s in a row capable of being extended to 4s)
* A list of "pairs" (2s in a row capable of being extended to 4s)
* Which squares are most likely to go to which player, using parity.

IV. Similarly to the concept of bitboards allowing fast computation on ordinary computers, I came up with the idea of digitboards—two-dimensional boards represented using one-dimensional lists. In a digitboard, each column is stored in one element of a list, and the digits in that number represent the different spaces in that column. For example, the number 0001211 could represent a column with player 2 in the 3rd row, and player 1 in rows 1, 2, and 4.

Different sketches of my idea used between one and eight digitboards. I'm not sure what the correct number is, and I'll probably be unable to find out until I write the code.

There were a few more ideas, but I'm not sure if they'll work / tried them out and had poor performance.

I implemented some of these strategies in Python, but not yet in TI-BASIC. TI-BASIC is difficult to write efficient code in, so I think before I write any TI-BASIC I'll study the source code of Velena and jonbush's program some.
I had several more complex AIs at one time, but here is the source for what I used for the challenge:

Code:
If N=1
Then
   4->Y
   Return
End
If N=2
Then
   If 0=[A](1,3
   Then
      3->Y
      Return
   End
   If 0=[A](1,5
   Then
      5->Y
      Return
   End
End
ClrList L1
7->dim(L1
[[3,4,5,7,5,4,3][4,6,7,10,7,6,4][5,8,11,13,11,8,5][5,8,11,13,11,8,5][4,6,7,10,7,6,4][3,4,5,7,5,4,3]]->[D]
[A]->[B]
1+(1=Z)->T
For(Y,1,7
   1+Sigma(0!=[B](A,Y),A,1,6->H
   If H<7
   Then
      [D](H,Y->L1(Y
      Y->K
      Z->P
      prgmCAICHECK
      If W
      Return
      T->P
      prgmCAICHECK
      If W
      Return
      If H<6
      Then
         H+1->H
         prgmCAICHECK
         If W
         ~100+L1(Y->L1(Y
         Z->P
         prgmCAICHECK
         If W
         ~50->L1(Y
      End
      Else
      ~1000->L1(Y
   End
End
max(L1->B
ClrList L2
For(A,1,7
   If B=L1(A
   A->L2(1+dim(L2
End
L2(randInt(1,dim(L2->Y


Code:
1->W
0->C
For(A,Y+1,7
   If P=[B](H,A
   Then
      C+1->C
      Else
      8->A
   End
End
For(A,Y-1,1,~1
   If P=[B](H,A
   Then
      C+1->C
      Else
      0->A
   End
End
C->L
If C>2
Return
0->C
For(A,H+1,6
   If P=[B](A,Y
   Then
      C+1->C
      Else
      7->A
   End
End
For(A,H-1,1,~1
   If P=[B](A,Y
   Then
      C+1->C
      Else
      0->A
   End
End
C+L->L
If C>2
Return
0->C
H->A
Y->B
While A<6 and B<7
   A+1->A
   B+1->B
   If P=[B](A,B
   Then
      C+1->C
      Else
      7->A
   End
End
H->A
Y->B
While A>1 and B>1
   A-1->A
   B-1->B
   If P=[B](A,B
   Then
      C+1->C
      Else
      0->A
   End
End
C+L->L
If C>2
Return
0->C
H->A
Y->B
While A<6 and B>1
   A+1->A
   B-1->B
   If P=[B](A,B
   Then
      C+1->C
      Else
      7->A
   End
End
H->A
Y->B
While A>1 and B<7
   A-1->A
   B+1->B
   If P=[B](A,B
   Then
      C+1->C
      Else
      0->A
   End
End
C+L->L
If C>2
Return
0->W


The basic strategy is:
▪Move in the center for the first move, or in column 3 for the second move (not necessarily the best)
▪Block any winning positions for the other player
▪Take any winning positions for the current player
▪Aggressively avoid moving in a column where the position above is a winning position for the other player
▪Avoid moving in a column where the position above is a winning position for the other player
▪Don't move in a filled column
▪Take the move where the most lines could be made (using the table)
▪Take the only possible move
Let's call the first player White, and the second player Black.

jonbush, that's pretty much what I had in mind, but then I thought about all of those rules in "Expert Play in Connect Four" and the VICTOR thesis. I was going to optimize it for speed to try to apply your rules 3 ply ahead, but I didn't see the point. I don't know how to apply parity rules either. Take the position:


Code:

D1 d2 D3 d4 D5 e1 B1 a1 E2 b2 E3 e4 A2 b3 B4 b5 D6


That's Joseki 8 from Expert Play. See here for the link. If Black plays a3 or e5, White has only one winning move: the other square. That doesn't look like it has *anything* to do with preserving his odd threat, or fighting an even threat by White * , and neither does the D6 that White played before. So I don't know how I can apply parity rules. The other thing that concerns me: If I have the ability to make an Even Threat as White, I won't pass it up. One threat is better than none; the only situation in which valuing an odd threat would help would be when I need to choose between an odd and even threat. But I don't see that happening often.

Now let's take the position after a3 E5: White can do literally anything except give up his own threat at c3/f3/g3, and win. So that's why I don't see looking ahead to win/block being helpful: usually at the endgame, you've either won or not. It seems uncommon to me to have a tactical situation in the middlegame where one player might have a double threat, which is when it would help.

I may just not understand it well, but it seems difficult to make an AI that takes even basic parity rules into account.

Finally, how fast does that test AI run? How fast do your current best AIs run?

* On second thought, maybe it prevents Black from getting an even threat on row 6. I still don't know what that would do, though, because doesn't an odd threat by White beat an even threat by Black?
(Sorry for the necro-post)
I wished I had participated to that contest...too bad!
Yesterday I've written my version of Connect4 in TI-Basic too , for TI-z80 models.
I opimised my program then achieved 3 seconds for the TI to think (time on my TI-84 Pocket.fr)



If you are interested, here is the link : https://tiplanet.org/forum/archives_voir.php?id=869728 Wink
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 2 of 2
» All times are UTC - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement