MENACE

Projects » MENACE

Not Finished

# Description

This project is an attempt to recreate MENACE. This article describes MENACE in its entirety

# Updates

Who Updated? |
Date |
Update |
---|---|---|

Trenly | 17 Jun 2018 03:06 | Got the basic naughts and crosses engine going. |

To Do:

- Create the memory setup for the AI
- Create the Code for the AI to recall the gameboard partial probabilities
- Create the code for remembering which gameboards were recalled and which moves were played
- Create the code for adjusting the partial probabilities for each gameboard
- Create the AI - Created the selection already
- Implement the AI

Main Naughts and Crosses Engine: (Player vs Player)

```
SetUpEditor ʟM,ʟMC
{0→ʟM
{0→ʟMC
StoreGDB GDB1
AxesOff
GridOff
CoordOff
Full
LabelOff
ExprOff
RectGC
Normal
Func
63→Ymax:0→Ymin
93→Xmax:0→Xmin
ClrDraw
Text(⁻1,2,14,"M.E.N.A.C.E.
Line(29,49,65,49
Line(65,49,65,13
Line(65,13,29,13
Line(29,13,29,49
Line(32,47,62,47
Line(31,46,63,46
Line(63,46,63,16
Line(62,47,62,15
Line(62,15,32,15
Line(61,15,33,15
Line(31,16,31,46
Line(32,15,32,47
Line(42,45,42,15
Line(52,45,52,15
Line(33,25,61,25
Line(33,36,61,36
19→H
35→V
1→P
Repeat dim(ʟM)=10
1→T
If fPart(dim(ʟM)/2):2→T
Line(H+14,V+2,H+22,V+2
Repeat sum(K={45,21,105
Repeat sum(K={45,21,105,24,25,26,34
getKey→K
End
If K=45:Stop
If sum(K={24,25,26,34:Then
Line(H+14,V+2,H+22,V+2,0
P+(K=26)(P<9)-(K=24)(P>1)+3(K=34)(P≤6)-3(K=25)(P≥4)→P
P/3
If Ans≤1:35→V
If Ans≤2:24→V
If Ans≤3:14→V
If sum(P={1,4,7
19→H
If sum(P={2,5,8
29→H
If sum(P={3,6,9
39→H
Line(H+14,V+2,H+22,V+2
End
End
If (K=105)not(sum(P=ʟM:Then
P→ʟM(1+dim(ʟM
Line(H+14,V+2,H+22,V+2,0
P/3
If Ans≤1:19→G
If Ans≤2:29→G
If Ans≤3:39→G
If sum(P={1,4,7
35→U
If sum(P={2,5,8
46→U
If sum(P={3,6,9
56→U
Text(⁻1,G,U,sub("OX",T,1)
expr(sub("020305071113171923",2P-1,2))→ʟMC(dim(ʟM
If dim(ʟMC)≥6:Then
1→A
For(E,2,dim(ʟMC),2
AʟMC(E)→A
End
If not(sum(not(fPart(A/{30,1001,7429,238,627,1495,506,935}):Then
1→A
For(E,3,dim(ʟMC),2
AʟMC(E)→A
End
End
sum(not(fPart(A/{30,1001,7429,238,627,1495,506,935})→W
If W:10→dim(ʟM
End
End
End
If not(W:Then
Text(⁻1,52,23,"TIE GAME!
Pause
Else
If T=2:Text(⁻1,52,15,"CROSSES WIN!
If T=1:Text(⁻1,52,15,"NAUGHTS WIN!
If T:Pause
End
RecallGDB GDB1
ClrDraw
ClrHome
```

Partial Probability Selection:

```
ʟPROB→ARRAY
sum(ARRAY→X
Xˉ¹→U
U→S
DelVar LDelVar C
rand→T
For(E,1,dim(ʟARRAY
While ʟARRAY(E) and not(C
If L≤T and U≥T
Then
E→C
Else
ʟARRAY(E)-1→ʟARRAY(E
U+Xˉ¹→U
L+Xˉ¹→L
End
End
End
C→P
```

## Discussion

I finished the basic naughts and crosses engine last night, as well as created a partial probability algorithm (I will post the algorithm to the routines page later, as it could be useful in other places).

As of this point I have a very basic AI going, which randomly chooses a position and plays it. This means I created the playing interface for the AI, and am able to start building the logic. However, I would like opinions of which version of menace to implement: With mirroring/rotation, or without mirroring. I for some reason believe that without mirroring would be easier to implement, but am not sure.

I would also like suggestions on how to implement the memory for storing each gameboard. The only criteria is that it must be a list of 9 numbers which correspond to the places on the board. I can convert lists to strings, but my thought was a matrix for each move. This would only require 4 matricies. Each matrix would correspond to a turn that MENACE makes. [G] would contain gameboard states for menaces 1st move, where each line represents a gameboard state. -1 would be used to indicate a position which has already been played. This would mean that [G] would look something like this, with the 0's being the partial probability of each layout after the first move. I can then use my list of moves which have been played to determine which line of the matrix is the current gameboard. I could then load that row into the probability list, make the selection and repeat. However, There are thousands of different gameboards that could be played, so i might have to narrow it to a subset based on the moves already played

ReplyOptionsI think a version without mirroring would be much easier (I got very confuzzled when I tried to implement mirroring right away) because you have much less boards to check for. As for checking the game state, a matrice sounds like it will work, but for rewarding/punishing MENACE, strings would probably be easiest to implement.

ReplyOptionsI agree strings might be easiest for that. However, the caclulator obviously has limited memory. There are many thousands of boards that can be possible, so I have to find some way to compress it.

I think that while I try and figure out a way to handle the memory I might build a different version of an AI that uses hardcoded logic:

ReplyOptionsSorry for the double post, but its been 8 hours and I fee this is relativey different in content compared to my last post.

I am not good at combinatorics, but according to this website, there are 255,168 possible games. If you consider that I do not have to store any of the boards that win after 5 moves, it helps. I also dont have to store any of the boards after 6 moves, but I do at 7. But again not at 8, or 9.

In total I have to store all the boards with 1,3,5,or 7 moves which do not contain a winning sequence. I may not be good enough at math to calculate the exact number, but I know it is a lot

With rotations it would be 774, but if menace went first it would be 304.

ReplyOptions