HP Forums
For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI. - Printable Version

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: HP Prime (/forum-5.html)
+--- Thread: For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI. (/thread-7144.html)



For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI. - falcon56215 - 11-01-2016 01:15 PM

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.


RE: For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI. - falcon56215 - 11-03-2016 12:05 PM

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!


RE: For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI. - falcon56215 - 11-14-2016 01:26 PM

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.


RE: For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI. - Tim Wessman - 11-14-2016 05:14 PM

(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.


RE: For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI. - falcon56215 - 11-14-2016 06:10 PM

(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!


RE: For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI. - chromos - 11-14-2016 09:06 PM

(11-14-2016 06:10 PM)falcon56215 Wrote:  You're a genius... (or just better at reading documentation than I am)
LOL.


RE: For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI. - Tim Wessman - 11-14-2016 09:18 PM

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


RE: For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI. - Tyann - 11-15-2016 06:29 AM

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.


RE: For your consideration... TIC-TAC-MAX... a tic-tac-toe game with miniMax AI. - Wes Loewer - 11-15-2016 06:37 PM

(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/