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 |
|---|---|---|
| 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
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
I 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.
I 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:
Sorry 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.