Win condition optimization

Forum Attachments

Summary:

...I need it faster...

Win condition optimization

Silver Phantom 10 Nov 2012 16:53

So i need help optimizing this
[A] is a 6x7 and contains 0-2, all of which will be near the bottom

DelVar L
{0,0,0,0,0,0,0,0→L1
For(D,1,6)             :to go through all 6 rows
For(C,1,4)             :to go through all 7 collumn without going out
expr("1000[A](D,C)+100[A](D,C+1)+10[A](D,C+2)+[A](D,C+3)")→X     :horizontal check
X=1111                 :player one win check
Ans+L1(1→L1(1
X=2222                 :player 2 win check
Ans+L1(2→L1(2
End
End
For(D,1,3)
For(C,1,7)
expr("1000[A](D,C)+100[A](D+1,C)+100[A](D+2,C)+10[A](D+3,C)")→X     :vertical check
X=1111
Ans+L1(3→L1(3
X=2222
Ans+L1(4→L1(4
End
For(C,1,4)
expr("1000[A](D,C)+100[A](D+1,C+1)+10[A](D+2,C+2)+[A](D+3,C+3)")→X   :diagonal check
X=1111
Ans+L1(5→L1(5
X=2222
Ans+L1(6→L1(6
expr("1000[A](D,C+3)+100[A](D+1,C+2)+10[A](D+2,C+1)+[A](D+3,C)")→X    :other diagonal check
X=1111
Ans+L1(7→L1(7
X=2222
Ans+L1(8→L1(8
End
End
If L1(1)=0 or L1(3)=0 or L1(5)=0 or L1(7)=0:Then   :wining statements
Disp "PLAYER 1 WIN"
Stop
End
If L1(2)=0 or L1(4)=0 or L1(6)=0 or L1(8)=0:Then
Disp "PLAYER 2 WIN"
Stop
End

i just need it faster, i don't care if it gains or loses a few bytes
thanks

---

The Silver Phantom welcomes you

Last edited on 10 Nov 2012 16:53 by Silver Phantom Show more

Re: Win condition optimization

Xeda Elnara 10 Nov 2012 21:57

I'm not sure if this is faster (and I am sure it can be much more optimised), but:

DelVar L1
8→dim(L1
For(D,1,6              :to go through all 6 rows
For(C,1,4              :to go through all 7 collumn without going out
prod(seq([A](D,C+E),E,0,3→X          :horizontal check
X=1                 :player one win check
Ans+L1(1→L1(1
X=16                :player 2 win check
Ans+L1(2→L1(2
End
End
For(D,1,3)
For(C,1,7)
prod(seq([A](D+E,C),E,0,3→X
X=1
Ans+L1(3→L1(3
X=16
Ans+L1(4→L1(4
End
For(C,1,4)
prod(seq([A](D+E,C+E),E,0,3→X
X=1
Ans+L1(5→L1(5
X=16
Ans+L1(6→L1(6
prod(seq([A](D+E,C+3-E),E,0,3→X
X=1
Ans+L1(7→L1(7
X=16
Ans+L1(8→L1(8
End
End
If not(L1(1)L1(3)L1(5)L1(7   :wining statements
"1
Return
If not(L1(2)L1(4)L1(6)L1(8
"2
Disp "PLAYER "+Ans+"WIN
Return

---

Z80 Assembly>English>TI-BASIC>Python>French>C>0

Re: Win condition optimization

Roguebantha 11 Nov 2012 14:26

For the times you do X=1 or 16 you should be able to put this in for Ans. Or did you do that so you could avoid parentheses? I think that it would probably be faster with them. Also, I love to get rid of if-statements and replace with calculation and in this case, I think I can get away with it. Instead of your last two if statements, assuming that someone will always win, you can type:
Disp "Player", L₁(1)L₁(3)L₁(5)L₁(7)+1, "wins."

---

Last edited on 11 Nov 2012 14:27 by Roguebantha Show more

Re: Win condition optimization

Silver Phantom 11 Nov 2012 15:16

getting rid of the if then statements would mean that every time that it checks for a win, it would make player 1 win

---

The Silver Phantom welcomes you

Re: Win condition optimization

Roguebantha 11 Nov 2012 15:36

It would work :) thats what the +1 on the end ensures.

---

Re: Win condition optimization

Xeda Elnara 11 Nov 2012 15:27

I do not believe the parentheses would make it faster, but it might since that would make it part of a calculation and so it doesn't need to store to Ans.

Disp "PLAYER",L1(1)L1(3)L1(5)L1(7)+1,"WINS"

This would work, but it would do something like this on the homescreen:

|prgmCONNECT4    |
|PLAYER          |
|               1|
|WINS            |
|                |
|                |
|                |
|                |

Also, I optimised further and this should definitely speed things up for certain case (or all cases). I will try to see if I can come up with a new approach to the problem using graph theory, though. Unfortunately, the way I am thinking of would require a 42x42 matrix. If I did it in assembly, I could cut that matrix down to 441 bytes, easily, and then I would just need to square it, square it again, et voila, you will have all the wins :D

DelVar X
For(D,1,6              :to go through all 6 rows
For(C,1,4              :to go through all 7 collumn without going out
prod(seq([A](D,C+E),E,0,3          :horizontal check
If Ans=1 or Ans=16
Ans→X
End
End
If not(X
Then
For(D,1,3
For(C,1,7
prod(seq([A](D+E,C),E,0,3
If Ans=1 or Ans=16
Ans→X
End
If not(X
Then
For(C,1,4
prod(seq([A](D+E,C+E),E,0,3
If Ans=1 or Ans=16
Ans→X
prod(seq([A](D+E,C+3-E),E,0,3
If Ans=1 or Ans=16
Ans→X
End
End
End
End
"0
If X=1
"1
If X=16
"2
If Ans≠"0
Disp "PLAYER "+Ans+"WIN
Return

---

Z80 Assembly>English>TI-BASIC>Python>French>C>0

Re: Win condition optimization

Roguebantha 11 Nov 2012 15:37

Actually for a program like this, I would recommend using Output instead if Disp.

---

Re: Win condition optimization

Silver Phantom 12 Nov 2012 03:44

Thanks! It's faster now by tenfold but still not the speed I want, oh well.

---

The Silver Phantom welcomes you

Re: Win condition optimization

Xeda Elnara 12 Nov 2012 13:18

Do you mind if I point out that you don't need to check every position after every move? All you need to do is check any places affected by the last choice. For example, if O is the piece last dropped:

x     x     x
  x   x   x
    x x x
x x x O x x x
    x x x
  x       x
x           x

The 'x' positions are all you need to check. Just compare them to the value at O and if you have 4 in a row, then O won. That should help speed things up quite a bit. I will try to figure out some useful code at another time (I have a bunch of projects due this week XD )

EDIT:
Say you read the 7 elements going across (note that you will rarely read all 7) and you get something like this:
{1,0,2,1,1,1,1}

Then use this:

cumSum(Ans=O→L1
ΔList(cumSum(Ans
ΔList(cumSum(Ans
ΔList(cumSum(Ans
ΔList(cumSum(Ans
augment(Ans,{0,0,0,0
If sum(3<Ans-L1
Disp "PLAYER "+sub("12",O,1)+" WINS!"

---

Z80 Assembly>English>TI-BASIC>Python>French>C>0

Last edited on 12 Nov 2012 13:26 by Xeda Elnara Show more

Re: Win condition optimization

Roguebantha 12 Nov 2012 15:09

This works fine, but i'd get rid of some code and do:

For(A,1,4)
ΔList(cumSum(Ans
End

It's just prettier that way :)

---

Last edited on 12 Nov 2012 20:45 by Roguebantha Show more

Re: Win condition optimization

Xeda Elnara 12 Nov 2012 17:06

Yeah, I wasn't sure if there were variables left to sacrifice :D

---

Z80 Assembly>English>TI-BASIC>Python>French>C>0

Re: Win condition optimization

Roguebantha 12 Nov 2012 20:47

Oh yeah, that's true :) So do this then:

ΔList(cumSum(ΔList(cumSum(ΔList(cumSum(ΔList(cumSum(Ans

---

Last edited on 12 Nov 2012 20:56 by Roguebantha Show more

Re: Win condition optimization

Xeda Elnara 12 Nov 2012 23:41

Nice call, good point!

---

Z80 Assembly>English>TI-BASIC>Python>French>C>0

Re: Win condition optimization

Roguebantha 13 Nov 2012 00:15

You'll actually cut more bytes/tokens off your program this way anyway, than even the For( loop, and it's also probably faster as well. :)

---

Re: Win condition optimization

Silver Phantom 13 Nov 2012 02:53

that's like going to extremes…well, an optimization is an optimization!

---

The Silver Phantom welcomes you

Re: Win condition optimization

Silver Phantom 13 Nov 2012 02:00

i like that concept, but im having trouble trying to avoid the list from going outside. instead i think i'll just take the whole 7 places and have 0 at the ones out of bounds, but i need help trying to detect it going out of bounds. i think the best way would be with if then statements

---

The Silver Phantom welcomes you

Re: Win condition optimization

Xeda Elnara 13 Nov 2012 13:38

Grr, I pressed backspace and my mouse clicked outside of the box, so I lost my whole post :[
Assume you placed your piece at (Y,X).
There are two ways you can read a column or row efficiently in this case, that I will show you. The first is minimalist (you will only read what you need):

seq([A](A,X),A,max(1,Y-3),min(6,Y+3   ;read the vertical pieces
seq([A](Y,A),A,max(1,X-3),min(7,X+3   ;read the horizontal pieces

Or you can do it the quick/small method that will read more than you need:

Matr>List([A],X,L1 ;Stores the whole column to L1
Matr>List([A]^T,Y,L1 ;Stores the whole row to L1. ^T is for transpose

Whichever way you choose, that will work for horizontal and vertical. The diagonals will be a bit more of a pain:

;Read the main diagonal (left to right, going down)
min(X,Y
seq([A](Y+A,X+A),A,max(1,Ans-3)-Ans,min(7,max(X,Y+1)+3)-max(X,Y+1

And the other diagonal:

min(X,7-Y
seq([A](Y-A,X+A),A,max(1,Ans-3)-Ans,min(7,max(X,8-Y)+3)-max(X,8-Y

If you want to try it out by hand, here is a board: :D

2=Y
4=X

 o o o o o o o
 o o o X o o o
 o o o o o o o
 o o o o o o o
 o o o o o o o
 o o o o o o o

---

Z80 Assembly>English>TI-BASIC>Python>French>C>0

Re: Win condition optimization

Silver Phantom 14 Nov 2012 16:00

I have a error with cumsum(Ans=O

---

The Silver Phantom welcomes you

Boba Foxx (guest) 14 Nov 2012 16:47

Which error (syntax, argument, answer type, etc.)?

Silver Phantom 14 Nov 2012 16:59

Data type

---

The Silver Phantom welcomes you

Boba Foxx (guest) 14 Nov 2012 17:34

Since the ans should be a list, I dunno what was left out. It might have been something like Ans(1)=0 or something.

Re: Win condition optimization

Xeda Elnara 14 Nov 2012 17:49

As Boba Foxx said, Ans should be a list like {1,0,2,1,1,1,1}

---

Z80 Assembly>English>TI-BASIC>Python>French>C>0

Re: Win condition optimization

Silver Phantom 14 Nov 2012 18:01

I couldn't tell if it was =0 or =O cause later on it uses O

---

The Silver Phantom welcomes you

Re: Win condition optimization

Xeda Elnara 14 Nov 2012 18:14

In the case I gave, O is just a 1 or a 2 (depending on the turn it is). I used O since that was what I used in a previous example.

---

Z80 Assembly>English>TI-BASIC>Python>French>C>0

Re: Win condition optimization

Silver Phantom 12 Nov 2012 03:47

Oh you could also replace the last few things with 4th root x to get a 1 or 2 easy

---

The Silver Phantom welcomes you

Re: Win condition optimization

Roguebantha 12 Nov 2012 03:56

What conditions are needed for a player to win?

---

Re: Win condition optimization

Silver Phantom 12 Nov 2012 12:26

4 pieces in a line diagonal, horizontal or vertical or if the board is filled with no win, it's a tie

---

The Silver Phantom welcomes you

Last edited on 12 Nov 2012 12:26 by Silver Phantom Show more