Post Reply 
For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI.
11-01-2016, 01:15 PM
Post: #1
For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI.
I wanted to learn about the miniMax algorithm, so I wrote this tic-tac-toe game and implemented miniMax so you could play a game against your Prime. It has a full touch screen interface:

[Image: TIC_TAC_MAX.png]

Instructions are included in the zip file.

When implementing the AI, I used the miniMax algorithm in a recursive function. The way I had originally coded the application, if the computer got to move first in a new game, it had to recurse through 9! or 362,880 possible moves. While this only took a few seconds with the emulated Prime calculator on my PC, the actual calculator took about 2 1/2 minutes to do this! In order to speed things up, I implemented some logic. If it is the Prime's go first, pick the center square. After the player's turn, this now leaves 7! moves or 5,040 possibilities to search through... much faster! If it is the Prime's move second, it checks to see if the center square has been taken. If not, choose it, otherwise choose a corner square at random. After the player's third move, it now only has 6! or 720 moves to recurse through. In order to create a weaker AI for different levels I limited the depth of the miniMax search. I'm sure the algorithm could be improved by adding alpha-beta pruning... maybe some industrious coder out there is up to the challenge!

All in all this was a fun application to code. I am thinking about doing a chess engine for the Prime, although I am not sure how feasible that would be... if it would be strong enough and fast enough to have a decent ELO rating.

I would also like to thank and acknowledge Mickaël Nicotera whose TIC-TAC-TOE game was the inspiration for this version.

Anyways, I hope everyone enjoys. Any suggestions or comments are welcome.


Attached File(s)
.zip  TIC_TAC_MAX.zip (Size: 135.57 KB / Downloads: 22)
Find all posts by this user
Quote this message in a reply
11-03-2016, 12:05 PM
Post: #2
RE: For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI.
Thanks for the suggestions moonbeam!

I have seen chess programs for the TI calculator series, and from what I have seen the HP Prime is much faster, so it should be possible, and if coded right it could probably play a decently strong game. I am used to coding in C#, so the syntax of the Prime programming language has been a challenge. I am continuously going back and correcting syntax errors.

A couple of things I think would make it difficult to write a chess engine on the Prime is the very weak debug mode. When you are used to step over and step out, it gets kind of tedious stepping through a loop that has 100 iterations just to get to the next part of the program. Also, and maybe I am missing this, there doesn't seem to be any support for custom variable types where you can define variables and then access them with friendly names like move.playerColor, etc.

The use of Notepad++ as a program editor is awesome, however... especially with the HP Prime language definitions I found on hpcalc.org. I modified the theme to match my dark visual studio theme:

[Image: Capture3.png]

I wish I would have gotten into things like this a long time ago. I remember watching WarGames and Professor Stephen Falken was my hero for a long time... as well as Matthew Broderick and that old IMSAI computer! I only had an Atari 400 at the time, and Atari Basic was my first language. I eventually progressed to Machine Language... and that was a bear! Maybe there was an easier way to do it, but I was coding stuff like load accumulator with such and such value then store it here... real basic level stuff and very difficult for a 13 year old kid with no internet access (and no world wide web!). I had to get books, and they usually had to be special ordered, as most bookstores carried no such programming books in the early 80s.

I have been learning quite a bit of C#, but I also worry that it and the .NET framework might not port well to other operating systems, such as linux... so I may be limiting myself by doing things the "Microsoft" way.... but I LOVE Visual Studio!!

Other than some of the above mentioned shortcomings, I have really enjoyed programming the Prime... it takes me back to my Atari Basic days!
Find all posts by this user
Quote this message in a reply
11-14-2016, 01:26 PM
Post: #3
RE: For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI.
Hmmm... I had to do a reset on my Prime because the HP Connectivity Kit kept crashing when I would expand the tree for the physical calculator.

After a reset and changing my settings back to the way I had them, I noticed TIC-TAC-MAX was no longer drawing Os on the board. It just made a dot on the board. After more research, I found that after setting the angle mode back to radians, the circles would then be drawn. The command used was ARC_P. Is this a bug in the software?

I set the angle mode back to degrees and reran the game and the same problem occurred. Is there some statement I need to use in the program to tell it to use radians, or is there something that needs to be specified in the ARC_P statement itself?

I would think it would work regardless of what angle mode the calculator happened to be in.
Find all posts by this user
Quote this message in a reply
11-14-2016, 05:14 PM
Post: #4
RE: For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI.
(11-14-2016 01:26 PM)falcon56215 Wrote:  I would think it would work regardless of what angle mode the calculator happened to be in.

ARC uses the current system angle settings (as specified in the help for the command). If you are just drawing a complete circle, you don't have to specify the star/stop angles as the default is a full circle. If you are drawing non-complete circles, you either need to change the app/system setting, or else have a function that returns the correct stop/start in deg/rad/grad.

TW

Although I work for HP, the views and opinions I post here are my own.
Find all posts by this user
Quote this message in a reply
11-14-2016, 06:10 PM
Post: #5
RE: For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI.
(11-14-2016 05:14 PM)Tim Wessman Wrote:  ARC uses the current system angle settings (as specified in the help for the command). If you are just drawing a complete circle, you don't have to specify the star/stop angles as the default is a full circle. If you are drawing non-complete circles, you either need to change the app/system setting, or else have a function that returns the correct stop/start in deg/rad/grad.

You're a genius... (or just better at reading documentation than I am)... removing the start/stop angles fixed the problem. Thanks!
Find all posts by this user
Quote this message in a reply
11-14-2016, 09:06 PM
Post: #6
RE: For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI.
(11-14-2016 06:10 PM)falcon56215 Wrote:  You're a genius... (or just better at reading documentation than I am)
LOL.

Prime, 15C CE
Find all posts by this user
Quote this message in a reply
11-14-2016, 09:18 PM (This post was last modified: 11-14-2016 09:22 PM by Tim Wessman.)
Post: #7
RE: For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI.
Quote:
(11-14-2016 09:06 PM)chromos Wrote:  You're a genius... (or just better at reading documentation than I am)
LOL.

I suppose when I helped write that entry something must have stuck in my head... Big Grin

I actually have a vague memory of specifically tweaking the ARC help entry while sitting in a McDonalds in Jackson Hole, Wyoming 3 summers ago. There was a deadline to get things off to translation and I'd been working on it in the car while riding up to Yellowstone to go to a family summer campout. We stopped there for an hour or two, the kids played and I finished the last tweaks to the help files and released them to the translators. One of the entries I remember working on were the ARC entries... Smile

TW

Although I work for HP, the views and opinions I post here are my own.
Find all posts by this user
Quote this message in a reply
11-15-2016, 06:29 AM
Post: #8
RE: For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI.
Hello falcon56215
Quote: When you are used to step over and step out, it gets kind of tedious stepping through a loop that has 100 iterations just to get to the next part of the program.
Surement le savez-vous, mais sinon cela peut toujours aidé, DEBUG() est programmable et peut
être placé seulement là où c'est nécessaire.

Surely you know, but otherwise this can always help, DEBUG () is programmable and can
Be placed only where necessary.

Sorry for my english
Find all posts by this user
Quote this message in a reply
11-15-2016, 06:37 PM
Post: #9
RE: For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI.
(11-01-2016 01:15 PM)falcon56215 Wrote:  The way I had originally coded the application, if the computer got to move first in a new game, it had to recurse through 9! or 362,880 possible moves.

Since you are doing this as an educational experience, you might want to explore making use of the symmetries. For instance, there are only 3 possible opening moves: center, corner, side.

If the opening move is at the:
center - there are only two possible replies (corner, side)
corner - there are 5 possible replies
side - there are 5 possible replies

There are 7 symmetries on a tic-tac-toe board: four reflections (vertical line, horizontal line, positive slope diagonal, negative slope diagonal) and 3 rotations (90°, 180°, 270°). However, only 3 are needed (say, vertical line, horizontal line, pos slope diagonal) while the other 4 are redundant. For instance, a rotation of 90° could be accomplished by reflecting over the diagonal then over the horizontal.

By the way, if you haven't yet seen the xkcd tic-tac-toe map, check out https://xkcd.com/832/
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)