Create unbeatable Greedy Algorithm for Computer!

[sbshah97]

Ground rules:

1. Whoever claims the Issue first, should send a Pull Request within 24 hours else it'll be assigned to another claimant and further Pull Requests regarding that issue will not be entertained.
2. Pull Requests sent without claiming and referencing the Issue will not be entertained.
3. Make sure your Pull Requests have just one commit in them. Squash multiple commits into one if you have to.

The computer logic written is not unbeatable. When user marks any two diagonally opposite corners in first two moves, the algorithm is unable to detect this as part of its winning strategy and the computer loses.

The computer could possibly be made unbeatable by tweaking with this logic and making the strategy strong. As the computer uses cell scoring strategy, the possible tweak may be scoring the cells more effectively so that the computer wouldn't lose.

[LauraLaureus]

Is this assigned to anyone? I would like to practise Java greedy algorithms applied to games, but I need to set up the android studio to check the results, so I will need more than 24h specified in point one. That fact it's okay for you in case you haven't anyone doing this already?

[sbshah97]

Go ahead. Try it out. If you don't finish it in 24 hours, come back and claim it again. Best of luck!

[LauraLaureus]

Android Studio set up done. Working on heuristic for unbeateable AI

[LauraLaureus]

I have a doubt? I thing there are two solutions to this problem 1) add some rules to current set of rules and adjust the score for them (easy implementation in less of 24h of development) or 2) implement a AIPlayer able to imagine user movements (that is a known algorithm but requires more than a day of implementation and testing). Which of them do you want?

[Hrily]

First one... :+1: The reason is, I want it to be understandable for anyone who wants to build TicTacToe computer but has no knowledge about AIs.

[LauraLaureus]

Okey, coffei and working on it ;)

[Hrily]

All the best :+1:

[LauraLaureus]

Do you have more cases than the one in this issue?

[Hrily]

Not in my knowledge and I also think there isn't. You can go ahead and try to find if any.

[LauraLaureus]

I have tested some cases and It's is unbeateable unless the player has two choices of winning. In this case blocks one of them. Is this enough for you?

Example of case where it fails:

X	O	-
-	-	-

User plays position 0 and IA position 1

X | O | - O | - | - X | - | - User plays position 6 and IA position 3

X | O | - O | O(2) | - X | O(1) | X User plays position 8 and IA has to choose between position 7 or 4 and plays 7.

To avoid this, Building a tree structure with possible board states and computing the best will be needed.

What do you think?

[Hrily]

https://en.wikipedia.org/wiki/Tic-tac-toe

See Strategy - 4. Blocking an opponent's fork This will help you...

[Hrily]

@LauraLaureus How is it going?

[LauraLaureus]

I have just made the pull request. If there is any case you winning tell me I'll study, but I think it's done. in fact I lose once and get draw rest of times.

[LauraLaureus]

I’m working in other set of rules and checking XD.

Laura del Pino Díaz (Ingeniera Informática / Computer Scientist) l4depende@gmail.com mailto:l4depende@gmail.com || lauradelpinodiaz94@gmail.com mailto:lauradelpinodiaz94@gmail.com

LinkedIn - https://es.linkedin.com/in/laura-del-pino-diaz-1493ba66/en https://es.linkedin.com/in/laura-del-pino-diaz-1493ba66/en Wordpress - http://lauralaureus.ideonica.com http://lauralaureus.ideonica.com/ GitHub - https://github.com/LauraLaureus https://github.com/LauraLaureus Twitter - https://twitter.com/LaureusDoC https://twitter.com/LaureusDoC

El 21 oct 2016, a las 13:32, Hrishi Hiraskar notifications@github.com escribió:

@LauraLaureus https://github.com/LauraLaureus How is it going?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/Hrily/TicTacToe/issues/3#issuecomment-255358520, or mute the thread https://github.com/notifications/unsubscribe-auth/AIWEmEuKlQHYR9-ahVJg3Ot645xSlMEmks5q2KLrgaJpZM4KbM53.

[sbshah97]

@Hrily do you want me to use MiniMax to implement an AI program for this right now?