Connect 4 four-in a row test

Forum Attachments

Summary:

My algorithm takes too long (~15 sec) Tests for a 4 in a row (vertically, horizantally, or diagonally) of either 1 or negative 1 in 6x7 matrix A, and if there is such an occurrence, outputs 1 or -1 in theta. If there is no such occurrence, it does nothing.

Connect 4 four-in a row test

TI-GBR 12 Oct 2015 17:37

My algorithm takes too long (~15 sec)
Tests for a 4 in a row (vertically, horizantally, or diagonally) of either 1 or negative 1 in 6x7 matrix A, and if there is such an occurrence, outputs 1 or -1 in theta. If there is no such occurrence, it does nothing and theta remains equal to zero.

I have already optimized it greatly, but it still take too long because of the seq( commands. I have a Ti 83 (not PLUS!)

(each line begins with an implied ":" )

0->θ
For(Y,1,7                                                            //Tests the verticals for 4 in a row
For(A,1,3
seq([A](I,Y),I,A,A+3
cumSum(Ans
If Ans(4)=4
1->θ
If Ans(4)=-4
-1->θ
End
End
For(Y,1,6                                                               //Tests horizontal rows for 4 in a row
For(A,1,4
seq([A](Y,I),I,A,A+3
cumSum(Ans
If Ans(4)=4
1->θ
If Ans(4)=-4
-1->θ
End
End
For(I,5,10                                                               //test diagonally up and to the right
seq([A](Y,I-Y),Y,(I-4)(I<=6)+6(I>=7),(I<=8)+(I-7)(I>9),-1->L1                                                //   <= means  ≤ and >= means ≥
For(A,1,dim(L1)-3
seq(L1(M),M,A,A+3
cumSum(Ans
If Ans(4)=4
1->θ
If Ans(4)=-4
-1->θ
End
End
For(I,3,-2,-1                                                                                             // tests diagonally down and to the right
seq([A](Y,Y+I),Y,(I>=0)+(1-I)(I<0),(7-I)(I>=2)+6(I<=1)->L1
For(A,1,dim(L1)-3
seq(L1(M),M,A,A+3
cumSum(Ans
If Ans(4)=4
1->θ
If Ans(4)=-4
-1->θ
End
End

Inputs: [A] 6x7
outputs:θ = -1,0,1

If θ=-1, player2 has gotten four in a row
If θ=1, player1 has gotten four in a row
If θ=0, no one has won, game continues

I need this optimized primarily for speed, maybe using something other than seq( , then for size. But the real problem is that it takes about 15 seconds, and on one has that kind of time to wait between turns in connect 4

BTW, after this is optimized, and assuming I dont lose all my data on the calculator, I can post the rest of the connect 4 game, but it should be pretty simple for anyone to come up with one given the checking algorithm and Matrix [A]

any suggestions to make this faster (preferably under 8 sec or faster) would be greatly appreciated.

Last edited on 12 Oct 2015 17:56 by TI-GBR Show more

Re: Connect 4 four-in a row test

Silver Phantom 12 Oct 2015 19:45

Do you know if an actual logic test written by hand, testing cell to cell, would be slower than a seq(?

Also, could you instead program it to test the rows and columns and diagonals that a new cell directly affects, since you'll probably be checking this after each turn.

---

The Silver Phantom welcomes you

Re: Connect 4 four-in a row test

TI-GBR 12 Oct 2015 19:58

hmm, that's a good point. So you don't think my original program could be made much faster?

Re: Connect 4 four-in a row test

jonbush 12 Oct 2015 20:35

Also, you only have to test the vertical, horizontal, and diagonals for the last move - not the entire board.

Re: Connect 4 four-in a row test

TI-GBR 12 Oct 2015 20:50

*sigh* all that work…
But yeah, I guess I'm overdoing it. Thanks.

Re: Connect 4 four-in a row test

(account deleted) 13 Oct 2015 04:30

Last edited on 01 Apr 2021 13:23 by (account deleted) Show more

Re: Connect 4 four-in a row test

Trenly 13 Oct 2015 03:30

In order to speed it up, you need to reduce the amount of tests you need to make.

I'm curious as to if you could use sum( to test for values horizontally

Sum(1=[A](1) //if this is 4 or more you need to check further
Ans->B
Sum(-1=[A](1)// if this is -4 or less you need to check further
Ans+B //if this is -2 or 2, then you only need to check the ends for 2 consecutive same numbers, as the other four will be the other number, thus creating a winning situation

Re: Connect 4 four-in a row test

lirtosiast 05 Mar 2016 02:12

Unfortunately, on the 84+ series you can't access columns of a matrix directly like that. There is, however, Matr▶List(.

If this is fixed it can be applied to horizontal checking by simply transposing the matrix.