[WIP] Minimax search function

[a1shadows]

Issue #9

[a1shadows]

@BusyByte Hey, could you please resolve the conflicts and review the pull request. Thanks.

[BusyByte]

@a1shadows sorry something wasn't quite right with my resolution of the merge conflicts, hopefully you can fix it up

[BusyByte]

@a1shadows let me know if you have any questions on the above or need help

[a1shadows]

@BusyByte Have tried addressing all the requested changes. Am working on testing the code. Could you please review the changes?

[a1shadows]

@a1shadows this looks good but still missing a test specification/property based test

I'll do the test code. I have my mid-terms till the 28th. Just need a little bit of time. Thanks for your constant guidance.

[a1shadows]

@BusyByte I've written a test for the function, but I'm having some difficulty coming up with more tests. Could you please review the new code and suggest how I should proceed with the tests?

[BusyByte]

@a1shadows fyi travis has broken, I've merge a fix to master for it now: https://github.com/aimacode/aima-scala/pull/72

you'll need to merge master in order to get travis to run your tests

[BusyByte]

@a1shadows might be worth going through a full game and verifying each player's actions are what you expect and not just the first one and verify you get NoAction at the end. I left some suggestions above but this seems pretty good so far.

[BusyByte]

@a1shadows also since this is adversarial maybe verify who should win and maybe a comment as to why

[a1shadows]

I'm getting a ton of errors on the code when I'm running it on the sbt which weren't there earlier. I can't understand them. They are all of this kind:

aima-scala\core\src\main\scala\aima\core\agent\Actuator.scala:8:16: type parameter Action defined in trait Actuator shadows trait Action defined in package agent. You may want to rename your type parameter, or possibly remove it.

Could you point me to what's going wrong, please?

[a1shadows]

Also, would it be possible to set up a gitter channel to discuss the repository? For general queries and the like?

[BusyByte]

@a1shadows I've created a gitter channel, you should get an invitation, I think the error you are seeing is because of a name collision. Maybe try upper case A in your type parameter or upper case ACTION for example. trait Foo[A] or trait Bar[ACTION]

[BusyByte]

@a1shadows maybe you need to do a sbt clean sbt ";clean;test:compile" after you merge master into your branch. I don't think there is a trait Action defined in package agent in package agent anymore looking at master.

[BusyByte]

@a1shadows this still says WIP in the title. Is there anything else you'd like to do before merging this?

[a1shadows]

Yeah. I'd like to work a bit on it.

On Sat, 29 Jun 2019, 5:00 pm Shawn Garner, notifications@github.com wrote:

@a1shadows https://github.com/a1shadows this still says WIP in the title. Is there anything else you'd like to do before merging this?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/aimacode/aima-scala/pull/71?email_source=notifications&email_token=AFIGZIQM36IBESICN2TJWGDP45BWHA5CNFSM4HCLQQRKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODY3XFGA#issuecomment-506950296, or mute the thread https://github.com/notifications/unsubscribe-auth/AFIGZISJXT33CFT5IDIL6M3P45BWHANCNFSM4HCLQQRA .

[a1shadows]

@BusyByte Hey, I was attempting to rewrite the code to give an optimal state for the game at every level as opposed to my earlier code that only gave the next best move, but I just realized that the pseudocode only provides an algorithm for the next best move with the assumption that the "MAX" player is making the move. I am unsure how to proceed from here on. Should I try to write the code for the complete algorithm that can calculate moves for both "MIN" and "MAX" players or should I restrict myself to what the book has provided?

[BusyByte]

@a1shadows Looking at the test for the Java version it looks like it should handle both players.

Looking at the Java implementation it just determines which player's turn it is based on the state. So when you call the search function you give it a state so it should just handle it naturally.

I think it selects the max utility of the minimum utility assuming the next player will pick the min. So it doesn't look like the algorithm needs changed to handle both users.

I think your spec may need to change to handle both users. It looks like the java spec is implementing aima 3e Fig 5.2

Sorry for the delay in response. Work has been pretty hectic lately.

[BusyByte]

@a1shadows is this good to go? If you are satisfied I can merge it. It still says WIP in the title so I'm inclined to wait.

[a1shadows]

Ahh. Sorry. I've been busy with work. I'll wrap it up within this weekend.

On Thu, 16 Jan 2020, 1:09 am Shawn Garner, notifications@github.com wrote:

@a1shadows https://github.com/a1shadows is this good to go? If you are satisfied I can merge it.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/aimacode/aima-scala/pull/71?email_source=notifications&email_token=AFIGZIVT26T3YQMRU7P2VN3Q55RABA5CNFSM4HCLQQRKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEJBRPOI#issuecomment-574822329, or unsubscribe https://github.com/notifications/unsubscribe-auth/AFIGZIVP5DUXYEQNCSZFT53Q55RABANCNFSM4HCLQQRA .

[a1shadows]

Still ironing a few things out. I'll let you know when I'm comfortable with the changes. Is that okay?

[BusyByte]

@a1shadows yeah, that's fine but please prioritize this as there are some more PRs coming through and I don't want you to have a bunch of merge conflicts to work through since your PR predates them.

[a1shadows]

I'm satisfied with my changes. Can you review and merge?

[a1shadows]

I decided to not leave that decision up to the caller because the correct behavior will change according to the state for which the decision will be made. For some of the nodes, minMaxValue has to be called for the correct decision and not maxMindecision. Would me like me to change the logic? Sorry for the late reply.

On Sun, Mar 1, 2020 at 10:50 PM Shawn Garner notifications@github.com wrote:

@BusyByte commented on this pull request.

In core/src/main/scala/aima/core/search/adversarial/MinimaxSearch.scala https://github.com/aimacode/aima-scala/pull/71#discussion_r386124778:

+

• def maxValue(state: STATE): UtilityValue = {
• if (g.isTerminalState(state))
• g.getUtility(state)
• else
• minValue(g.result(state, maxMinValue(g.getActions(state))))
• }
• def minValue(state: STATE): UtilityValue = {
• if (g.isTerminalState(state))
• g.getUtility(state)
• else
• maxValue(g.result(state, minMaxValue(g.getActions(state))))
• }
• maxMinValue(g.getActions(g.initialState))

@a1shadows https://github.com/a1shadows I was looking at this when trying to implement alpha beta search and have a question. Why are you passing in the g.initialState rather than state which is passed into the function? this does not seem to match the algorithm.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/aimacode/aima-scala/pull/71?email_source=notifications&email_token=AFIGZIXSKVMEYC4KUHB6NODRFKKMLA5CNFSM4HCLQQRKYY3PNVWWK3TUL52HS4DFWFIHK3DMKJSXC5LFON2FEZLWNFSXPKTDN5WW2ZLOORPWSZGOCXPAWJQ#pullrequestreview-366873382, or unsubscribe https://github.com/notifications/unsubscribe-auth/AFIGZIUA4J4SVH7D6FNHY2DRFKKMLANCNFSM4HCLQQRA .