JavaScript Tic-Tac-Toe AI: Really AI??

[Pokerchip28]

Artificial Intelligence: Teaching the Computer to Play Tic-Tac-Toe

https://www.sciencebuddies.org/science- ... ic-tac-toe

I decided to choose this as my science fair topic and I am sort of regretting it. As a freshman in high school, I am unable to change my experiment at this point so I am obligated to work through this. I am sort of stuck though, since I am very confused on what my independent, dependent, and control variables should be. I need a quantitative value to measure for this, so I am thinking of something like success rate or the amount of rounds played until my artificial intelligence begins to win or tie with the player or itself, that is if I am testing it against itself. The problem is that I have been reading the procedures and I have noticed that the way the project is described, isn't AI. From my research, AI should be something that learns from nothing, but I don't know how to code for this. I just need help to find a way to write a JavaScript program that can start very stupid, only knowing it's controls and environment, and begin to develop its own strategies by playing over and over again, failing, and learning by its faults. My hangup is mostly how to make the machine learn and what my variables should measure or change. Thank you soooo and very much to anyone willing to help, I am in great need at the moment!

Garrett

[bfinio]

Hi Garrett,

I'm a mechanical engineer, not a computer scientist, so I can't tell you exactly how to do this project, but I hope I can clarify some of the terminology and point you in the right direction.

First, the words "Artificial Intelligence" get thrown around a lot and the definition may change depending on who you ask. In general everyday language, people might expect "AI" to mean robots from movies like Terminator, Star Wars, and Transformers - machines that can think and feel just like humans. Obviously those don't exist in the real world (yet!). More practically, many people do use AI to refer to computer programs that are "hard-coded" and do not "learn from nothing" like you described. For example, we commonly refer to enemy characters in video games as "AI," but a human programmed their behavior, they did not learn it (otherwise the AI in every video game you played would start out totally dumb and very easy to beat). So, for purposes of this project, I think it would be acceptable to write a program to play tic-tac-toe against a human, using an algorithm that you came up with and coded yourself.

If you DO want to go the "learning" route, you will need to do more research on terms like "machine learning" and "genetic algorithms" or "evolutionary algorithms." There are lots of examples online of people doing this with classic video games. This is similar to what you described. For example in a Mario game, an AI might measure its progress from how far it can make it through the level before dying. It will start out "dumb" by just randomly pressing controller buttons. Over time, it will notice that certain sequences of buttons get it farther through the level than others, and it will start pressing those buttons instead of doing it randomly. You could take a similar approach with tic-tac-toe. For example (say the human is O's), at first the computer might always place an X randomly. After 100 games, it might notice that "the game lasts longer if I place the first X next to the first O" (no idea if that's true, just making it up as an example), and then use that information to change its behavior. Programming something like that would be much more complicated, so if that is beyond your comfort level, I would stick with the hard-coded approach for now. Since you are only a freshman, you'll have plenty of time to learn more about programming and maybe try a more advanced version of the project in a year or two.

One final note - you should ask if your science fair will accept engineering design projects instead of scientific method projects. Science Buddies has a resource about the differences between the two:

https://www.sciencebuddies.org/science- ... fic-method

If you do have to stick with scientific method, then there are ways to think of variables for this (for example, write two different programs and compare their win rates against human players).

Hope that helps!

Ben

[LeungWilley]

Hi Garrett,
Sorry to hear that you are struggling with this. I have a couple of suggestion for you:

First, for the "machine learning / AI" part of the question, one way to approach this is to have the "AI" log the results of the sequence of move in a table. This table (experience) is then used to help the AI (Alogrithm) determine its next move in a game , i.e. perform a lookup of the table and look for the sequence of moves that yields the highest percentage of a particular strategy. (In other word, the AI will determine its move (placement of the "O" based on the previous "learned" experience. As the result table grows, the AI Algorithm should be able to pick better and better move.)

At any rate, in regards to the second part of your question about what should be your independent, dependent, and control variables, Using one of the example you provided: the amount of rounds played until my artificial intelligence begins to win or tie with the player," you could have an experiment where your algorithm is tweaked to figure out what strategy will work best to achieve the fewest amount of rounds.

For example,
1. Strategy 1 (Control): Have the algorithm use the "highest" win percentage move every time
2. Strategy 2: Have the algorithm use the "2nd highest" win percentage move every time
3. Strategy 3: Have the algorithm aim for the "tie strategy" move every time.

You will have to empty the results table each time you run this code (and if you are "teaching" the algorithm, you will also need to apply the same lesson each time. (the standard scientific method, etc...)

Hopefully, this gives you some idea on how to proceed.
Please let us know if there's anything else we can do to help.
Good Luck!
Willey

[Pokerchip28]

Ok I understand both propositions and appreciate the feedback! I have decided to pursue the idea of true AI being that it learns on its own, however, the machine learning/genetic algorithm idea is going to screw me over, to be honest with you. I am very very thankful that two helpful people have put forth their contributions and I just need a bit more information as to where I should go to learn how to develop a genetic learning algorithm for this AI. I have actually always been interested in genetic algorithms and machine learning, but have never attempted to write a program of the sort myself. If anyone has any guidance or suggestions to push me in the right direction, please feel free to help me out! Thanks a ton!

Garrett

[Pokerchip28]

I also apologize for not responding sooner, school has been demanding and I did not think to check back on this forum. Thanks so and very much again! One more thing, I will ask my teacher if he will accept an engineering design process experiment but I am afraid he will be confused or dislike the idea of doing a different sort of experiment from the rest. I also have until the 12th of December to complete my data table and graph, so based on those added factors, how might I integrate this engineering method into my project over the scientific method? Anyways, thanks again very much!

Garrett

[LeungWilley]

Hi Garrett,
This is quite an ambitious project that you are taking on! I don't know if you are going to have enough time to implement all of this by the 12th but let's see if we can't at least get to a good starting point for you:

To start, let's follow the methodology section from "Genetic Algorithm" article from Wikipedia as a starting point: (I know, your teacher probably won't allow you to use this source, but the information is still valid and can be confirmed with other sources in the references sections) https://en.wikipedia.org/wiki/Genetic_algorithm

Methodology (and using the example I mentioned in the earlier post)
1. Initialization - You are going to need to generate a table with all the possible solutions to the Tic-Tac-Toe game play. That would be your "population"
2. Selection - Setup a criteria (such as win rate above a certain percentage for a sequence of move, for example) and then refine this population. (Easiest thing to do may be a randomized selection here)
3. Genetic Operator - In short, you are going to program the computer to basically play against itself using this newly selected population. You can get creative here and determine what other "mutation" you might want to insert here as well (for example, say you can program the algorithm to go back in time (i.e. a time travel gene) after learning what the other player played and adjust its move)
4. Termination - Once you achieve the desired win rate, you can terminate the learning portion of the program.

Now, in regards to integrating this engineering portion into the scientific method, you will still need to come up with a hypothesis. For example, why do you deploy a certain selection criteria? Once you have framed that question, you can then design the rest of the experiment to answer it.

I hope that helps. Please let us know if we can help with anything else.
Best of luck!
Willey